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