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

Abstrakt

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.

Cytowania

2 8

CrossRef
0

Web of Science
3 3

Scopus

Autorzy (3)

Cytuj jako

Pełna treść

pobierz publikację

pobrano 26 razy

Wersja publikacji: Accepted albo Published Version
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2009.02.024
Licencja: Copyright (2009 Elsevier B.V)

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

Informacje szczegółowe

Kategoria:: Publikacja w czasopiśmie
Typ:: artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:: DISCRETE APPLIED MATHEMATICS nr 157, strony 3625 - 3630,
ISSN: 0166-218X
Język:: angielski
Rok wydania:: 2009
Opis bibliograficzny:: 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:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2009.02.024
Weryfikacja:: Politechnika Gdańska