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

Authors

  • Lei He National University of Defense Technology
  • Mathijs de Weerdt Delft University of Technology
  • Neil Yorke-Smith Delft University of Technology

Abstract

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 realworld 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.

Downloads

Published

2019-07-06

How to Cite

He, L., de Weerdt, M., & Yorke-Smith, N. (2019). Tabu-Based Large Neighbourhood Search for Time/Sequence-Dependent Scheduling Problems with Time Windows. Proceedings of the International Conference on Automated Planning and Scheduling, 29(1), 186-194. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/3475