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