THE 3-MACHINE NO-WAIT FLOWSHOP IS NP-COMPLETE

被引：165

作者：

ROCK, H

机构：

来源：

JOURNAL OF THE ACM | 1984年 / 31卷 / 02期

关键词：

D O I：

10.1145/62.65

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

引用

页码：336 / 345

页数：10

共 18 条

[1] SCHEDULING IN A SEMI-ORDERED FLOWSHOP WITHOUT INTERMEDIATE QUEUES [J].

ARORA, RK ;

RANA, SP .

AIIE TRANSACTIONS, 1980, 12 (03) :263-272

[2]

Garey M. R., 1976, SIAM Journal on Computing, V5, P704, DOI 10.1137/0205049

[3]

Garey Michael R., 1979, COMPUTERS INTRACTABI

[4] SEQUENCING 1 STATE-VARIABLE MACHINE - SOLVABLE CASE OF TRAVELING SALESMAN PROBLEM [J].

GILMORE, PC ;

GOMORY, RE .

OPERATIONS RESEARCH, 1964, 12 (05) :655-&

[5] UNIT EXECUTION TIME SHOP PROBLEMS [J].

GONZALEZ, T .

MATHEMATICS OF OPERATIONS RESEARCH, 1982, 7 (01) :57-66

[6] LOCAL SEARCH FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM [J].

KANELLAKIS, PC ;

PAPADIMITRIOU, CH .

OPERATIONS RESEARCH, 1980, 28 (05) :1086-1099

[7]

Karp R.M., 1972, COMPLEXITY COMPUTER

[8]

Lenstra J.K., 1977, ANN DISCRETE MATH, V1, P343, DOI [/10.1016/S0167-5060(08)70743-X, DOI 10.1016/S0167-5060(08)70743-X, 10.1016/S0167-5060(08)70743-X]

[9] ORDERED FLOW-SHOP PROBLEMS WITH NO IN-PROCESS WAITING - FURTHER RESULTS [J].

PANWALKAR, SS ;

WOOLLAM, CR .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1980, 31 (11) :1039-1043

[10] FLOWSHOP SCHEDULING WITH LIMITED TEMPORARY-STORAGE [J].

PAPADIMITRIOU, CH ;

KANELLAKIS, PC .

JOURNAL OF THE ACM, 1980, 27 (03) :533-549

← 1 2 →