On the complexity of scheduling incompatible jobs with unit-times: Mathematical Foundations of Computer Science 1993

Hans Bodlaender; Klaus Jansen

doi:10.1007/3-540-57182-5_21

On the complexity of scheduling incompatible jobs with unit-times: Mathematical Foundations of Computer Science 1993

Hans Bodlaender, Klaus Jansen

Decision Support Systems

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

Abstract

We consider scheduling problems in a multiprocessor system with incompatible jobs of unit-time length where two incompatible jobs can not be processed on the same machine. Given a deadline κ′ and a number of κ machines, the problem is to find a feasible assignment of the jobs to the machines. We prove the computational complexity of this scheduling problem restricted to different graph classes, arbitrary and constant numbers κ and κ′.

Original language	English
Title of host publication	Mathematical Foundations of Computer Science 1993
Subtitle of host publication	18th International Symposium, MFCS'93 Gdańsk, Poland, August 30–September 3, 1993 Proceedings
Editors	Andrzej M. Borzyszkowski, Stefan Sokołowski
Publisher	Springer
Pages	291-300
Number of pages	10
Volume	711
ISBN (Electronic)	978-3-540-47927-7
ISBN (Print)	978-3-540-57182-7
DOIs	https://doi.org/10.1007/3-540-57182-5_21
Publication status	Published - 1993

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer

Access to Document

10.1007/3-540-57182-5_21

http://dx.doi.org/10.1007/3-540-57182-5_21

Cite this

Bodlaender, H., & Jansen, K. (1993). On the complexity of scheduling incompatible jobs with unit-times: Mathematical Foundations of Computer Science 1993. In A. M. Borzyszkowski, & S. Sokołowski (Eds.), Mathematical Foundations of Computer Science 1993: 18th International Symposium, MFCS'93 Gdańsk, Poland, August 30–September 3, 1993 Proceedings (Vol. 711, pp. 291-300). (Lecture Notes in Computer Science). Springer. https://doi.org/10.1007/3-540-57182-5_21

Bodlaender, Hans ; Jansen, Klaus. / On the complexity of scheduling incompatible jobs with unit-times : Mathematical Foundations of Computer Science 1993. Mathematical Foundations of Computer Science 1993: 18th International Symposium, MFCS'93 Gdańsk, Poland, August 30–September 3, 1993 Proceedings. editor / Andrzej M. Borzyszkowski ; Stefan Sokołowski. Vol. 711 Springer, 1993. pp. 291-300 (Lecture Notes in Computer Science).

@inbook{1e17efb34cb74b789882c9aaae056a83,

title = "On the complexity of scheduling incompatible jobs with unit-times: Mathematical Foundations of Computer Science 1993",

abstract = "We consider scheduling problems in a multiprocessor system with incompatible jobs of unit-time length where two incompatible jobs can not be processed on the same machine. Given a deadline κ′ and a number of κ machines, the problem is to find a feasible assignment of the jobs to the machines. We prove the computational complexity of this scheduling problem restricted to different graph classes, arbitrary and constant numbers κ and κ′.",

author = "Hans Bodlaender and Klaus Jansen",

year = "1993",

doi = "10.1007/3-540-57182-5_21",

language = "English",

isbn = "978-3-540-57182-7",

volume = "711",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "291--300",

editor = "Borzyszkowski, {Andrzej M.} and Stefan Soko{\l}owski",

booktitle = "Mathematical Foundations of Computer Science 1993",

}

Bodlaender, H & Jansen, K 1993, On the complexity of scheduling incompatible jobs with unit-times: Mathematical Foundations of Computer Science 1993. in AM Borzyszkowski & S Sokołowski (eds), Mathematical Foundations of Computer Science 1993: 18th International Symposium, MFCS'93 Gdańsk, Poland, August 30–September 3, 1993 Proceedings. vol. 711, Lecture Notes in Computer Science, Springer, pp. 291-300. https://doi.org/10.1007/3-540-57182-5_21

On the complexity of scheduling incompatible jobs with unit-times: Mathematical Foundations of Computer Science 1993. / Bodlaender, Hans; Jansen, Klaus.
Mathematical Foundations of Computer Science 1993: 18th International Symposium, MFCS'93 Gdańsk, Poland, August 30–September 3, 1993 Proceedings. ed. / Andrzej M. Borzyszkowski; Stefan Sokołowski. Vol. 711 Springer, 1993. p. 291-300 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - On the complexity of scheduling incompatible jobs with unit-times

T2 - Mathematical Foundations of Computer Science 1993

AU - Bodlaender, Hans

AU - Jansen, Klaus

PY - 1993

Y1 - 1993

N2 - We consider scheduling problems in a multiprocessor system with incompatible jobs of unit-time length where two incompatible jobs can not be processed on the same machine. Given a deadline κ′ and a number of κ machines, the problem is to find a feasible assignment of the jobs to the machines. We prove the computational complexity of this scheduling problem restricted to different graph classes, arbitrary and constant numbers κ and κ′.

AB - We consider scheduling problems in a multiprocessor system with incompatible jobs of unit-time length where two incompatible jobs can not be processed on the same machine. Given a deadline κ′ and a number of κ machines, the problem is to find a feasible assignment of the jobs to the machines. We prove the computational complexity of this scheduling problem restricted to different graph classes, arbitrary and constant numbers κ and κ′.

U2 - 10.1007/3-540-57182-5_21

DO - 10.1007/3-540-57182-5_21

M3 - Chapter

SN - 978-3-540-57182-7

VL - 711

T3 - Lecture Notes in Computer Science

SP - 291

EP - 300

BT - Mathematical Foundations of Computer Science 1993

A2 - Borzyszkowski, Andrzej M.

A2 - Sokołowski, Stefan

PB - Springer

ER -

Bodlaender H, Jansen K. On the complexity of scheduling incompatible jobs with unit-times: Mathematical Foundations of Computer Science 1993. In Borzyszkowski AM, Sokołowski S, editors, Mathematical Foundations of Computer Science 1993: 18th International Symposium, MFCS'93 Gdańsk, Poland, August 30–September 3, 1993 Proceedings. Vol. 711. Springer. 1993. p. 291-300. (Lecture Notes in Computer Science). doi: 10.1007/3-540-57182-5_21

On the complexity of scheduling incompatible jobs with unit-times: Mathematical Foundations of Computer Science 1993

Abstract

Publication series

Access to Document

Fingerprint

Cite this