A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion

被引：47

作者：

Kasperski, Adam ^{[1
]}

Zielinski, Pawel ^{[2
]}

机构：

[1] Wroclaw Univ Technol, Inst Ind Engn & Management, PL-50370 Wroclaw, Poland

[2] Wroclaw Univ Technol, Inst Math & Comp Sci, PL-50370 Wroclaw, Poland

来源：

OPERATIONS RESEARCH LETTERS | 2008年 / 36卷 / 03期

关键词：

scheduling; interval data; minmax regret; approximation algorithm;

D O I：

10.1016/j.orl.2007.11.004

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper we discuss a minmax regret version of the single-machine scheduling problem with the total flow time criterion. Uncertain processing times are modeled by closed intervals. We show that if the deterministic problem is polynomially solvable, then its minmax regret version is approximable within 2. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：343 / 344

页数：2

共 9 条

[1] BRUCKER P, 1998, SCHEDULING ALGORITHM
[2] ROBUST SCHEDULING TO HEDGE AGAINST PROCESSING TIME UNCERTAINTY IN SINGLE-STAGE PRODUCTION
DANIELS, RL
KOUVELIS, P
[J]. MANAGEMENT SCIENCE, 1995, 41 (02) : 363 - 376
[3] An approximation algorithm for interval data minmax regret combinatorial optimization problems
Kasperski, A
Zielinski, P
[J]. INFORMATION PROCESSING LETTERS, 2006, 97 (05) : 177 - 180
[4] Kouvelis P., 1997, ROBUST DISCRETE OPTI
[5] Lawler E.L., 1978, Annals of Discrete Mathematics, V2, P75
[6] Complexity of minimizing the total flow time with interval data and minmax regret criterion
Lebedev, Vasilij
Averbakh, Igor
[J]. DISCRETE APPLIED MATHEMATICS, 2006, 154 (15) : 2167 - 2177
[7] COMPLEXITY OF SCHEDULING UNDER PRECEDENCE CONSTRAINTS
LENSTRA, JK
RINNOOYKAN, AHG
[J]. OPERATIONS RESEARCH, 1978, 26 (01) : 22 - 35
[8] MONTEMANNI R, 2006, J MATH MODELL ALGORI, V6, P287
[9] Smith W., 1956, Naval Res. Logistics Q., V3, P59, DOI [10.1002/nav.3800030106, DOI 10.1002/NAV.3800030106]

← 1 →