Tabu-Based Large Neighbourhood Search for Time/Sequence-Dependent Scheduling Problems with Time Windows

Tabu-Based Large Neighbourhood Search for Time/Sequence-Dependent Scheduling Problems with Time Windows

He, L. (TU Delft Algorithmics; National University of Defense Technology)
de Weerdt, M.M. (TU Delft Algorithmics)
Yorke-Smith, N. (TU Delft Algorithmics)

Benton, J. (editor)
Lipovetzky, Nir (editor)
Onaindia, Eva (editor)
Smith, David E. (editor)
Srivastava, Siddharth (editor)

2019-06

An important class of scheduling problems is characterised by time-dependency and/or sequence-dependency with time windows. We introduce and analyze four algorithmic ideas for this class: a novel hybridization of adaptive large neighbourhood search (ALNS) and tabu search (TS), randomized generic neighbourhood operators, a partial sequence dominance heuristic, and a fast insertion strategy. An evaluation of the resulting hybrid algorithm on two domains, a real-world multi-orbit agile Earth observation satellite scheduling problem, and an order acceptance and scheduling problem, shows that it robustly outperforms a mixed integer programming method, a two-stage hybridization of ALNS and TS, and recent state-of-the-art metaheuristic methods.

http://resolver.tudelft.nl/uuid:b2e093c8-5683-4d68-8069-4c306531e5dc

Association for the Advancement of Artificial Intelligence (AAAI), Berkeley, CA

2020-01-05

9781577358077

Proceedings of the 29th International Conference on Automated Planning and Scheduling, ICAPS 2019, 29

29th International Conference on Automated Planning and Scheduling, 2019-07-11 → 2019-07-15, Berkeley, United States

Proceedings International Conference on Automated Planning and Scheduling, ICAPS, 2334-0835

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Institutional Repository

conference paper

© 2019 L. He, M.M. de Weerdt, N. Yorke-Smith