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).
Authors
- Edward G. Coffman Jr.,
- prof. dr hab. inż. Dariusz Dereniowski link open in new tab ,
- Wiesław Kubiak
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.1007/s00236-011-0146-7
- Category
- Publikacja w czasopiśmie
- Type
- artykuł w czasopiśmie wyróżnionym w JCR
- Language
- angielski
- Publication year
- 2012
