Skip to main content

Research Repository

Advanced Search

An analysis of indirect optimisation strategies for scheduling.

Neau, Charles; Regnier-Coudert, Olivier; McCall, John

Authors

Charles Neau

Olivier Regnier-Coudert

John McCall



Abstract

By incorporating domain knowledge, simple greedy procedures can be defined to generate reasonably good solutions to many optimisation problems. However, such solutions are unlikely to be optimal and their quality often depends on the way the decision variables are input to the greedy method. Indirect optimisation uses meta-heuristics to optimise the input of the greedy decoders. As the performance and the runtime differ across greedy methods and meta-heuristics, deciding how to split the computational effort between the two sides of the optimisation is not trivial and can significantly impact the search. In this paper, an artificial scheduling problem is presented along with five greedy procedures, using varying levels of domain information. A methodology to compare different indirect optimisation strategies is presented using a simple Hill Climber, a Genetic Algorithm and a population-based Local Search. By assessing all combinations of meta-heuristics and greedy procedures on a range of problem instances with different properties, experiments show that encapsulating problem knowledge within greedy decoders may not always prove successful and that simpler methods can lead to comparable results as advanced ones when combined with meta-heuristics that are adapted to the problem. However, the use of efficient greedy procedures reduces the relative difference between meta-heuristics.

Citation

NEAU, C., REGNIER-COUDERT, O. and MCCALL, J. 2018. An analysis of indirect optimisation strategies for scheduling. In Proceedings of Institute of Electrical and Electronics Engineers (IEEE) congress on evolutionary computation (IEEE CEC 2018), 8-13 July 2018, Rio de Janeiro, Brazil. Piscataway, NJ: IEEE [online], article ID 8477967. Available from: https://doi.org/10.1109/CEC.2018.8477967

Conference Name Institute of Electrical and Electronics Engineers (IEEE) congress on evolutionary computation (IEEE CEC 2018)
Conference Location Rio de Janeiro, Brazil
Start Date Jul 8, 2018
End Date Jul 13, 2018
Acceptance Date Mar 15, 2018
Online Publication Date Oct 4, 2018
Publication Date Oct 4, 2018
Deposit Date Jan 4, 2019
Publicly Available Date Jan 4, 2019
Publisher Institute of Electrical and Electronics Engineers
Article Number 8477967
DOI https://doi.org/10.1109/CEC.2018.8477967
Keywords Decoding; Optimization; Resource management; Processor scheduling; Runtime; Scheduling; Schedules
Public URL http://hdl.handle.net/10059/3242

Files





You might also like



Downloadable Citations