A Hyper-Heuristic Ensemble Method for Static Job-shop Scheduling
Sim, K. (2016). A Hyper-Heuristic Ensemble Method for Static Job-shop Scheduling. Evolutionary Computation, (pre-print, accepted for publication May 2016), (), .
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.
Director of CEC
+44 131 455 2783
+44 131 455 2497
Areas of Expertise
See all areas of expertise
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.