Skip to main content

Research Repository

Advanced Search

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

Hart, Emma; Sim, Kevin



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
Keywords Job-shop-scheduling; dispatching rule; heuristic ensemble; hyper-heuristic; genetic programming;
Public URL
Publisher URL
Contract Date Apr 12, 2016


A hyper-heuristic ensemble method for static job-shop scheduling. (1.1 Mb)

You might also like

Downloadable Citations