Wyszukiwarka
Abstrakt
Artykuł podejmuje problem szeregowania zadań przy założeniu podziału czasu na sloty jednakowej długości, gdzie każde z zadań ma ustaloną długość oraz czas jego zakończenia, który jest relatywny do końca slotu. Problem znalezienia uszeregowania polega na dokonaniu przydziału zadań do poszczególnych slotów, przy czym w ogólności długość zadania może wymuszać sytuację, w której zadańie jest realizowane nie tylko w slocie, w którym się kończy, lecz także we wcześniejszych slotach. Długość harmonogramu to kryterium optymalizacyjne rozważane w pracy. Artykuł podaje szereg algorytmów, w szczególności: optymalny algorytm dla jednej maszyny o czasie działania O(n log^2n); optymalny algorytm o czasie działania O(n log n) dla dowolnej liczby maszyn i zadań, których długość nie przekracza ustalonego czasu zakończenia; oraz wielomianowy algorytm aproksymacyjny o stałym wspołczynniku aproksymacji dla ogólnego przypadku.
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:
-
JOURNAL OF SCHEDULING
nr 13,
strony 479 - 492,
ISSN: 1094-6136 - Język:
- angielski
- Rok wydania:
- 2010
- Opis bibliograficzny:
- Dereniowski D., Kubiak W.: Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines// JOURNAL OF SCHEDULING. -Vol. 13, nr. Nr 5 (2010), s.479-492
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 130 razy
Publikacje, które mogą cię zainteresować
Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.
- H. Furmańczyk,
- A. Kosowski,
- P. Żyliński