Large Neighborhood Search and Adaptive Randomized Decompositions for Flexible Jobshop Scheduling

Dario Pacino, Pascal Van Hentenryck

Research output: Contribution to journalConference articleResearch

297 Downloads (Pure)

Abstract

This paper considers a constraint-based scheduling approach to the flexible jobshop, a generalization of the traditional jobshop scheduling where activities have a choice of machines. It studies both large neighborhood (LNS) and adaptive randomized decomposition (ARD) schemes, using random, temporal, and machine decompositions. Empirical results on standard benchmarks show that, within 5 minutes, both LNS and ARD produce many new best solutions and are about 0.5 % in average from the best-known solutions. Moreover, over longer runtimes, they improve 60 % of the best-known solutions and match the remaining ones. The empirical results also show the importance of hybrid decompositions in LNS and ARD.
Original languageEnglish
JournalProceedings of the International Joint Conference on Artificial Intelligence
Number of pages6
ISSN1045-0823
Publication statusPublished - 2011
Externally publishedYes
Event22nd International Joint Conference on Artificial Intelligence - Barcelona, Spain
Duration: 16 Jul 201122 Jul 2011
Conference number: 22

Conference

Conference22nd International Joint Conference on Artificial Intelligence
Number22
CountrySpain
CityBarcelona
Period16/07/201122/07/2011

Cite this