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

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 in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12070/180
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 22
  • ???jsp.display-item.citation.isi??? ND
social impact