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

Search

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

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.

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 94 times

Recommended for you

Meta Tags