Single machine robust scheduling with budgeted uncertainty

被引：5

作者：

Bougeret, Marin ^{[1
]}

Pessoa, Artur ^{[2
]}

Poss, Michael ^{[1
]}

机构：

[1] Univ Montpellier, LIRMM, CNRS, Rue Ada 156, F-34095 Montpellier, France

[2] Univ Fed Fluminense, Prod Engn Dept, Rua Passo Patria 156,309-D, BR-24210240 Niteroi, Brazil

来源：

OPERATIONS RESEARCH LETTERS | 2023年 / 51卷 / 02期

关键词：

Robust scheduling; NP-hardness; Approximation algorithms; OPTIMIZATION; COMPLEXITY; ALGORITHM; JOB;

D O I：

10.1016/j.orl.2023.01.007

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider robust single machine scheduling problems. First, we prove that with uncertain processing times, minimizing the number of tardy jobs is NP-hard. Second, we show that the weighted variant of the problem has the same complexity as the nominal counterpart whenever only the weights are uncertain. Last, we provide approximation algorithms for the problems minimizing the weighted sum of completion times. Noticeably, our algorithms extend to more general robust combinatorial optimization problems with cost uncertainty, such as max-cut.(c) 2023 Elsevier B.V. All rights reserved.

引用

页码：137 / 141

页数：5

共 16 条

[1] Complexity of single machine scheduling problems under scenario-based uncertainty [J].