Journal article

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

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

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY | TAYLOR & FRANCIS LTD | Published : 2019

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

View full abstract

University of Melbourne Researchers