NEW RESULTS IN THE WORST-CASE ANALYSIS FOR FLOWSHOP SCHEDULING

被引：18

作者：

NOWICKI, E

SMUTNICKI, C

机构：

[1] Technical University of Wrocław, Institute of Engineering Cybernetics, 50-372 Wrocław

来源：

DISCRETE APPLIED MATHEMATICS | 1993年 / 46卷 / 01期

关键词：

SCHEDULING; HEURISTICS; WORST-CASE ANALYSIS;

D O I：

10.1016/0166-218X(93)90156-I

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The worst-case analysis of the approximation algorithm proposed by Palmer and the algorithm RAES (the best of algorithms proposed by Dannenbring) for m-machine permutation flow-shop problem are presented. The worst-case performance ratios equal approximately m/square-root 2 for each of the algorithms are found. An evaluation of the worst-case performance ratio of Nawaz's et al. algorithm N is shown. Proposed are a few modifications improving the speed of the algorithms RAES and N.

引用

页码：21 / 41

页数：21

共 17 条

[1] A VECTOR-SUM THEOREM AND ITS APPLICATION TO IMPROVING FLOW-SHOP GUARANTEES [J].