A new local search optimization algorithm for the job-shop problem

• Autorzy: Grabowski J. , Wodecki M.

Warianty tytułu

PL

Nowy algorytm lokalnej optymalizacji dla ogólnego problemu szeregowania

• Języki publikacji: EN

Abstrakty

EN

This paper deals with a classic job-shop scheduling problem with makespan criterion. We present some new theoretical properties of the problem associated with the blocks, moves and neighbourhood structure, and algorithm based on a tabu search approach. Computational experiments are given and compared with the results yielded by the best algorithms discussed in the literature. These results show that the algorithm proposed solves the job-shop instances with high accuracy in a very short time.

PL

W referacie przedstawimy algorytm tabu oparty na idei bloków z drogi krytycznej, dla rozwiązywania ogólnego problemu szeregowania (ang. job-shop problem). Szacowanie wartości funkcji celu rozwiązań z otoczenia (bez konieczności dokładnego ich liczenia), znacznie przyspiesza zbieżność i skraca czas działania algorytmu. Przedstawimy pewne metody (perturbacje) pozwalające na bardzo szybką zmianę badanych obszarów zbioru rozwiązań dopuszczalnych oraz nowy sposób realizacji listy tabu, który zapobiega powstawaniu cykli w algorytmie (generowaniu tych samych rozwiązań po pewnej liczbie kroków algorytmu). Przeprowdzone eksperymenty obliczeniowe wskazują jednoznacznie, że wyżej przedstawione idee znacznie przyspieszają oraz poprawiają wyniki algorytmu.

Słowa kluczowe

EN

tabu search algorithm; job shop problem

PL

algorytm tabu search; problem szeregowania

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2003
• Tom: T. 7, z. 1-2
• Strony: 121--128
• Opis fizyczny: Bibliogr. 11 poz., tab.

Twórcy

autor

Grabowski J.

• Wrocław, University of Technology, Institute of Engineering Cybernetics

autor

Wodecki M.

• University of Wroclaw, Institute of Computer Science

Bibliografia

• [1] Aarts E., Lenstra J.K.: Local search in combinatorial optimization. New York, Wiley 1970
• [2] Balas E., Vazacopoulos A.: Guided local search with shifting bottleneck for job-shop scheduling. Management Science, 44, 2, 1998, 262-275
• [3] Grabowski J.: Generalized problems of operations sequencing in the discrete production systems. (Polish), Monographs 9, Scientific Papers of the Institute of Technical Cybernetics of Wroclaw Technical University 1979
• [4] Grabowski J., Nowicki E., Smutnicki C.: Block algorithm for scheduling of operations in job- shop system. (Polish), Przegląd Statystyczny, 35, 1988, 67-80
• [5] Grabowski J., Pempera J.: New block properties for the permutation flow-shop problem with application in TS. Journal of the Operational Research Society, 52, 2001, 210-220
• [6] Grabowski J.,Wodecki M.: A very fast tabu search algorithm for the jobshop problem. Raport serii: Preprinty nr 21/2001, ICT Politechniki Wrocławskiej, 2001
• [7] Van Laarhoven R, Aarts E., Lenstra J.K.: Job-shop scheduling by simulated annealing. Operations Research, 40, 1992, 113-125
• [8] Matsuo H., Suh C.J., Sullivan R.S.: Controlled search simulated annealing method for the general job-shop scheduling problem. Working Paper 03-04-88, Department of Management, Graduate School of Business, The University of Texas at Austin 1988
• [9] Nowicki E., Smutnicki C.: A fast tabu search algorithm for the job-shop problem. Management Science, 42, 6, 1996, 797-813
• [10] Pezzella F., Merelli EA tabu search method guided by shifting bottleneck for the job-shop scheduling problem. European Journal of Operational Research, 120, 2000, 297-310
• [11] Vaessens R., Aarts E., Lenstra J.K.: Job shop scheduling by local search. INFORMS Journal of Computing, 8, 1996, 303-317