Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem
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 o...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Published: |
Elsevier
2016
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/37265/ |
| _version_ | 1848795423304581120 |
|---|---|
| author | Asta, Shahriar Karapetyan, Daniel Kheiri, Ahmed Özcan, Ender Parkes, Andrew J. |
| author_facet | Asta, Shahriar Karapetyan, Daniel Kheiri, Ahmed Özcan, Ender Parkes, Andrew J. |
| author_sort | Asta, Shahriar |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T19:31:51Z |
| format | Article |
| id | nottingham-37265 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:31:51Z |
| publishDate | 2016 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-372652020-05-04T18:26:42Z https://eprints.nottingham.ac.uk/37265/ 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. 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. Elsevier 2016-12-10 Article PeerReviewed Asta, Shahriar, Karapetyan, Daniel, Kheiri, Ahmed, Özcan, Ender and Parkes, Andrew J. (2016) Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem. Information Sciences, 373 . pp. 476-498. ISSN 1872-6291 Metaheuristics; Hybrid heuristics; Hyper-heuristics; Monte Carlo tree search; Permutation based local search; Multi-project scheduling http://www.sciencedirect.com/science/article/pii/S0020025516307502 doi:10.1016/j.ins.2016.09.010 doi:10.1016/j.ins.2016.09.010 |
| spellingShingle | Metaheuristics; Hybrid heuristics; Hyper-heuristics; Monte Carlo tree search; Permutation based local search; Multi-project scheduling Asta, Shahriar Karapetyan, Daniel Kheiri, Ahmed Özcan, Ender Parkes, Andrew J. Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem |
| title | Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem |
| title_full | Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem |
| title_fullStr | Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem |
| title_full_unstemmed | Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem |
| title_short | Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem |
| title_sort | combining monte-carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem |
| topic | Metaheuristics; Hybrid heuristics; Hyper-heuristics; Monte Carlo tree search; Permutation based local search; Multi-project scheduling |
| url | https://eprints.nottingham.ac.uk/37265/ https://eprints.nottingham.ac.uk/37265/ https://eprints.nottingham.ac.uk/37265/ |