A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints

Krzysztof Giaro; Marek Kubale; Paweł Obszarski

doi:10.1016/j.dam.2009.02.024

A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints

Abstract

We address a generalization of the classical 1- and 2-processor unit execution time scheduling problem on dedicated machines. In our chromatic model of scheduling machines have non-simultaneous availability times and tasks have arbitrary release times and due dates. Also, the versatility of our approach makes it possible to generalize all known classical criteria of optimality. Under these stipulations we show that the problem of optimal scheduling of sparse tree-like instances can be solved in polynomial time. However, if we admit dense instances then the problem becomes NP-hard, even if there are only two machines.

Citations

2 8

CrossRef
0

Web of Science
3 3

Scopus

Authors (3)

Cite as

Full text

download paper

downloaded 25 times

Publication version: Accepted or Published Version
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.dam.2009.02.024
License: Copyright (2009 Elsevier B.V)

full content of the article see on external site open in new tab

Keywords

Details

Category:: Articles
Type:: artykuł w czasopiśmie wyróżnionym w JCR
Published in:: DISCRETE APPLIED MATHEMATICS no. 157, pages 3625 - 3630,
ISSN: 0166-218X
Language:: English
Publication year:: 2009
Bibliographic description:: Giaro K., Kubale M., Obszarski P.: A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints// DISCRETE APPLIED MATHEMATICS. -Vol. 157, nr. iss. 17, October 28. (2009), s.3625-3630
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.dam.2009.02.024
Verified by:: Gdańsk University of Technology