Search
Porównanie heurystyk dla problemu szeregowania zadań czasowo-zależnych o wspólnym podstawowym czasie wykonywania
Abstract
W pracy rozważany jest następujący, jednoprocesorowy problem szeregowania zadań czasowo-zależnych. danych jest n+1 zadań o czasach wykonywania postaci pi = a + bisi, gdzie si oznacza czas rozpoczęcia wykonywania i-tego zadania, a > 0, bi > 0, i = 0, 1, ..., n. wszystkie zadania są niepodzielne i dostępne w chwili t0 = 0. należy znaleźć harmonogram minimalizujący łączny czas zakończenia. w pracy przedstawiono algorytm, który, o ile kolejne wartości bi rosną dostatecznie szybko, znajduje optymalny harmonogram. następnie zaproponowano dwie nowe heurystyki, oraz porównano rozwiązania zwracane przez te, oraz inne znane heurystyki dla danych wejściowych o znanym rozwiązaniu optymalnym.
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Published in:
-
Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
no. T. 12,
pages 145 - 152,
ISSN: 1732-1166 - Language:
- Polish
- Publication year:
- 2007
- Bibliographic description:
- Ocetkiewicz K.: Porównanie heurystyk dla problemu szeregowania zadań czasowo-zależnych o wspólnym podstawowym czasie wykonywania// Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne. -Vol. T. 12., (2007), s.145-152
- Verified by:
- Gdańsk University of Technology
seen 109 times