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:

    Article

  • Date:

    27 April 2016

  • Publication Status:

    Published

  • Publisher

    MIT Press Journal

  • DOI:

    10.1162/EVCO_a_00183

  • ISSN:

    1063-6560

  • Library of Congress:

    QA75 Electronic computers. Computer science

  • Dewey Decimal Classification:

    006.3 Artificial intelligence

Citation

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

Authors

Keywords

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

Monthly Views:

Available Documents