Dr Kevin Sim K.Sim@napier.ac.uk
Lecturer
A Novel Heuristic Generator for JSSP Using a Tree-Based Representation of Dispatching Rules
Sim, Kevin; Hart, Emma
Abstract
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.
Citation
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 |
Files
A Novel Heuristic Generator for JSSP Using a Tree-Based Representation of Dispatching Rules
(168 Kb)
PDF
Copyright Statement
This is the author’s version of the work. It is posted herefor your personal use. Not for redistribution. The definitiveVersion was published in GECCO 2015,
http://dx.doi.org/10.1145/2739482.2764697
You might also like
Evolving Behavior Allocations in Robot Swarms
(2024)
Conference Proceeding
Towards optimisers that `Keep Learning'
(2023)
Conference Proceeding
A Feature-Free Approach to Automated Algorithm Selection
(2023)
Conference Proceeding
Downloadable Citations
About Edinburgh Napier Research Repository
Administrator e-mail: repository@napier.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
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/)
Powered by Worktribe © 2024
Advanced Search