Skip to main content

Research Repository

Advanced Search

Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem

Asta, Shahriar; Karapetyan, Daniel; Kheiri, Ahmed; Özcan, Ender; Parkes, Andrew J.

Authors

Shahriar Asta

Daniel Karapetyan

Ahmed Kheiri



Abstract

Multi-mode resource and precedence-constrained project scheduling is a well-known challenging real-world optimisation problem. An important variant of the problem requires scheduling of activities for multiple projects considering availability of local and global resources while respecting a range of constraints. A critical aspect of the benchmarks addressed in this paper is that the primary objective is to minimise the sum of the project completion times, with the usual makespan minimisation as a secondary objective. We observe that this leads to an expected different overall structure of good solutions and discuss the effects this has on the algorithm design. This paper presents a carefully-designed hybrid of Monte-Carlo tree search, novel neighbourhood moves, memetic algorithms, and hyper-heuristic methods. The implementation is also engineered to increase the speed with which iterations are performed, and to exploit the computing power of multicore machines. Empirical evaluation shows that the resulting information-sharing multi-component algorithm significantly outperforms other solvers on a set of “hidden” instances, i.e. instances not available at the algorithm design phase.

Citation

Asta, S., Karapetyan, D., Kheiri, A., Özcan, E., & Parkes, A. J. (2016). Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem. Information Sciences, 373, 476-498. https://doi.org/10.1016/j.ins.2016.09.010

Journal Article Type Article
Acceptance Date Sep 5, 2016
Online Publication Date Sep 7, 2016
Publication Date Dec 10, 2016
Deposit Date Sep 30, 2016
Publicly Available Date Sep 30, 2016
Journal Information Sciences
Print ISSN 0020-0255
Electronic ISSN 1872-6291
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 373
Pages 476-498
DOI https://doi.org/10.1016/j.ins.2016.09.010
Keywords Metaheuristics; Hybrid heuristics; Hyper-heuristics; Monte Carlo tree search; Permutation based local search; Multi-project scheduling
Public URL http://eprints.nottingham.ac.uk/id/eprint/37265
Publisher URL http://www.sciencedirect.com/science/article/pii/S0020025516307502
Copyright Statement Copyright information regarding this work can be found at the following address: http://creativecommons.org/licenses/by-nc-nd/4.0
Additional Information This article is maintained by: Elsevier; Article Title: Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem; Journal Title: Information Sciences; CrossRef DOI link to publisher maintained version: https://doi.org/10.1016/j.ins.2016.09.010; Content Type: article; Copyright: © 2016 Elsevier Inc. All rights reserved.

Files


1511.04387v2.pdf (448 Kb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://creativecommons.org/licenses/by-nc-nd/4.0





You might also like



Downloadable Citations