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

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.

Keywords:

• Symmetry breaking
• project scheduling
• RCPSP/max
• generalised precedence constraints
• high-multiplicity scheduling
• polyhedral analysis

Notes

1 The full data and results can be found as the following link: https://doi.org/10.26180/5bfb37e6250ab

Additional information

Funding

This research was supported by the Australian Research Council under grant LP140101063. This research was supported in part by the Monash eResearch Centre and eSolutions-Research Support Services through the use of the MonARCH HPC Cluster.