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

• Autorzy: Ocetkiewicz K.M.

Warianty tytułu

EN

Comparison of heuristics for time-dependent scheduling with common base processing time problem

• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

szeregowanie zadań czasowo-zależnych; heurystyki; harmonogramy

EN

time-dependent scheduling; heuristics; base processing time

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2007
• Tom: T. 12
• Strony: 145--152
• Opis fizyczny: Bibliogr. 4 poz., tab.

Twórcy

autor

Ocetkiewicz K.M.

• Katedra Algorytmów i Modelowania Systemów, Politechnika Gdańska

Bibliografia

• [1] Gawiejnowicz S., Lai T-c., Chiang M-H.: Polynomially solvable cases of scheduling deteriorating jobs to minimize total completion time, W: Brucker P. et al. (eds.): 7th Workshop on Project Management and Scheduling, Osnabrück, 2000, s. 131-134, 2000.
• [2] Mosheiov G.: V-shaped policies for scheduling deteriorating jobs, W: Operations Research 39, s. 979-991,1991.
• [3] Gawiejnowicz S., Kurc W., Pankowska L: A greedy approach for a time-dependent scheduling problem. W: Lecture Notes on Computer Science 2328, s.79-86, 2002.
• [4] Gawiejnowicz S., Kurc W., Pankowska L: Minimalizacja łącznego czasu zakończenia zbioru zadań czasowo-zależnych metodą kolejnych ulepszeń. W: Sterowanie procesami dyskretnymi, zarządzanie i inżynieria produkcji, s.47-54, WNT 2004.