Quarterly (spring, summer, fall, winter)
176 pp. per issue
7 x 10
ISSN
1063-6560
E-ISSN
1530-9304
2014 Impact factor:
2.37

Evolutionary Computation

Winter 2016, Vol. 24, No. 4, Pages 609-635
(doi: 10.1162/EVCO_a_00183)
© 2016 Massachusetts Institute of Technology
A Hyper-Heuristic Ensemble Method for Static Job-Shop Scheduling
Article PDF (1.23 MB)
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 hyper-heuristic 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.