PERMUTATION VS NON-PERMUTATION FLOW-SHOP SCHEDULES

被引：62

作者：

POTTS, CN

SHMOYS, DB

WILLIAMSON, DP

机构：

[1] CORNELL UNIV,CTR ENGN & THEORY,ORIE,ITHACA,NY 14853

[2] MIT,COMP SCI LAB,CAMBRIDGE,MA 02139

来源：

OPERATIONS RESEARCH LETTERS | 1991年 / 10卷 / 05期

基金：

美国国家科学基金会;

关键词：

FLOWSHOP SCHEDULING; PERMUTATION SCHEDULES; APPROXIMATION ALGORITHMS;

D O I：

10.1016/0167-6377(91)90014-G

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In studying the m-machine flow shop scheduling problem, it is common practice to focus attention on permutation schedules. We show that for the problem of minimizing the maximum completion time, this assumption can be a costly one, by exhibiting a family of instances for which the value of the best permutation schedule is worse than that of the true optimal schedule by a factor of more than 1/2 square-root m.

引用

页码：281 / 284

页数：4