A Hyper-Heuristic Ensemble Method for Static Job-shop Scheduling

Hart, E., Sim, K. (2016). A Hyper-Heuristic Ensemble Method for Static Job-shop Scheduling. Evolutionary Computation, (pre-print, accepted for publication May 2016), (), .


ISBN:
ISSN:

Abstract

We describe a new hyper-heuristic method NELLI-GP for solving job-shop schedul- ing 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 in- stance 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.
[Read More]

Authors

Emma Hart
Director of CEC
e.hart@napier.ac.uk
+44 131 455 2783
Kevin Sim
Lecturer
K.Sim@napier.ac.uk
+44 131 455 2497

Areas of Expertise

Bio-inspired Computing
The Bio-Inspired Algorithms group within the Centre for Algorithms, Visualisation and Evolving Systems is a large and thriving group with interests in nature-inspired computing that include Evolutionary Computing, Hyper-Heuristics, Artificial Immune Systems and Swarm Intelligence.