Near-optimal solutions of large-scale single-machine scheduling problems

Near-optimal solutions of large-scale single-machine scheduling problems

0.00 Avg rating0 Votes
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: , ,
Keywords: programming: dynamic, heuristics
Abstract:

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%.

Reviews

Required fields are marked *. Your email address will not be published.