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%.
Near-optimal solutions of large-scale Single Machine Scheduling problems with release dates
AVELLA, Pasquale;
2005-01-01
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%.File | Dimensione | Formato | |
---|---|---|---|
JOC_2005.pdf
non disponibili
Licenza:
Non specificato
Dimensione
131.54 kB
Formato
Adobe PDF
|
131.54 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.