An efficient algorithm for the earliness-tardiness scheduling problem

Francis Sourd (Francis.Sourdlip6.fr)
Safia Kedad-Sidhoum (Safia.Kedad-Sidhoumlip6.fr)

Abstract: This paper addresses the one-machine scheduling problem with earliness-tardiness penalties. We propose a new branch-and-bound algorithm that can solve instances with up to 50 jobs and that can solve problems with even more general non-convex cost functions. The algorithm is based on the combination of a Lagrangean relaxation of resource constraints and new dominance rules.

Keywords: Earliness-tardiness scheduling

Category 1: Applications -- OR and Management Sciences (Scheduling )

Citation: Published in Journal of Scheduling

Download:

Entry Submitted: 09/07/2005
Entry Accepted: 09/07/2005
Entry Last Modified: 11/23/2007

Modify/Update this entry