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 AlahakoonThis 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 ConferencePagination
1167 - 1174Publisher
Association for Computing MachineryLocation
Kyoto, JapanPlace of publication
New York, N.Y.Publisher DOI
Start date
2018-07-15End date
2018-07-19ISBN-13
978-1-4503-5618-3Language
engPublication classification
E1.1 Full written paper - refereedCopyright notice
2018, Association for Computing MachineryEditor/Contributor(s)
Hernán Aguirre, Keiki TakadamaTitle of proceedings
GECCO '18 : Proceedings of the Genetic and Evolutionary Computation ConferenceUsage metrics
Categories
No categories selectedLicence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC