Title: An automatic algorithm selection approach for the multi-mode resource-constrained project scheduling problem
Authors: Messelis, Tommy ×
De Causmaecker, Patrick #
Issue Date: Mar-2014
Publisher: Elsevier
Series Title: European Journal of Operational Research vol:233 pages:511-528
Abstract: This paper investigates the construction of an automatic algorithm selection tool for the multi-mode resource- constrained project scheduling problem (MRCPSP). The research described relies on the notion of empirical hardness models. These models map problem instance features onto the performance of an algorithm. Using such models, the performance of a set of algorithms can be predicted. Based on these predictions, one can automatically select the algorithm that is expected to perform best given the available computing resources. The idea is to combine different algorithms in a super-algorithm that performs better than any of the components individually. We apply this strategy to the classic problem of project scheduling with multiple execution modes. We show that we can indeed significantly improve on the performance of state-of-the-art algorithms when evaluated on a set of unseen instances. This becomes important when lots of instances have to be solved consecutively. Many state-of-the-art algorithms perform very well on a majority of benchmark instances, while performing worse on a smaller set of instances. The performance of one algorithm can be very different on a set of instances while another algorithm sees no difference in performance at all. Knowing in advance, without using scarce computational resources, which algorithm to run on a certain problem instance, can significantly improve the total overall performance.
ISSN: 0377-2217
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Computer Science, Campus Kulak Kortrijk
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
FinalPrePrint.pdf Published 1096KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science