The Anchor-Robust Project Scheduling Problem

Pascale Bendotti (), Philippe Chrétienne (), Pierre Fouilhoux () and Adèle Pass-Lanneau ()
Additional contact information
Pascale Bendotti: OSIRIS Department, Electricité de France Recherche & Développement, 91120 Palaiseau, France; Centre National de la Recherche Scientifique, Operations Research Team, Laboratoire d’Informatique de Paris 6, Sorbonne Université, 75005 Paris, France
Philippe Chrétienne: Centre National de la Recherche Scientifique, Operations Research Team, Laboratoire d’Informatique de Paris 6, Sorbonne Université, 75005 Paris, France
Pierre Fouilhoux: Centre National de la Recherche Scientifique, Operations Research Team, Laboratoire d’Informatique de Paris 6, Sorbonne Université, 75005 Paris, France
Adèle Pass-Lanneau: OSIRIS Department, Electricité de France Recherche & Développement, 91120 Palaiseau, France; Centre National de la Recherche Scientifique, Operations Research Team, Laboratoire d’Informatique de Paris 6, Sorbonne Université, 75005 Paris, France

Operations Research, 2023, vol. 71, issue 6, 2267-2290

Abstract: In project scheduling with uncertain processing times, the decision maker often needs to compute a baseline schedule in advance while guaranteeing that some jobs will not be rescheduled later. Standard robust approaches either produce a schedule with a very large makespan or offer no guarantee on starting times of the jobs. The concept of anchor-robustness is introduced as a middle ground between these approaches. A subset of jobs is said to be anchored if the starting times of its jobs in the baseline schedule can be guaranteed. The Anchor-Robust Project Scheduling Problem (AnchRobPSP) is proposed as a robust two-stage problem to find a baseline schedule of bounded makespan and a max-weight subset of anchored jobs. AnchRobPSP is considered for several uncertainty sets, such as box or budgeted uncertainty sets. Dedicated graph models are presented. In particular, the existence of a compact mixed integer programming reformulation for budgeted uncertainty is proven. AnchRobPSP is shown to be NP-hard even for budgeted uncertainty. Polynomial and pseudopolynomial algorithms are devised for box uncertainty and special cases of budgeted uncertainty. According to numerical results, the proposed approaches solve large-scale instances and outperform classical affine decisions rules for AnchRobPSP. Insights on the price of anchor-robustness are given based on computations.

Keywords: Optimization; project scheduling; robust optimization; rescheduling; anchored decisions (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2315 (application/pdf)

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:inm:oropre:v:71:y:2023:i:6:p:2267-2290

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().