In this paper we deal with solution algorithms for a general formulation of the job shop problem, called alternative graph. We study in particular the job shop scheduling problem with blocking and/or no-wait constraints. Most of the key properties developed for solving the job shop problem with infinite capacity buffer do not hold in the more general alternative graph model. In this paper we report on an extensive study on the applicability of a metaheuristic approach, called rollout or pilot method. Its basic idea is a look-ahead strategy, guided by one or more subheuristics, called pilot heuristics. Our results indicate that this method is competitive and very promising for solving complex scheduling problems.

Meloni, C., Pacciarelli, D., & Pranzo, M. (2004). A rollout metaheuristic for job-shop scheduling problems. ANNALS OF OPERATIONS RESEARCH, 131(1-4), 215-235 [10.1023/B:ANOR.0000039520.24932.4b].

A rollout metaheuristic for job-shop scheduling problems

PRANZO, MARCO
2004

Abstract

In this paper we deal with solution algorithms for a general formulation of the job shop problem, called alternative graph. We study in particular the job shop scheduling problem with blocking and/or no-wait constraints. Most of the key properties developed for solving the job shop problem with infinite capacity buffer do not hold in the more general alternative graph model. In this paper we report on an extensive study on the applicability of a metaheuristic approach, called rollout or pilot method. Its basic idea is a look-ahead strategy, guided by one or more subheuristics, called pilot heuristics. Our results indicate that this method is competitive and very promising for solving complex scheduling problems.
File in questo prodotto:
File Dimensione Formato  
2004-AOR.pdf

non disponibili

Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 214.54 kB
Formato Adobe PDF
214.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: http://hdl.handle.net/11365/22048
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo