Algorytm branch-and-bound dla pewnego problemu szeregowania zadań uwarunkowanych czasowo

• Autorzy: Ocetkiewicz K. M.

Warianty tytułu

EN

Branch-and-bound algorithm for a certain time-dependent scheduling problem

• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiono algorytm branch-and-bound dla problemu szeregowania zadań uwarunkowanych czasowo 1 | pi = 1 + atst | XQ, a także wyniki eksperymentów komputerowych prezentujących wydajność algorytmu. Zastosowanie przedstawionego algorytmu umożliwia powiększenie "obliczalnych" rozmiarów instancji o 6-10 zadań w stosunku do algorytmu pełnego przeszukiwania.

EN

The article presents a branch-and-bound algorithm for a follo­wing time-dependent scheduling problem: 1 \pt: = 1 + atst | XC,. The computational experiments were conducted to examine the efficiency of the algorithm. Application of the presented algorithm allows us to increase the size of input instances that can be solved to optimality in reasonable time by 6-10 jobs, compared to the exhaustive-search algorithm.

Słowa kluczowe

PL

szeregowanie zadań uwarunkowanych czasowo; branch-and-bound

EN

time-dependent scheduling; branch-and-bound

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2009
• Tom: T. 13, z. 2
• Strony: 521--529
• Opis fizyczny: Bibliogr. 7 poz., rys., wykr., tab.

Twórcy

autor

Ocetkiewicz K. M.

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

Bibliografia

• [1] Cheng T.C.E., Ding Q., Lin B.M.T., A concise survey of scheduling with time-dependent processing times. EJOR, 152, 2004, 1-13.
• [2] 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 Osnabriick, 2000, 131-134.
• [3] Mosheiov G., V-shaped policies for scheduling deteriorating jobs. Operations Research, 39, 1991, 979-991.
• [4] Gawiejnowicz S., Kurc W., Pankowska L., A greedy approach for a time-dependent scheduling problem. LNCS, 2328, 2002, 79-86.
• [5] Gawiejnowicz S., Kurc W., Pankowska L., Minimalizacja łącznego czasu zakończenia zbioru zadań czasowo-zależnych metodą kolejnych ulepszeń. Sterowanie procesami dyskretnymi, zarządzanie i inżynieria produkcji, 2004, 47-54.
• [6] Ocetkiewicz K.M., Porównanie heurystyk dla problemu szeregowania zadań czasowo-zależnych o wspólnym podstawowym czasie wykonywania. Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej, 12, 2007, 145-152.
• [7] Browne S., Yechiali U., Scheduling deteriorating jobs on a single processor. Operations Research, 38, 1990, 495^98.