Wyszukiwarka
Abstrakt
Podejmujemy problem szeregowania zadań jednostkowych z zadanymi czasamy przybycia i zależnościami kolejnościowymi. Uszeregowanie jest idealne jeśli jednocześnie minimalizuje maksymalny oraz średni czas zakończenia zadania. Podajemy przyklad pokazujący, że uszeregowania idealne nie istnieją dla relacji zależności zadań będącej drzewem, gdy dopuścimy możliwość wystąpienia przerwań. Z drugiej strony podajemy algorytm o złożoności O(n^3), który zawsze znajduje idealne uszeregowanie dla tego problemu bez przerwań. Wynik ten w szczególności dowodzi hipotezę postawioną przez Baptiste i Timkovsky (Math. Methods Oper. Res. 60(1):145-153, 2004).
Cytowania
-
8
CrossRef
-
0
Web of Science
-
8
Scopus
Autorzy (3)
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 wyróżnionym w JCR
- Opublikowano w:
-
ACTA INFORMATICA
nr T. 49,
strony 1 - 14,
ISSN: 0001-5903 - Język:
- angielski
- Rok wydania:
- 2012
- Opis bibliograficzny:
- Coffman Jr. E., Dereniowski D., Kubiak W.: An efficient algorithm for finding ideal schedules// ACTA INFORMATICA. -Vol. T. 49, nr. nr 1 (2012), s.1-14
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s00236-011-0146-7
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 110 razy