Search
Abstract
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).
Citations
-
8
CrossRef
-
0
Web of Science
-
8
Scopus
Authors (3)
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
ACTA INFORMATICA
no. T. 49,
pages 1 - 14,
ISSN: 0001-5903 - Language:
- English
- Publication year:
- 2012
- Bibliographic description:
- 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:
- Digital Object Identifier (open in new tab) 10.1007/s00236-011-0146-7
- Verified by:
- Gdańsk University of Technology
seen 110 times