Research Output
A Novel Heuristic Generator for JSSP Using a Tree-Based Representation of Dispatching Rules
  A previously described hyper-heuristic framework named
NELLI is adapted for the classic Job Shop Scheduling Problem (JSSP) and used to find ensembles of reusable heuristics that cooperate to cover the heuristic search space. A new heuristic generator is incorporated that creates novel heuristics, formulated as GP-like tree structures, by combining problem specific information formulated as a large set of terminal nodes. The new heuristics operate as dynamic dispatching rules, selecting at each iteration the highest priority operation available for scheduling. The new system is trained and tested on a large set of 1400 newly generated problem instances, using both makespan and weighted tardiness as fitness metrics. Results on unseen test instances show
that relatively small ensembles of evolved heuristics significantly outperform any individual one size �fits all heuristic and a greedy selection from a large set of existing rules.

  • Date:

    31 December 2015

  • Publication Status:

    Published

  • DOI:

    10.1145/2739482.2764697

  • Library of Congress:

    QA75 Electronic computers. Computer science

  • Dewey Decimal Classification:

    004 Data processing & computer science

  • Funders:

    Engineering and Physical Sciences Research Council

Citation

Sim, K., & Hart, E. (2015). A Novel Heuristic Generator for JSSP Using a Tree-Based Representation of Dispatching Rules. In GECCO Companion '15 Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation, (1485-1486). https://doi.org/10.1145/2739482.2764697

Authors

Keywords

Novel Heuristic Generator; JSSP; dispatching rules; Hyper-heuristics; Artificial Immune Systems;

Monthly Views:

Available Documents