On the robust single machine scheduling problem

被引：99

作者：

Yang, J ^{[1
]}

Yu, G

机构：

[1] New Jersey Inst Technol, Dept Ind & Mfg Engn, Newark, NJ 07102 USA

[2] Univ Texas, Dept Management Sci & Informat Syst, Austin, TX 78712 USA

[3] Univ Texas, Ctr Management Operat & Logist, Austin, TX 78712 USA

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2002年 / 6卷 / 01期

关键词：

robust optimization; machine scheduling; NP-completeness; heuristic;

D O I：

10.1023/A:1013333232691

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The single machine scheduling problem with sum of completion times criterion (SS) can be solved easily by the Shortest Processing Time (SPT) rule. In the case of significant uncertainty of the processing times, a robustness approach is appropriate. In this paper, we show that the robust version of the (SS) problem is NP-complete even for very restricted cases. We present an algorithm for finding optimal solutions for the robust (SS) problem using dynamic programming. We also provide two polynomial time heuristics and demonstrate their effectiveness.

引用

页码：17 / 33

页数：17

共 23 条

[1]

AGRAWALA AK, 1984, IEEE T COMPUT, V33, P351, DOI 10.1109/TC.1984.1676440

[2] 2-MACHINE ORDERED FLOWSHOP SCHEDULING UNDER RANDOM BREAKDOWNS [J].

ALLAHVERDI, A ;

MITTENTHAL, J .

MATHEMATICAL AND COMPUTER MODELLING, 1994, 20 (02) :9-17

[3]

ALLAHVERDI A, 1994, NAV RES LOG, V41, P677, DOI 10.1002/1520-6750(199408)41:5<677::AID-NAV3220410509>3.0.CO

[4]

2-7

[5] SCHEDULING ON A 2-MACHINE FLOWSHOP SUBJECT TO RANDOM BREAKDOWNS WITH A MAKESPAN OBJECTIVE FUNCTION [J].

ALLAHVERDI, A ;

MITTENTHAL, J .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1995, 81 (02) :376-387

[6]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[7]

BIRGE J, 1990, NAV RES LOG, V37, P661, DOI 10.1002/1520-6750(199010)37:5<661::AID-NAV3220370506>3.0.CO

[8]

2-3

[9] ASSESSING THE EFFECTS OF MACHINE BREAKDOWNS IN STOCHASTIC SCHEDULING [J].

BIRGE, JR ;

GLAZEBROOK, KD .

OPERATIONS RESEARCH LETTERS, 1988, 7 (06) :267-271

[10] ROBUST SCHEDULING TO HEDGE AGAINST PROCESSING TIME UNCERTAINTY IN SINGLE-STAGE PRODUCTION [J].

DANIELS, RL ;

KOUVELIS, P .

MANAGEMENT SCIENCE, 1995, 41 (02) :363-376

← 1 2 3 →