Dr Kevin Sim K.Sim@napier.ac.uk
Lecturer
A previously described hyper-heuristic framework named
NELLI is adapted for the classic Job Shop Scheduling Problem (JSSP) and used to find ensembles of reusable heuristics that cooperate to cover the heuristic search space. A new heuristic generator is incorporated that creates novel heuristics, formulated as GP-like tree structures, by combining problem specific information formulated as a large set of terminal nodes. The new heuristics operate as dynamic dispatching rules, selecting at each iteration the highest priority operation available for scheduling. The new system is trained and tested on a large set of 1400 newly generated problem instances, using both makespan and weighted tardiness as fitness metrics. Results on unseen test instances show
that relatively small ensembles of evolved heuristics significantly outperform any individual one size �fits all heuristic and a greedy selection from a large set of existing rules.
Sim, K., & Hart, E. (2015). A Novel Heuristic Generator for JSSP Using a Tree-Based Representation of Dispatching Rules. In GECCO Companion '15 Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation (1485-1486). https://doi.org/10.1145/2739482.2764697
Conference Name | Proceedings of the Companion Publication of the 2015 on Genetic and Evolutionary Computation Conference - GECCO Companion '15 |
---|---|
Start Date | Jul 11, 2015 |
End Date | Jul 15, 2015 |
Acceptance Date | Mar 21, 2015 |
Publication Date | 2015 |
Deposit Date | May 11, 2015 |
Publicly Available Date | Dec 31, 2015 |
Peer Reviewed | Peer Reviewed |
Pages | 1485-1486 |
Book Title | GECCO Companion '15 Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation |
ISBN | 9781450334884 |
DOI | https://doi.org/10.1145/2739482.2764697 |
Keywords | Novel Heuristic Generator; JSSP; dispatching rules; Hyper-heuristics; Artificial Immune Systems; |
Public URL | http://researchrepository.napier.ac.uk/id/eprint/8053 |
Publisher URL | http://dx.doi.org/10.1145/2739482.2764697 |
A Novel Heuristic Generator for JSSP Using a Tree-Based Representation of Dispatching Rules
(<nobr>168 Kb</nobr>)
PDF
Copyright Statement
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