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).
Autorzy
- Edward G. Coffman Jr.,
- prof. dr hab. inż. Dariusz Dereniowski link otwiera się w nowej karcie ,
- Wiesław Kubiak
Informacje dodatkowe
- DOI
- Cyfrowy identyfikator dokumentu elektronicznego link otwiera się w nowej karcie 10.1007/s00236-011-0146-7
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuł w czasopiśmie wyróżnionym w JCR
- Język
- angielski
- Rok wydania
- 2012
Źródło danych: MOSTWiedzy.pl - publikacja "An efficient algorithm for finding ideal schedules" link otwiera się w nowej karcie
