Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: szeregowanie zadań czasowo-zależnych

Sortuj według:

Ogranicz wyniki do:

Porównanie heurystyk dla problemu szeregowania zadań czasowo-zależnych o wspólnym podstawowym czasie wykonywania

Ocetkiewicz K.M.

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

2007

T. 12

145-152

W pracy rozważany jest następujący, jednoprocesorowy problem szeregowania zadań czasowo-zależnych. Danych jest n+ 1 zadań o czasach wykonywania postaci p; = a + bis;, gdzie s; oznacza czas rozpoczęcia wykonywania i-tego zadania, a > O, b; > O, i = O, 1, ..., n. Wszystkie zadania są niepodzielne i dostępne w chwili to = O. 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.

In this paper a single machine time-dependent scheduling problem is considered. The processing time of the i-th job is given by Pi = a + biSi, where a > 0, bi > 0, i = 0, 1, ..., n. All tasks are available at t0 = 0, and the goal is to minimize the total completion time. An algorithm, which gives optimal solution, provided that the values of bi coefficients grow sufficiently fast, was presented. Two new heuristics were introduced. Their's, and other known heuristics' results were compared to optimal solutions.