Skip to main content

Research Repository

Advanced Search

A Novel Heuristic Generator for JSSP Using a Tree-Based Representation of Dispatching Rules

Sim, Kevin; Hart, Emma

Authors



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.

Presentation Conference Type Conference Paper (Published)
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
Contract Date May 11, 2015

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



Downloadable Citations