Article ID: | iaor2007169 |
Country: | United States |
Volume: | 17 |
Issue: | 2 |
Start Page Number: | 183 |
End Page Number: | 191 |
Publication Date: | Mar 2005 |
Journal: | INFORMS Journal On Computing |
Authors: | Avella Pasquale, Boccia Maurizio, D'Auria Bernardo |
Keywords: | programming: dynamic, heuristics |
The single-machine scheduling problem (SMSP) with release dates concerns the optimal allocation of a set of jobs on a single machine that is not able to process more than one job at a time. Each job is ready to be processed at a release date and without interruption. The goal is to minimize the total weighted completion time of the jobs. In this paper the time-indexed formulation is considered and a new lagrangean heuristic is proposed, based on the observation that lagrangean relaxation of job constraints leads to a weighted stable set problem on an interval graph. The relaxed problem is polynomially solvable by a dynamic-programming algorithm. We report computational experience, showing that instances up to 400 jobs and maximum processing time 50 (around 5,000,000 variables) are solved in less than 40 minutes on a personal computer, yielding duality gaps never exceeding 3%. We also test a set of hard instances, built to produce bad performances where we yield duality gaps less than 5%.