2021/06/22 by Pascale Bendotti, Bendotti, Pascale, Philippe Chrétienne +5
Decision Sciences · Engineering · #Construction Project Management and Performance #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Resource-Constrained Project Scheduling #Risk and Portfolio Optimization #Scheduling and Optimization Algorithms #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2106.12055
openalex publication_date 2021/06/22 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
In project scheduling under processing times uncertainty, the Anchor-Robust\nProject Scheduling Problem is to find a baseline schedule of bounded makespan\nand a max-weight subset of jobs whose starting times are guaranteed. The\nproblem was proven NP-hard even for budgeted uncertainty. In the present work\nwe design mixed-integer programming (MIP) formulations that are valid for a\nvariety of uncertainty sets encompassing budgeted uncertainty. A new dominance\namong solutions is proposed, resulting into an MIP formulation. We further\nstudy the combinatorial structure of the problem. Non-trivial polynomial cases\nunder budgeted uncertainty are exhibited, where the dominance-based formulation\nyields a polyhedral characterization of integer solutions. In more general\ncases, the dominance-based formulation is shown to be tighter than all\npreviously known formulations. In numerical experiments we investigate how the\nformulation performs on instances around the polynomial cases, for both\nbudgeted uncertainty sets and more elaborate uncertainty sets involving several\nbudgets.\n