A hyper-heuristic ensemble method for static job-shop scheduling.

Hart, Emma; Sim, Kevin

Abstract

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.

• 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
• Contract Date: Apr 12, 2016