Journal
EVOLUTIONARY COMPUTATION
Volume 24, Issue 4, Pages 609-635Publisher
MIT PRESS
DOI: 10.1162/EVCO_a_00183
Keywords
Job-shop-scheduling; dispatching rule; heuristic ensemble; hyper-heuristic; genetic programming
Funding
- Leverhulme Fellowship [RF-2015-092]
- EPSRC [EP/J021628/1]
- EPSRC [EP/J021628/1] Funding Source: UKRI
- Engineering and Physical Sciences Research Council [EP/J021628/1] Funding Source: researchfish
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available