A Rollout Metaheuristic for Job Shop Scheduling Problems

Carlo Meloni, Dario Pacciarelli () and Marco Pranzo

Annals of Operations Research, 2004, vol. 131, issue 1, 215-235

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. Copyright Kluwer Academic Publishers 2004

Keywords: metaheuristics; job shop scheduling; rollout; alternative graph (search for similar items in EconPapers)
Date: 2004
References: Add references at CitEc
Citations: View citations in EconPapers (17)

Downloads: (external link)
http://hdl.handle.net/10.1023/B:ANOR.0000039520.24932.4b (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:131:y:2004:i:1:p:215-235:10.1023/b:anor.0000039520.24932.4b

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/B:ANOR.0000039520.24932.4b

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().