COMPLEXITY OF SCHEDULING MULTIPROCESSOR TASKS WITH PRESPECIFIED PROCESSOR ALLOCATIONS

Authors
HOOGEVEEN JA VANDEVELDE SL VELTMAN B
Citation
Ja. Hoogeveen et al., COMPLEXITY OF SCHEDULING MULTIPROCESSOR TASKS WITH PRESPECIFIED PROCESSOR ALLOCATIONS, Discrete applied mathematics, 55(3), 1994, pp. 259-272
Citations number
13
Categorie Soggetti
Mathematics,Mathematics
Journal title
Discrete applied mathematics → ACNP
Volume
55
Issue
3
Year of publication
1994
Pages
259 - 272
Database
ISI
SICI code
Abstract
We investigate the computational complexity of scheduling multiprocess or tasks with prespecified processor allocations. We consider two crit eria: minimizing schedule length and minimizing the sum of the task co mpletion times. In addition, we investigate the complexity of problems when precedence constraints or release dates are involved.