Complexity of scheduling multiprocessor tasks with prespecified processor allocations

J.A. Hoogeveen; S.L. van de Velde; B. Veltman

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

Complexity of scheduling multiprocessor tasks with prespecified processor allocations

J.A. Hoogeveen, S.L. van de Velde, B. Veltman

Research output: Contribution to journal › Article › Academic › peer-review

128 Citations (Scopus)

77 Downloads (Pure)

Abstract

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.

Original language	English
Pages (from-to)	259-272
Journal	Discrete applied mathematics
Volume	55
Issue number	3
DOIs	https://doi.org/10.1016/0166-218X(94)90012-4
Publication status	Published - 1995

Keywords

Multiprocessor tasks
Prespecified processor allocations
Makespan
Total completion time
Release dates
Precedence constraints

Access to Document

10.1016/0166-218X(94)90012-4Licence: Other

Hoogeveen94complexityFinal published version, 919 KBLicence: Other

Cite this

@article{c5cfefe487524c55a556ad78bad4176c,

title = "Complexity of scheduling multiprocessor tasks with prespecified processor allocations",

abstract = "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.",

keywords = "Multiprocessor tasks, Prespecified processor allocations, Makespan, Total completion time, Release dates, Precedence constraints",

author = "J.A. Hoogeveen and {van de Velde}, S.L. and B. Veltman",

year = "1995",

doi = "10.1016/0166-218X(94)90012-4",

language = "English",

volume = "55",

pages = "259--272",

journal = "Discrete applied mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Complexity of scheduling multiprocessor tasks with prespecified processor allocations

AU - Hoogeveen, J.A.

AU - van de Velde, S.L.

AU - Veltman, B.

PY - 1995

Y1 - 1995

N2 - 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.

AB - 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.

KW - Multiprocessor tasks

KW - Prespecified processor allocations

KW - Makespan

KW - Total completion time

KW - Release dates

KW - Precedence constraints

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

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

M3 - Article

SN - 0166-218X

VL - 55

SP - 259

EP - 272

JO - Discrete applied mathematics

JF - Discrete applied mathematics

IS - 3

ER -