File(s) under permanent embargo
Evolving Large Reusable Multi-pass Heuristics for Resource Constrained Job Scheduling
conference contributionposted 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.
EventCongress on Evolutionary Computation (2020 : Online from Glasgow, Scotland)
Pagination1 - 8
LocationOnline from Glasgow, Scotland
Place of publicationPiscataway, N.J.
Publication classificationE1 Full written paper - refereed
Title of proceedingsCEC 2020 : Proceedings from the IEEE Congress on Evolutionary Computation
Read the peer-reviewed publication
genetic programmingschedulinglearningScience & TechnologyTechnologyLife Sciences & BiomedicineComputer Science, Artificial IntelligenceComputer Science, Theory & MethodsEngineering, Electrical & ElectronicMathematical & Computational BiologyOperations Research & Management ScienceComputer ScienceEngineeringDESIGNCLASSIFICATIONEVOLUTIONHYBRIDACOCORE2020 B