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)
EditorsJ. Benton, N. Lipovetzky, E. Onaindia, D.E. Smith, S. Srivastave
Place of PublicationBerkeley, CA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages9
Publication statusPublished - Jun 2019
Event29th International Conference on Automated Planning and Scheduling - Berkeley, United States
Duration: 11 Jul 201915 Jul 2019
Conference number: 29


Conference29th International Conference on Automated Planning and Scheduling
Abbreviated titleICAPS
CountryUnited States

ID: 53981396