SHOP SCHEDULING PROBLEMS WITH MULTIPROCESSOR TASKS ON DEDICATED PROCESSORS

被引：24

作者：

BRUCKER, P ^{[1
]}

KRAMER, A ^{[1
]}

机构：

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

来源：

ANNALS OF OPERATIONS RESEARCH | 1995年 / 57卷

关键词：

D O I：

10.1007/BF02099688

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The computational complexity of shop scheduling problems with multiprocessor tasks on dedicated processors is investigated. The objective is makespan minimization. Preemption of tasks is not allowed. For open and flow-shop problems with three stages, complete classifications into polynomial solvable and NP-hard problems are given. These classifications depend on the compatibility structures of the problems. Furthermore, results for open-shop problems with unit processing times are derived. Finally, it is shown that most of the special cases of the job-shop problem which are polynomially solvable remain polynomially solvable in the multiprocessor task situation.

引用

页码：13 / 27

页数：15

共 23 条

[1]

BIANCO L, 1994, NAV RES LOG, V41, P959, DOI 10.1002/1520-6750(199412)41:7<959::AID-NAV3220410708>3.0.CO

[2]

2-K

[3] PREEMPTIVE SCHEDULING OF MULTIPROCESSOR TASKS ON THE DEDICATED PROCESSOR SYSTEM SUBJECT TO MINIMAL LATENESS [J].

BIANCO, L ;

BLAZEWICZ, J ;

DELLOLMO, P ;

DROZDOWSKI, M .

INFORMATION PROCESSING LETTERS, 1993, 46 (03) :109-113

[4]

BLAZEWICZ J, 1992, INFORM PROCESS LETT, V41, P275, DOI 10.1016/0020-0190(92)90172-R

[5]

Blazewicz J., 1993, SCHEDULING COMPUTER

[6] 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

[7]

Brucker P., 1993, ZOR, Methods and Models of Operations Research, V37, P59, DOI 10.1007/BF01415528

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

BRUCKER, P .

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

[9] ALGORITHMS FOR EDGE COLORING BIPARTITE GRAPHS AND MULTIGRAPHS [J].

GABOW, HN ;

KARIV, O .

SIAM JOURNAL ON COMPUTING, 1982, 11 (01) :117-129

[10]

Garey M.R., 1979, COMPUTERS INTRACTABI, V174

← 1 2 3 →