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.
Original languageEnglish
Title of host publicationProceedings of the 29th International Conference on Automated Planning and Scheduling (ICAPS'19)
Place of PublicationBerkeley, CA
Publication statusPublished - Jun 2019

ID: 53981396