Complexity of scheduling multiprocessor tasks with prespecified processor allocations

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

Research output: Contribution to journalArticleAcademicpeer-review

109 Citations (Scopus)
27 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 languageEnglish
Pages (from-to)259-272
JournalDiscrete applied mathematics
Volume55
Issue number3
DOIs
Publication statusPublished - 1995

Fingerprint

Multiprocessor Scheduling
Computational complexity
Scheduling
Release Dates
Precedence Constraints
Completion Time
Computational Complexity
Schedule

Keywords

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

Cite this

Hoogeveen, J.A. ; van de Velde, S.L. ; Veltman, B. / Complexity of scheduling multiprocessor tasks with prespecified processor allocations. In: Discrete applied mathematics. 1995 ; Vol. 55, No. 3. pp. 259-272.
@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",

}

Complexity of scheduling multiprocessor tasks with prespecified processor allocations. / Hoogeveen, J.A.; van de Velde, S.L.; Veltman, B.

In: Discrete applied mathematics, Vol. 55, No. 3, 1995, p. 259-272.

Research output: Contribution to journalArticleAcademicpeer-review

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

VL - 55

SP - 259

EP - 272

JO - Discrete applied mathematics

JF - Discrete applied mathematics

SN - 0166-218X

IS - 3

ER -