Elimination of dominated partial schedules in scheduling deteriorating jobs

• Autorzy: Ocetkiewicz K.

Warianty tytułu

PL

Eliminacja zdominowanych częściowych harmonogramów w szeregowaniu zadań uwarunkowanych czasowo

• Języki publikacji: EN

Abstrakty

EN

In the article we consider a problem of scheduling deteriorating jobs that can be described by 1 | pi = a + bisi | ?Ci. We introduce the concept of dominated partial schedules and present a non-polynomial algorithm for the problem, that is based on elimination of dominated partial schedules. We present the results of computational experiments comparing the efficiency of given algorithm to other exact algorithms for the problem (exhaustive-search, branch-and-bound). Finally, we investigate the usefulness of the given algorithm as an approximate algorithm for problems 1 | pi = a + bisi | ?wiCi, 1 | pi = ai + bisi | ?Ci and 1 | pi = ai + bisi | ?wiCi.

PL

W artykule rozważany jest problem szeregowania zadań uwarunkowanych czasowo, w notacji trójpolowej opisywany przez 1 | pi = a + bisi | ?Ci. Wprowadzona jest koncepcja zdominowanych częściowych harmonogramów oraz przedstawiony jest niewielomianowy algorytm dla problemu, który bazuje na eliminacji zdominowanych częściowych harmonogramów. Przedstawione są wyniki eksperymentów obliczeniowych, porównujących zaprezentowany algorytm oraz inne algorytmy dokładne dla problemu 1 | pi = a + bisi | ?Ci (pełne przeszukiwanie, branch-and-bound). Na koniec sprawdzona jest skuteczność algorytmu jako algorytmu przybliżonego dla problemów 1 | pi = a + bisi | ?wiCi, 1 | pi = ai + bisi | ?Ci oraz 1 | pi = ai + bisi | ?wiCi.

Słowa kluczowe

EN

deteriorating jobs; computer programs

PL

zadania uwarunkowane czasowo; programy komputerowe

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2010
• Tom: T. 18
• Strony: 339--344
• Opis fizyczny: Bibliogr. 9 poz., rys., tab.

Twórcy

autor

Ocetkiewicz K.

• Gdansk University of Technology Department of Algorithms and System Modelling

Bibliografia

• [1] Cheng T.C.E., Ding Q., Lin B.M.T.: A concise survey of scheduling with time-dependent processing times, European Journal of Operational Research, 152, 1-13, 2004.
• [2] Gawiejnowicz S., Kurc W., Pankowska L., A greedy approach for a time-dependent scheduling problem, Lecture Notes in Computer Science, 2328, 79-86, 2002.
• [3] Gawiejnowicz S., Kurc W., Pankowska L., Minimalizacja łacznego czasu zakończenia zbioru zadań czasowo-zależnych metodą kolejnych ulepszeń (in Polish), Sterowanie procesami dyskretnymi, zarządzanie i inżynieria produkcji, 47–54, 2004.
• [4] Gawiejnowicz S., Lai T.-C., Chiang M.-H., Polynomially solvable cases of scheduling deteriorating jobs to minimize total completion time, Extended Abstracts of the 7th Workshop on Project and Management Scheduling, University of Osnabruck, 131-134, 2000.
• [5] Graham R.L., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Math., 5, 287-326, 1979.
• [6] Mosheiov G.: V-shaped policies for scheduling deteriorating jobs, Operations Research, 39 (6), 979-991, 1991.
• [7] Ocetkiewicz K.M.: Porównanie heurystyk dla problemu szeregowania zadań czasowo-zależnych o wspólnym podstawowym czasie wykonywania (in Polish), Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej, 12, 145–152, 2007.
• [8] Ocetkiewicz K.M.: Algorytm branch-and-bound dla pewnego problemu szeregowania zadań uwarunkowanych czasowo (in Polish), Automatyka 13 (2), 521–529, 2009.
• [9] Ocetkiewicz K.M.: A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem. European Journal of Operational Research 203 (2), 316–320, 2010.