Investigating the recoverable robust single machine scheduling problem under interval uncertainty

被引：7
作者：
Bold, Matthew [1 ]
Goerigk, Marc [2 ]
机构：
[1] Univ Lancaster, STOR I Ctr Doctoral Training, Lancaster, England
[2] Univ Siegen, Network & Data Sci Management, Siegen, Germany
来源：
DISCRETE APPLIED MATHEMATICS | 2022年 / 313卷
基金：
英国工程与自然科学研究理事会;
关键词：
Scheduling; Optimisation under uncertainty; Recoverable robustness; j is an element of N; TOTAL FLOW TIME; COMPLEXITY;
D O I：
10.1016/j.dam.2022.02.005
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We investigate the recoverable robust single machine scheduling problem under interval uncertainty. In this setting, jobs have first-stage processing times p and second-stage processing times q and we aim to find a first-stage and second-stage schedule with a minimum combined sum of completion times, such that at least jobs share the same position in both schedules. We provide positive complexity results for some important special cases of this problem, as well as derive a 2-approximation algorithm to the full problem. Computational experiments examine the performance of an exact mixed-integer programming formulation and the approximation algorithm, and demonstrate the strength of a proposed polynomial time greedy heuristic. (c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
引用
收藏
页码：99 / 114
页数：16
相关论文
共 26 条
[1]   Complexity of single machine scheduling problems under scenario-based uncertainty [J].
Aloulou, Mohamed Ali ;
Della Croce, Federico .
OPERATIONS RESEARCH LETTERS, 2008, 36 (03) :338-342
[2]  
Bold M., 2020, ARXIV PREPRINT ARXIV
[3]   Robust scheduling with budgeted uncertainty [J].
Bougeret, Marin ;
Pessoa, Artur Alves ;
Poss, Michael .
DISCRETE APPLIED MATHEMATICS, 2019, 261 :93-107
[4]   Recoverable robust shortest path problems [J].
Buesing, Christina .
NETWORKS, 2012, 59 (01) :181-189
[5]   ROBUST SCHEDULING TO HEDGE AGAINST PROCESSING TIME UNCERTAINTY IN SINGLE-STAGE PRODUCTION [J].
DANIELS, RL ;
KOUVELIS, P .
MANAGEMENT SCIENCE, 1995, 41 (02) :363-376
[6]   A family of inequalities valid for the robust single machine scheduling polyhedron [J].
de Farias, Ismael Regis, Jr. ;
Zhao, Hongxia ;
Zhao, Ming .
COMPUTERS & OPERATIONS RESEARCH, 2010, 37 (09) :1610-1614
[7]   On the robust assignment problem under a fixed number of cost scenarios [J].
Deineko, VG ;
Woeginger, GJ .
OPERATIONS RESEARCH LETTERS, 2006, 34 (02) :175-179
[8]  
Fischer D., 2020, ARXIV PREPRINT ARXIV
[9]  
Goerigk M., 2021, ARXIV PREPRINT ARXIV
[10]  
Graham R. L., 1979, Discrete Optimisation, P287
123