Dedicated scheduling of tasks to minimize mean flow time

Krzysztof Giaro; Marek Kubale; Michał Małafiejski; Konrad Piwakowski

Dedicated scheduling of tasks to minimize mean flow time

Abstrakt

This paper investigates the complexity of scheduling biprocessor tasks on dedicated processors to minimize mean flow time. Since the general problem is strongly NP-hard, we assume some restrictions on task lengths and the structure of associated scheduling graphs. Of particular interest are acyclic graphs. In this way we identify a borderline between NP-hard and polynomially solvable special cases.

Autorzy (4)

Krzysztof Giaro prof. dr hab. inż.
Marek Kubale prof. dr hab. inż.
Michał Małafiejski dr hab. inż.
Konrad Piwakowski dr inż.
- Wydział Elektroniki, Telekomunikacji i Informatyki
- Politechnika Gdańska

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Kategoria:: Publikacja w czasopiśmie
Typ:: artykuł w czasopiśmie z listy filadelfijskiej
Opublikowano w:: LECTURE NOTES IN COMPUTER SCIENCE nr 2328, strony 87 - 96,
ISSN: 0302-9743
Język:: angielski
Rok wydania:: 2002
Opis bibliograficzny:: Giaro K., Kubale M., Małafiejski M., Piwakowski K.: Dedicated scheduling of tasks to minimize mean flow time// LECTURE NOTES IN COMPUTER SCIENCE. -Vol. 2328., (2002), s.87-96
Weryfikacja:: Politechnika Gdańska