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

Lei He; Mathijs de Weerdt; Neil Yorke-Smith

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

Lei He, Mathijs de Weerdt, Neil Yorke-Smith

Algorithmics

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

11 Citations (Scopus)

110 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 language	English
Title of host publication	Proceedings of the 29th International Conference on Automated Planning and Scheduling, ICAPS 2019
Editors	J. Benton, Nir Lipovetzky, Eva Onaindia, David E. Smith, Siddharth Srivastava
Place of Publication	Berkeley, CA
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Pages	186-194
Number of pages	9
Volume	29
ISBN (Electronic)	9781577358077
Publication status	Published - Jun 2019
Event	29th International Conference on Automated Planning and Scheduling - Berkeley, United States Duration: 11 Jul 2019 → 15 Jul 2019 Conference number: 29

Publication series

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

Conference

Conference	29th International Conference on Automated Planning and Scheduling
Abbreviated title	ICAPS
Country/Territory	United States
City	Berkeley
Period	11/07/19 → 15/07/19

Bibliographical note

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.

Access to Document

3475-Article Text-6524-1-10-20190619Final published version, 424 KB

https://aaai.org/ojs/index.php/ICAPS/article/view/3475

Cite this

He, L., de Weerdt, M., & Yorke-Smith, N. (2019). Tabu-Based Large Neighbourhood Search for Time/Sequence-Dependent Scheduling Problems with Time Windows. In J. Benton, N. Lipovetzky, E. Onaindia, D. E. Smith, & S. Srivastava (Eds.), Proceedings of the 29th International Conference on Automated Planning and Scheduling, ICAPS 2019 (Vol. 29, pp. 186-194). (Proceedings International Conference on Automated Planning and Scheduling, ICAPS). Association for the Advancement of Artificial Intelligence (AAAI). https://aaai.org/ojs/index.php/ICAPS/article/view/3475

He, Lei ; de Weerdt, Mathijs ; Yorke-Smith, Neil. / Tabu-Based Large Neighbourhood Search for Time/Sequence-Dependent Scheduling Problems with Time Windows. Proceedings of the 29th International Conference on Automated Planning and Scheduling, ICAPS 2019. editor / J. Benton ; Nir Lipovetzky ; Eva Onaindia ; David E. Smith ; Siddharth Srivastava. Vol. 29 Berkeley, CA : Association for the Advancement of Artificial Intelligence (AAAI), 2019. pp. 186-194 (Proceedings International Conference on Automated Planning and Scheduling, ICAPS).

@inproceedings{b2e093c856834d6880694c306531e5dc,

title = "Tabu-Based Large Neighbourhood Search for Time/Sequence-Dependent Scheduling Problems with Time Windows",

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.",

author = "Lei He and {de Weerdt}, Mathijs and Neil Yorke-Smith",

note = "Green Open Access added to TU Delft Institutional Repository {\textquoteleft}You share, we take care!{\textquoteright} – 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.; 29th International Conference on Automated Planning and Scheduling, ICAPS ; Conference date: 11-07-2019 Through 15-07-2019",

year = "2019",

month = jun,

language = "English",

volume = "29",

series = "Proceedings International Conference on Automated Planning and Scheduling, ICAPS",

publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",

pages = "186--194",

editor = "J. Benton and Nir Lipovetzky and Eva Onaindia and Smith, {David E.} and Siddharth Srivastava",

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

address = "United States",

}

He, L, de Weerdt, M & Yorke-Smith, N 2019, Tabu-Based Large Neighbourhood Search for Time/Sequence-Dependent Scheduling Problems with Time Windows. in J Benton, N Lipovetzky, E Onaindia, DE Smith & S Srivastava (eds), Proceedings of the 29th International Conference on Automated Planning and Scheduling, ICAPS 2019. vol. 29, Proceedings International Conference on Automated Planning and Scheduling, ICAPS, Association for the Advancement of Artificial Intelligence (AAAI), Berkeley, CA, pp. 186-194, 29th International Conference on Automated Planning and Scheduling, Berkeley, California, United States, 11/07/19. <https://aaai.org/ojs/index.php/ICAPS/article/view/3475>

Tabu-Based Large Neighbourhood Search for Time/Sequence-Dependent Scheduling Problems with Time Windows. / He, Lei; de Weerdt, Mathijs ; Yorke-Smith, Neil.
Proceedings of the 29th International Conference on Automated Planning and Scheduling, ICAPS 2019. ed. / J. Benton; Nir Lipovetzky; Eva Onaindia; David E. Smith; Siddharth Srivastava. Vol. 29 Berkeley, CA: Association for the Advancement of Artificial Intelligence (AAAI), 2019. p. 186-194 (Proceedings International Conference on Automated Planning and Scheduling, ICAPS).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

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

AU - He, Lei

AU - de Weerdt, Mathijs

AU - Yorke-Smith, Neil

N1 - Conference code: 29

PY - 2019/6

Y1 - 2019/6

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

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

UR - http://www.scopus.com/inward/record.url?scp=85077018430&partnerID=8YFLogxK

M3 - Conference contribution

VL - 29

T3 - Proceedings International Conference on Automated Planning and Scheduling, ICAPS

SP - 186

EP - 194

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

A2 - Benton, J.

A2 - Lipovetzky, Nir

A2 - Onaindia, Eva

A2 - Smith, David E.

A2 - Srivastava, Siddharth

PB - Association for the Advancement of Artificial Intelligence (AAAI)

CY - Berkeley, CA

T2 - 29th International Conference on Automated Planning and Scheduling

Y2 - 11 July 2019 through 15 July 2019

ER -

He L, de Weerdt M , Yorke-Smith N. Tabu-Based Large Neighbourhood Search for Time/Sequence-Dependent Scheduling Problems with Time Windows. In Benton J, Lipovetzky N, Onaindia E, Smith DE, Srivastava S, editors, Proceedings of the 29th International Conference on Automated Planning and Scheduling, ICAPS 2019. Vol. 29. Berkeley, CA: Association for the Advancement of Artificial Intelligence (AAAI). 2019. p. 186-194. (Proceedings International Conference on Automated Planning and Scheduling, ICAPS).

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

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

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

Supplementary data for the article: Time/sequence-dependent scheduling: the design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm

Source code for the article: Time/sequence-dependent scheduling: the design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm

Cite this

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

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Datasets

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

Supplementary data for the article: Time/sequence-dependent scheduling: the design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm

Source code for the article: Time/sequence-dependent scheduling: the design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm

Cite this