Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines - Publikacja - MOST Wiedzy

Wyszukiwarka

Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines

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.

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

wyświetlono 6 razy

Meta Tagi