Prof Emma Hart E.Hart@napier.ac.uk
Professor
We describe a new hyper-heuristic method NELLI-GP for solving job-shop scheduling problems (JSSP) that evolves an ensemble of heuristics. The ensemble adopts a divide-and-conquer approach in which each heuristic solves a unique subset of the instance set considered. NELLI-GP extends an existing ensemble method called NELLI by introducing a novel heuristic generator that evolves heuristics composed of linear sequences of dispatching rules: each rule is represented using a tree structure and is itself evolved. Following a training period, the ensemble is shown to outperform both existing dispatching rules and a standard genetic programming algorithm on a large set of new test instances. In addition, it obtains superior results on a set of 210 benchmark problems from the literature when compared to two state-of-the-art hyperheuristic approaches. Further analysis of the relationship between heuristics in the evolved ensemble and the instances each solves provides new insights into features that might describe similar instances.
Hart, E., & Sim, K. (2016). A hyper-heuristic ensemble method for static job-shop scheduling. Evolutionary Computation, 24(4), 609-635. https://doi.org/10.1162/EVCO_a_00183
Journal Article Type | Article |
---|---|
Acceptance Date | Apr 6, 2016 |
Online Publication Date | Apr 27, 2016 |
Publication Date | Apr 27, 2016 |
Deposit Date | Apr 12, 2016 |
Publicly Available Date | Jul 28, 2016 |
Journal | Evolutionary Computation |
Print ISSN | 1063-6560 |
Electronic ISSN | 1530-9304 |
Publisher | MIT Press |
Peer Reviewed | Peer Reviewed |
Volume | 24 |
Issue | 4 |
Pages | 609-635 |
DOI | https://doi.org/10.1162/EVCO_a_00183 |
Keywords | Job-shop-scheduling; dispatching rule; heuristic ensemble; hyper-heuristic; genetic programming; |
Public URL | http://researchrepository.napier.ac.uk/id/eprint/9844 |
Publisher URL | http://dx.doi.org/10.1162/EVCO_a_00183 |
A hyper-heuristic ensemble method for static job-shop scheduling.
(<nobr>1.1 Mb</nobr>)
PDF
Evolutionary Approaches to Improving the Layouts of Instance-Spaces
(2022)
Conference Proceeding
Minimising line segments in linear diagrams is NP-hard
(2022)
Journal Article
A Neural Approach to Generation of Constructive Heuristics
(2021)
Conference Proceeding
Drawing Algorithms For Linear Diagrams (Supplementary)
(2020)
Dataset
Algorithm selection using deep learning without feature extraction
(2019)
Conference Proceeding
About Edinburgh Napier Research Repository
Administrator e-mail: repository@napier.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Advanced Search