Complexity of single machine scheduling problems under scenario-based uncertainty

被引:62
作者
Aloulou, Mohamed Ali [1 ]
Della Croce, Federico [2 ]
机构
[1] Univ Paris 09, LAMSADE, F-75775 Paris 16, France
[2] Politecn Turin, DAI, Turin, Italy
关键词
scheduling; scenario-based uncertainty; absolute robustness;
D O I
10.1016/j.orl.2007.11.005
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
We present algorithmic and computational complexity results for several single machine scheduling problems where some job characteristics are uncertain. This uncertainty is modeled through a finite set of well-defined scenarios. We use here the so-called absolute robustness criterion to select among feasible solutions. (C) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码:338 / 342
页数:5
相关论文
共 10 条
[1]   Minmax regret solutions for minimax optimization problems with uncertainty [J].
Averbakh, I .
OPERATIONS RESEARCH LETTERS, 2000, 27 (02) :57-65
[2]   ROBUST SCHEDULING TO HEDGE AGAINST PROCESSING TIME UNCERTAINTY IN SINGLE-STAGE PRODUCTION [J].
DANIELS, RL ;
KOUVELIS, P .
MANAGEMENT SCIENCE, 1995, 41 (02) :363-376
[3]  
Garey MR, 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[4]  
Graham R. L., 1979, Discrete Optimisation, P287
[5]   Minimizing maximal regret in the single machine sequencing problem with maximum lateness criterion [J].
Kasperski, A .
OPERATIONS RESEARCH LETTERS, 2005, 33 (04) :431-436
[6]   Robust scheduling of a two-machine flow shop with uncertain processing times [J].
Kouvelis, P ;
Daniels, RL ;
Vairaktarakis, G .
IIE TRANSACTIONS, 2000, 32 (05) :421-432
[7]  
Kouvelis P., 1997, ROBUST DISCRETE OPTI
[8]   OPTIMAL SEQUENCING OF A SINGLE MACHINE SUBJECT TO PRECEDENCE CONSTRAINTS [J].
LAWLER, EL .
MANAGEMENT SCIENCE SERIES A-THEORY, 1973, 19 (05) :544-546
[9]   N JOB, ONE MACHINE SEQUENCING ALGORITHM FOR MINIMIZING THE NUMBER OF LATE JOBS [J].
MOORE, JM .
MANAGEMENT SCIENCE, 1968, 15 (01) :102-109
[10]   On the robust single machine scheduling problem [J].
Yang, J ;
Yu, G .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2002, 6 (01) :17-33