A very difficult scheduling problem with communication delays

Han Hoogeveen; Gerhard J. Woeginger

doi:10.1016/S0167-6377(01)00103-1

A very difficult scheduling problem with communication delays

Han Hoogeveen, Gerhard J. Woeginger^*

^*Corresponding author for this work

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

Abstract

A set of unit-time tasks has to be processed on an unrestricted number of processors subject to precedence constraints and unit-time communication delays such that the makespan is minimized. What is the smallest number m* such that increasing the number of processors beyond m* cannot decrease the makespan any more? We prove that answering this problem is complete for the complexity class FP^{NP[log n]}. Hence, the problem is at least as difficult as all the problems in NP and at least as difficult as all the problems in coNP, and unless some complexity classes collapse, it is even more difficult than all these problems. This answers a question raised by Ivan Rival.

Original language	English
Pages (from-to)	241-245
Number of pages	5
Journal	Operations Research Letters
Volume	29
Issue number	5
DOIs	https://doi.org/10.1016/S0167-6377(01)00103-1
Publication status	Published - Dec 2001

Keywords

Communication delays
Computational complexity
Makespan
Parallel computation
Precedence constraints
Scheduling

Access to Document

10.1016/S0167-6377(01)00103-1

Cite this

@article{0f8b6dca7a484f3e9d2831c6c60d0c1f,

title = "A very difficult scheduling problem with communication delays",

abstract = "A set of unit-time tasks has to be processed on an unrestricted number of processors subject to precedence constraints and unit-time communication delays such that the makespan is minimized. What is the smallest number m* such that increasing the number of processors beyond m* cannot decrease the makespan any more? We prove that answering this problem is complete for the complexity class FPNP[log n]. Hence, the problem is at least as difficult as all the problems in NP and at least as difficult as all the problems in coNP, and unless some complexity classes collapse, it is even more difficult than all these problems. This answers a question raised by Ivan Rival.",

keywords = "Communication delays, Computational complexity, Makespan, Parallel computation, Precedence constraints, Scheduling",

author = "Han Hoogeveen and Woeginger, {Gerhard J.}",

year = "2001",

month = dec,

doi = "10.1016/S0167-6377(01)00103-1",

language = "English",

volume = "29",

pages = "241--245",

journal = "Operations Research Letters",

publisher = "Elsevier BV",

number = "5",

}

TY - JOUR

T1 - A very difficult scheduling problem with communication delays

AU - Hoogeveen, Han

AU - Woeginger, Gerhard J.

PY - 2001/12

Y1 - 2001/12

N2 - A set of unit-time tasks has to be processed on an unrestricted number of processors subject to precedence constraints and unit-time communication delays such that the makespan is minimized. What is the smallest number m* such that increasing the number of processors beyond m* cannot decrease the makespan any more? We prove that answering this problem is complete for the complexity class FPNP[log n]. Hence, the problem is at least as difficult as all the problems in NP and at least as difficult as all the problems in coNP, and unless some complexity classes collapse, it is even more difficult than all these problems. This answers a question raised by Ivan Rival.

AB - A set of unit-time tasks has to be processed on an unrestricted number of processors subject to precedence constraints and unit-time communication delays such that the makespan is minimized. What is the smallest number m* such that increasing the number of processors beyond m* cannot decrease the makespan any more? We prove that answering this problem is complete for the complexity class FPNP[log n]. Hence, the problem is at least as difficult as all the problems in NP and at least as difficult as all the problems in coNP, and unless some complexity classes collapse, it is even more difficult than all these problems. This answers a question raised by Ivan Rival.

KW - Communication delays

KW - Computational complexity

KW - Makespan

KW - Parallel computation

KW - Precedence constraints

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=0035687841&partnerID=8YFLogxK

U2 - 10.1016/S0167-6377(01)00103-1

DO - 10.1016/S0167-6377(01)00103-1

M3 - Article

VL - 29

SP - 241

EP - 245

JO - Operations Research Letters

JF - Operations Research Letters

IS - 5

ER -

A very difficult scheduling problem with communication delays

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this