ML Anthology

Large Neighborhood Search and Adaptive Randomized Decompositions for Flexible Jobshop Scheduling

Dario Pacino, Pascal Van Hentenryck
IJCAI 2011 pp. 1997-2002
doi:10.5591/978-1-57735-516-8/IJCAI11-333 /ijcai/2011/pacino2011ijcai-large/

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.

PDF IJCAI Semantic Scholar

Cite

Text

Pacino and Van Hentenryck. "Large Neighborhood Search and Adaptive Randomized Decompositions for Flexible Jobshop Scheduling." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-333

Markdown

[Pacino and Van Hentenryck. "Large Neighborhood Search and Adaptive Randomized Decompositions for Flexible Jobshop Scheduling." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/pacino2011ijcai-large/) doi:10.5591/978-1-57735-516-8/IJCAI11-333

BibTeX

@inproceedings{pacino2011ijcai-large,
  title     = {{Large Neighborhood Search and Adaptive Randomized Decompositions for Flexible Jobshop Scheduling}},
  author    = {Pacino, Dario and Van Hentenryck, Pascal},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2011},
  pages     = {1997-2002},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-333},
  url       = {https://mlanthology.org/ijcai/2011/pacino2011ijcai-large/}
}