COMPLEXITY OF SCHEDULING MULTIPROCESSOR TASKS WITH PRESPECIFIED PROCESSOR ALLOCATIONS

被引：99

作者：

HOOGEVEEN, JA

VANDEVELDE, SL

VELTMAN, B

机构：

[1] CWI,POB 4079,1009 AB AMSTERDAM,NETHERLANDS

[2] TWENTE UNIV TECHNOL,SCH MANAGEMENT STUDIES TECHNOL & INNOVATION,7500 AE ENSCHEDE,NETHERLANDS

[3] TWENTE UNIV TECHNOL,DEPT MATH & COMP SCI,7500 AE ENSCHEDE,NETHERLANDS

来源：

DISCRETE APPLIED MATHEMATICS | 1994年 / 55卷 / 03期

关键词：

MULTIPROCESSOR TASKS; PRESPECIFIED PROCESSOR ALLOCATIONS; MAKESPAN; TOTAL COMPLETION TIME; RELEASE DATES; PRECEDENCE CONSTRAINTS;

D O I：

10.1016/0166-218X(94)90012-4

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We investigate the computational complexity of scheduling multiprocessor tasks with prespecified processor allocations. We consider two criteria: minimizing schedule length and minimizing the sum of the task completion times. In addition, we investigate the complexity of problems when precedence constraints or release dates are involved.

引用

页码：259 / 272

页数：14

共 13 条

[1]

BIANCO L, 1991, 14TH INT S MATH PROG

[2] SCHEDULING SUBJECT TO RESOURCE CONSTRAINTS - CLASSIFICATION AND COMPLEXITY [J].