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

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

3 Citations (Scopus)
67 Downloads (Pure)

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 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 2019
EditorsJ. Benton, Nir Lipovetzky, Eva Onaindia, David E. Smith, Siddharth Srivastava
Place of PublicationBerkeley, CA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages186-194
Number of pages9
Volume29
ISBN (Electronic)9781577358077
Publication statusPublished - Jun 2019
Event29th International Conference on Automated Planning and Scheduling - Berkeley, United States
Duration: 11 Jul 201915 Jul 2019
Conference number: 29

Publication series

NameProceedings International Conference on Automated Planning and Scheduling, ICAPS
ISSN (Print)2334-0835
ISSN (Electronic)2334-0843

Conference

Conference29th International Conference on Automated Planning and Scheduling
Abbreviated titleICAPS
CountryUnited States
CityBerkeley
Period11/07/1915/07/19

Fingerprint Dive into the research topics of 'Tabu-Based Large Neighbourhood Search for Time/Sequence-Dependent Scheduling Problems with Time Windows'. Together they form a unique fingerprint.

Cite this