Large Neighborhood Search and Adaptive Randomized Decompositions for Flexible Jobshop Scheduling

Pacino, Dario; Van Hentenryck, Pascal

doi:10.5591/978-1-57735-516-8/IJCAI11-333

Large Neighborhood Search and Adaptive Randomized Decompositions for Flexible Jobshop Scheduling

Dario Pacino, Pascal Van Hentenryck

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 1997-2001.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-333

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.

Dario Pacino, and Pascal Van Hentenryck. 2011. Large Neighborhood Search and Adaptive Randomized Decompositions for Flexible Jobshop Scheduling. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 1997–2001. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-333

@inproceedings{ijcai2011p333,
  title     = {Large Neighborhood Search and Adaptive Randomized Decompositions for Flexible Jobshop Scheduling},
  author    = {Pacino, Dario and Van Hentenryck, Pascal},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {1997--2001},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-333},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-333},
}

TY  - CPAPER
TI  - Large Neighborhood Search and Adaptive Randomized Decompositions for Flexible Jobshop Scheduling
AU  - Pacino, Dario
AU  - Van Hentenryck, Pascal
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 1997
EP  - 2001
DO  - 10.5591/978-1-57735-516-8/IJCAI11-333
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-333
ER  -