Preemptive job-shop scheduling problems with a fixed number of jobs

被引：0

作者：

Brucker, P ^{[1
]}

Kravchenko, SA

Sotskov, YN

机构：

[1] Univ Osnabruck, Fachbereich Math Informat, D-49069 Osnabruck, Germany

[2] Inst Engn Cybernet, Minsk 220012, BELARUS

来源：

MATHEMATICAL METHODS OF OPERATIONS RESEARCH | 1999年 / 49卷 / 01期

关键词：

job-shop problem; scheduling; NP-hard;

D O I：

暂无

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

It is shown that the two machine preemptive job-shop problem with mean flow-time or makespan objective function and three jobs is NP-hard. This contrasts the fact that the nonpreemptive versions of these problems are polynomially solvable if the number of jobs is arbitrary but fixed. It is also shown that the preemptive problems can be solved pseudopolynomially if both the number of machines and the number of jobs is fixed.

引用

页码：41 / 76

页数：36

共 16 条

[1] A POLYNOMIAL ALGORITHM FOR THE 2 MACHINE JOB-SHOP SCHEDULING PROBLEM WITH A FIXED NUMBER OF JOBS [J].

BRUCKER, P .

OR SPEKTRUM, 1994, 16 (01) :5-7

[2] On the complexity of two machine job-shop scheduling with regular objective functions [J].

Brucker P. ;

Kravchenko S.A. ;

Sotskov Y.N. .

Operations-Research-Spektrum, 1997, 19 (1) :5-10

[3] AN EFFICIENT ALGORITHM FOR THE JOB-SHOP PROBLEM WITH 2 JOBS [J].

BRUCKER, P .

COMPUTING, 1988, 40 (04) :353-359

[4]

Garey M. R., 1976, Mathematics of Operations Research, V1, P117, DOI 10.1287/moor.1.2.117

[5] FLOW-SHOP AND JOB-SHOP SCHEDULES - COMPLEXITY AND APPROXIMATION [J].

GONZALEZ, T ;

SAHNI, S .

OPERATIONS RESEARCH, 1978, 26 (01) :36-52

[6]

Jackson J.R., 1956, Naval Research Logistics Quarterly, V3, P201, DOI DOI 10.1002/NAV.3800030307

[7]

Kravchenko S. A., 1996, ZOR-Mathematical Methods of Operations Research, V43, P233

[8]

KRAVCHENKO SA, 1995, COMPLEXITY 2 MACHINE

[9]

KRAVCHENKO SA, 1995, N7 I ENG CYB

[10]

Lawler E., 1993, LOGISTICS PRODUCTION, DOI 10.1016/S0927-0507(05)80189-6

← 1 2 →