A VECTOR-SUM THEOREM AND ITS APPLICATION TO IMPROVING FLOW-SHOP GUARANTEES

被引：21

作者：

BARANY, I

机构：

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 1981年 / 6卷 / 03期

关键词：

D O I：

10.1287/moor.6.3.445

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The author proves that if a closed polygonal path in R**d consists of a finite number of line segments of at most unit length, then it is possible to transpose the segments in such a way that the new polygonal path is contained in a ball of radius left bracket 3/2 d right bracket . Using this result the author gives a near optimal algorithm for the NP-complete flow shop problem. The error of the algorithm cannot exceed a constant depending on the maximal execution time and the number of machines but not depending on the number of jobs. The author's theorems improve earlier results of the same type by I. S. Belov and J. I. Stolin.

引用

页码：445 / 452

页数：8