Research Output

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

  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.

  • Type:


  • Date:

    27 April 2016

  • Publication Status:


  • Publisher

    MIT Press Journal

  • DOI:


  • ISSN:


  • Library of Congress:

    QA75 Electronic computers. Computer science

  • Dewey Decimal Classification:

    006.3 Artificial intelligence


Hart, E., & Sim, K. (2016). A hyper-heuristic ensemble method for static job-shop scheduling. Evolutionary Computation, 24(4), (609-635). doi:10.1162/EVCO_a_00183. ISSN 1063-6560



Job-shop-scheduling; dispatching rule; heuristic ensemble; hyper-heuristic; genetic programming;

Monthly Views:

Available Documents