Deakin University

File(s) under permanent embargo

Evolving Large Reusable Multi-pass Heuristics for Resource Constrained Job Scheduling

conference contribution
posted on 2020-01-01, 00:00 authored by Su Nguyen, Dhananjay ThiruvadyDhananjay Thiruvady
Resource constrained job scheduling is a challenging combinatorial optimisation with many real-world applications. A number of exact methods and meta-heuristics have been proposed in the literature to solve this problem, but often encounter scalability issues. This paper investigates an automated heuristic design approach to deal with this problem. The aim of this approach is to generate heuristics that can quickly construct good solutions, which can be applied directly or used to initialise other meta-heuristics. A new adaptive genetic programming algorithm is proposed to coevolve a large set of reusable heuristics to solve the resource constrained job scheduling problem. There are three different aspects to the novelty behind our proposed algorithm: (a) a new phenotypic representation of heuristics, (b) an efficient mapping technique to monitor the evolutionary process, and (c) an adaptive fitness function to guide the search towards a diverse and competitive population. The experimental results show that evolved heuristics show promise and are able to outperform some existing meta-heuristics for large-scale instances. Analyses also show that the algorithm can be further improved if appropriate parameters are selected.



Congress on Evolutionary Computation (2020 : Online from Glasgow, Scotland)


1 - 8




Online from Glasgow, Scotland

Place of publication

Piscataway, N.J.

Start date


End date






Publication classification

E1 Full written paper - refereed

Title of proceedings

CEC 2020 : Proceedings from the IEEE Congress on Evolutionary Computation