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, July). A Novel Heuristic Generator for JSSP Using a Tree-Based Representation of Dispatching Rules. Presented at Proceedings of the Companion Publication of the 2015 on Genetic and Evolutionary Computation Conference - GECCO Companion '15

• 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
• Contract Date: May 11, 2015