Charles Neau
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 |
Files
NEAU 2018 An analysis of indirect
(1.1 Mb)
PDF
Publisher Licence URL
https://creativecommons.org/licenses/by-nc/4.0/
You might also like
Two-layer ensemble of deep learning models for medical image segmentation.
(2024)
Journal Article
DEFEG: deep ensemble with weighted feature generation.
(2023)
Journal Article
A comparative study of anomaly detection methods for gross error detection problems.
(2023)
Journal Article
Downloadable Citations
About OpenAIR@RGU
Administrator e-mail: publications@rgu.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2025
Advanced Search