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.
Authors
Additional information
- Category
- Publikacja w czasopiśmie
- Type
- artykuł w czasopiśmie wyróżnionym w JCR
- Language
- angielski
- Publication year
- 2010
