Large Neighborhood Search and Adaptive Randomized Decompositions for Flexible Jobshop Scheduling
Dario Pacino and Pascal Van Hentenryck
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 schemes (ARDS), using random, temporal, and machine decompositions. Empirical results on standard benchmarks show that, within 5 minutes, both LNS and ARDS produce many new best solutions and are about 0.5\% in average from the best-known solutions. Moreover, over longer runtimes, they improve 61\% of the best-known solutions and match the remaining ones. The empirical results also show the importance of hybrid decompositions in LNS and ARDS.