Lower bounds for the earliness-tardiness scheduling problem on single and parallel machines

Safia Kedad-Sidhoum (Safia.Kedad-Sidhoumlip6.fr)
Yasmin Rios Solis (Yasmin.Rioslip6.fr)
Francis Sourd (Francis.Sourdlip6.fr)

Abstract: This paper addresses the parallel machine scheduling problem in which the jobs have distinct due dates with earliness and tardiness costs. New lower bounds are proposed for the problem, they can be classed into two families. First, two assignment-based lower bounds for the one-machine problem are generalized for the parallel machine case. Second, a time-indexed formulation of the problem is investigated in order to derive efficient lower bounds throught column generation or Lagrangean relaxation. A simple local search algorithm is also presented in order to derive an upper bound. Computational experiments compare these bounds for both the one machine and parallel machine problems and show that the gap between upper and lower bounds is about 1%.

Keywords: Parallel machine scheduling, earliness-tardiness, Just-in-Time, lower bounds, IP time-indexed formulation

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

Citation: To appear in European Journal of Operation Research [link]

Download: [Compressed Postscript][PDF]

Entry Submitted: 10/27/2004
Entry Accepted: 10/27/2004
Entry Last Modified: 06/22/2007

Modify/Update this entry