A POLYNOMIAL ALGORITHM FOR THE 2 MACHINE JOB-SHOP SCHEDULING PROBLEM WITH A FIXED NUMBER OF JOBS

被引：15

作者：

BRUCKER, P ^{[1
]}

机构：

[1] UNIV OSNABRUCK,FACHBEREICH MATH INFORMAT,D-49069 OSNABRUCK,GERMANY

来源：

OR SPEKTRUM | 1994年 / 16卷 / 01期

关键词：

2 MACHINE JOB-SHOP; POLYNOMIAL ALGORITHM;

D O I：

10.1007/BF01719698

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

It is shown that the job-shop problem with two machines and a fixed number of k jobs with makespan criterion J2\n = k\C(max) is polynomially solvable. Sotskov and Shakhlevich (1993) have shown that problem J3\n = 3\C(max) is NP-hard. Furthermore it is well known that J\n=2\C(max) in polynomially solvable. Thus, our result settles the remaining open question concerning the complexity status of job-shop problems with fixed numbers of jobs and machines.

引用

页码：5 / 7

页数：3