Genetic programming approach to learning multi-pass heuristics for resource constrained job scheduling

Su Nguyen, Dhananjay Thiruvady, Andreas Ernst, Damminda Alahakoon

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)

Abstract

This study considers a resource constrained job scheduling problem. Jobs need to be scheduled on different machines satisfying a due time. If delayed, the jobs incur a penalty which is measured as a weighted tardiness. Furthermore, the jobs use up some proportion of an available resource and hence there are limits on multiple jobs executing at the same time. Due to complex constraints and a large number of decision variables, the existing solution methods, based on meta-heuristics and mathematical programming, are very time-consuming and mainly suitable for small-scale problem instances. We investigate a genetic programming approach to automatically design reusable scheduling heuristics for this problem. A new representation and evaluation mechanisms are developed to provide the evolved heuristics with the ability to effectively construct and refine schedules. The experiments show that the proposed approach is more efficient than other genetic programming algorithms previously developed for evolving scheduling heuristics. In addition, we find that the obtained heuristics can be effectively reused to solve unseen and large-scale instances and often find higher quality solutions compared to algorithms already known in the literature in significantly reduced time-frames.

Original languageEnglish
Title of host publicationGECCO 2018
Subtitle of host publicationProceedings of the 2018 Genetic and Evolutionary Computation Conference
EditorsKeiki Takadama
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Pages1167-1174
Number of pages8
ISBN (Electronic)9781450356183
DOIs
Publication statusPublished - 2 Jul 2018
EventThe Genetic and Evolutionary Computation Conference, 2018 - Kyoto, Japan
Duration: 15 Jul 201819 Jul 2018
http://gecco-2018.sigevo.org/index.html/tiki-index.php

Conference

ConferenceThe Genetic and Evolutionary Computation Conference, 2018
Abbreviated titleGECCO 2018
CountryJapan
CityKyoto
Period15/07/1819/07/18
OtherThe Genetic and Evolutionary Computation Conference (GECCO) presents the latest high-quality results in genetic and evolutionary computation since 1999. Topics include: genetic algorithms, genetic programming, ant colony optimization and swarm intelligence, complex systems (artificial life/robotics/evolvable hardware/generative and developmental systems/artificial immune systems), digital entertainment technologies and arts, evolutionary combinatorial optimization and metaheuristics, evolutionary machine learning, evolutionary multiobjective optimization, evolutionary numerical optimization, real world applications, search-based software engineering, theory and more.
Internet address

Keywords

  • Combinatorial optimisation
  • Genetic programming
  • Scheduling

Cite this