An analysis of indirect optimisation strategies for scheduling.

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

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

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Institute of Electrical and Electronics Engineers (IEEE) congress on evolutionary computation (IEEE CEC 2018)
• 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 (IEEE)
• Peer Reviewed: Peer Reviewed
• 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
• Contract Date: Jan 4, 2019