An automatic algorithm selection approach for the multi-mode resource-constrained project scheduling problem

Tommy Messelis

doi:10.1016/j.ejor.2013.08.021

2014-03-01

Tommy Messelis *

Patrick De Causmaecker

DOI：10.1016/j.ejor.2013.08.021

原文链接

查看原文

摘要

En 中文

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. (C) 2013 Elsevier B.V. All rights reserved.

Keyword:

Decision support systems

Combinatorial optimisation

Performance prediction

Project scheduling

Algorithm portfolio

Automatic algorithm selection