Search
Abstract
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 (2)
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:
-
JOURNAL OF SCHEDULING
no. 13,
pages 479 - 492,
ISSN: 1094-6136 - Language:
- English
- Publication year:
- 2010
- Bibliographic description:
- 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
- Verified by:
- Gdańsk University of Technology
seen 135 times
Recommended for you
Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.
- H. Furmańczyk,
- A. Kosowski,
- P. Żyliński