Symmetry breaking of identical projects in the high-multiplicity RCPSP/max

Steven J. Edwards, Davaatseren Baatar, Kate Smith-Miles and Andreas T. Ernst

Journal of the Operational Research Society, 2021, vol. 72, issue 8, 1822-1843

Abstract: This article considers the high-multiplicity resource-constrained project scheduling problem with generalised precedence constraints (RCPSP/max). Projects, which can be partitioned into relatively few classes, are to be scheduled subject to resource and generalised precedence constraints. We show that there exists symmetry between projects of the same class and propose two approaches of symmetry breaking: (1) adding additional constraints to the model in the form of precedence constraints, (2) remodelling the problem to reduce the number of variables. To test the usefulness of the symmetry breaking approaches a computational study is completed considering two families of discrete-time based MIP models and a number of state-of-the-art CP-based scheduling approaches. The study shows that both symmetry breaking approaches allow all solving methods to find and prove more optimal solutions. The best CP approach is then used to find a number of new best solutions to relevant problems from the MPSPlib, a multi-project scheduling problem library, for both the total makespan and average project delay objective, whereas the best MIP approach is used to determine a number of tighter lower bounds.

Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2019.1595192 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tjorxx:v:72:y:2021:i:8:p:1822-1843

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2019.1595192

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().