A compact reformulation of the two-stage robust resource-constrained project scheduling problem. (June 2021)

• Record Type: Journal Article
• Authors: Bold, Matthew; Goerigk, Marc
• Is Part Of: Computers & operations research. Volume 130(2021)
• Publication Date: 2021-06
• Subjects: Project scheduling -- Robust optimisation -- Resource constraints -- Budgeted uncertainty; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105232
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We consider a two-stage robust resource-constrained project scheduling problem. Activity durations are uncertain and lie in a budgeted uncertainty set. A new compact mixed-integer programming formulation for the problem is derived. In computational experiments we compare against the current best method. Our approach is easy to apply and solve 49% more instances given the same time. Abstract: This paper considers the resource-constrained project scheduling problem with uncertain activity durations. We assume that activity durations lie in a budgeted uncertainty set, and follow a robust two-stage approach, where a decision maker must resolve resource conflicts subject to the problem uncertainty, but can determine activity start times after the uncertain activity durations become known. We introduce a new reformulation of the second-stage problem, which enables us to derive a compact robust counterpart to the full two-stage adjustable robust optimisation problem. Computational experiments show that this compact robust counterpart can be solved using standard optimisation software significantly faster than the current state-of-the-art algorithm for solving this problem, reaching optimality for almost 50% more instances on the same benchmark set.