Abstract
The Order Acceptance and Scheduling (OAS) problem describes a class of real-world problems such as in smart manufacturing and satellite scheduling. This problem consists of simultaneously selecting a subset of orders to be processed as well as determining the associated schedule. A common generalization includes sequence-dependent setup times and time windows. We propose a novel memetic algorithm for this problem, called Sparrow. It comprises a hybridization of biased random key genetic algorithm (BRKGA) and adaptive large neighbourhood search (ALNS). Sparrow integrates the exploration ability of BRKGA and the exploitation ability of ALNS. On a set of standard benchmark instances, this algorithm obtains better-quality solutions with runtimes comparable to state-of-the-art algorithms. To further understand the strengths and weaknesses of these algorithms, their performance is also compared on a set of new benchmark instances with more realistic properties. We conclude that Sparrow is distinguished by its ability to solve difficult instances from the OAS literature, and that the hybrid steady-state genetic algorithm (HSSGA) performs well on large instances in terms of optimality gap, although taking more time than Sparrow.
Original language | English |
---|---|
Article number | 106102 |
Pages (from-to) | 1-15 |
Number of pages | 15 |
Journal | Computers and Industrial Engineering |
Volume | 138 |
DOIs | |
Publication status | Published - 2019 |
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-careOtherwise 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.
Keywords
- Adaptive large neighbourhood search
- Biased random key genetic algorithm
- Memetic algorithm
- Order acceptance and scheduling
- Sequence-dependent setup times
Fingerprint
Dive into the research topics of 'Order Acceptance and Scheduling with Sequence-Dependent Setup Times: A New Memetic Algorithm and Benchmark of the State of the Art'. Together they form a unique fingerprint.Datasets
-
Supplementary data for the article: Time/sequence-dependent scheduling: the design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm
He, L. (Creator), de Weerdt, M. M. (Creator), Yorke-Smith, N. (Creator), Aghezzaf, E. (Creator), Cesaret, B. (Creator), Oguz, C. (Creator), Salman, S. (Creator), Vansteenwegen, P. (Creator) & Verbeeck, C. (Creator), TU Delft - 4TU.ResearchData, 28 Dec 2019
DOI: 10.4121/UUID:1A4E5895-7DAE-4B6A-9315-A9E8CB463D73
Dataset/Software: Dataset
-
Supplementary data for the article: Order Acceptance and Scheduling with Sequence-dependent Setup Times: a New Memetic Algorithm and Benchmark of the State of the Art
He, L. (Creator), Guijt, A. (Creator), de Weerdt, M. M. (Creator), Xing, L. (Creator), Yorke-Smith, N. (Creator), Cesaret, B. (Contributor), Oguz, C. (Contributor) & Salman, S. (Contributor), TU Delft - 4TU.ResearchData, 31 Oct 2019
DOI: 10.4121/UUID:C3623076-A1AC-4103-AD31-3068A28312F9
Dataset/Software: Dataset
-
Source code for the article: Time/sequence-dependent scheduling: the design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm
He, L. (Creator), de Weerdt, M. M. (Creator) & Yorke-Smith, N. (Creator), TU Delft - 4TU.ResearchData, 28 Dec 2019
DOI: 10.4121/UUID:3A23B216-3762-4A61-BA2C-D3DF6DC53268
Dataset/Software: Dataset