The Anchor-Robust Project Scheduling Problem

• 成果类型: Article
• 署名作者: Bendotti, Pascale; Chretienne, Philippe; Fouilhoux, Pierre; Pass-Lanneau, Adele
• 署名单位: Electricite de France (EDF); Centre National de la Recherche Scientifique (CNRS); Sorbonne Universite
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2315
• 发表日期: 2023
• 关键词: uncertainty

摘要

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