Tytuł artykułu
Autorzy
Identyfikatory
Warianty tytułu
Comparison of heuristics for time-dependent scheduling with common base processing time problem
Języki publikacji
Abstrakty
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.
Rocznik
Tom
Strony
145--152
Opis fizyczny
Bibliogr. 4 poz., tab.
Twórcy
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BPG5-0029-0014