An efficient algorithm for finding ideal schedules - Publikacja - MOST Wiedzy

Wyszukiwarka

An efficient algorithm for finding ideal schedules

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

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 69 razy

Publikacje, które mogą cię zainteresować

Meta Tagi