Deakin University
Browse

File(s) under permanent embargo

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

conference contribution
posted on 2018-01-01, 00:00 authored by Su Nguyen, Dhananjay ThiruvadyDhananjay Thiruvady, Andreas T Ernst, Damminda Alahakoon
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.

History

Event

ACM Special Interest Group on Genetic and Evolutionary Computation. Conference (2018 : Kyoto, Japan)

Series

ACM Special Interest Group on Genetic and Evolutionary Computation Conference

Pagination

1167 - 1174

Publisher

Association for Computing Machinery

Location

Kyoto, Japan

Place of publication

New York, N.Y.

Start date

2018-07-15

End date

2018-07-19

ISBN-13

978-1-4503-5618-3

Language

eng

Publication classification

E1.1 Full written paper - refereed

Copyright notice

2018, Association for Computing Machinery

Editor/Contributor(s)

Hernán Aguirre, Keiki Takadama

Title of proceedings

GECCO '18 : Proceedings of the Genetic and Evolutionary Computation Conference

Usage metrics

    Research Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC