Home > Research > Publications & Outputs > Combining Monte-Carlo and hyper-heuristic metho...

Electronic data

  • MISTA2013

    Rights statement: This is the author’s version of a work that was accepted for publication in Information Sciences. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Information Sciences, 373, 2016 DOI: 10.1016/j.ins.2016.09.010

    Accepted author manuscript, 438 KB, PDF document

    Available under license: CC BY-NC-ND: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License

Links

Text available via DOI:

View graph of relations

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

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published

Standard

Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem. / Asta, Shahriar; Karapetyan, Daniel; Kheiri, Ahmed et al.
In: Information Sciences, Vol. 373, 10.12.2016, p. 476-498.

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Harvard

APA

Vancouver

Asta S, Karapetyan D, Kheiri A, Özcan E, Parkes AJ. Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem. Information Sciences. 2016 Dec 10;373:476-498. Epub 2016 Sept 7. doi: 10.1016/j.ins.2016.09.010

Author

Asta, Shahriar ; Karapetyan, Daniel ; Kheiri, Ahmed et al. / Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem. In: Information Sciences. 2016 ; Vol. 373. pp. 476-498.

Bibtex

@article{a5eb83b11027434794f5499c9fef2792,
title = "Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem",
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.",
keywords = "Hybrid heuristics, Hyper-heuristics, Metaheuristics, Monte Carlo tree search, Multi-project scheduling, Permutation based local search",
author = "Shahriar Asta and Daniel Karapetyan and Ahmed Kheiri and Ender {\"O}zcan and Parkes, {Andrew J.}",
note = "This is the author{\textquoteright}s version of a work that was accepted for publication in Information Sciences. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Information Sciences, 373, 2016 DOI: 10.1016/j.ins.2016.09.010",
year = "2016",
month = dec,
day = "10",
doi = "10.1016/j.ins.2016.09.010",
language = "English",
volume = "373",
pages = "476--498",
journal = "Information Sciences",
issn = "0020-0255",
publisher = "Elsevier Inc.",

}

RIS

TY - JOUR

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

AU - Asta, Shahriar

AU - Karapetyan, Daniel

AU - Kheiri, Ahmed

AU - Özcan, Ender

AU - Parkes, Andrew J.

N1 - This is the author’s version of a work that was accepted for publication in Information Sciences. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Information Sciences, 373, 2016 DOI: 10.1016/j.ins.2016.09.010

PY - 2016/12/10

Y1 - 2016/12/10

N2 - 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.

AB - 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.

KW - Hybrid heuristics

KW - Hyper-heuristics

KW - Metaheuristics

KW - Monte Carlo tree search

KW - Multi-project scheduling

KW - Permutation based local search

U2 - 10.1016/j.ins.2016.09.010

DO - 10.1016/j.ins.2016.09.010

M3 - Journal article

AN - SCOPUS:84987861878

VL - 373

SP - 476

EP - 498

JO - Information Sciences

JF - Information Sciences

SN - 0020-0255

ER -