Block approach-local search algorithm for single machine total weighted tardiness problem

• Autorzy: Bożejko W. , Grabowski J. , Wodecki M.

Warianty tytułu

PL

Zastosowanie bloków w algorytmie lokalnych poszukiwań dla jednomaszynowego problemu szeregowania z minimalizacją sumy kosztów opóźnień

• Języki publikacji: EN

Abstrakty

EN

This paper deals with the single-machine scheduling problem to minimize total weighted tardiness of jobs. Some new properties of the problem have been presented and discussed. These properties allow us to propose a new fast tabu search approach with a specific neighborhood which employs blocks of jobs and a compound moves technique. The proposed algorithm is empirically evaluated and found to be relatively more effective in finding good solutions in a shorter time than existing algorithms.

PL

W pracy rozpatrujemy problem szeregowania zadań na jednej maszynie z minimalizacją sumy kosztów opóźnień. Przedstawiamy szereg nowych własności pozwalających na rozbicie permutacji (rozwiązania dopuszczalnego) na podciągi, zwane blokami. Dzięki temu, z otoczeń generowanych przez ruchy typu zamień lub wstaw, eliminujemy wiele rozwiązań nie gwarantujących poprawę wartości funkcji celu. Algorytm oparty na metodzie poszukiwania z zabronieniami (tabu search), w którym stosuje się te otoczenia, działa bardzo szybko, a otrzymane wyniki są lepsze niż inne wyniki opisane w literaturze algorytmów.

Słowa kluczowe

EN

sequencing; weighted tardiness problem; heuristics; tabu search

PL

szeregowanie zadań; koszty opóźnień; heurystyki; metoda poszukiwania z zabronieniami

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2005
• Tom: T. 9, z. 1-2
• Strony: 25--35
• Opis fizyczny: Bibliogr. 15 poz., rys., tab.

Twórcy

autor

Bożejko W.

• Institute of Engineering Cybernetics, Wroclaw University of Technology

autor

Grabowski J.

• Institute of Engineering Cybernetics, Wroclaw University of Technology

autor

Wodecki M.

• Institute of Computer Science, University of Wroclaw

Bibliografia

• [ 1 ] Bożejko W., Grabowski J., Wodecki M . : A block approach tabu search algorithm for single machine total weihhted tardiness problem . Technical Report 2 / 2 005, Institute of E ngineering Cybernetics Wrocław University of Technology
• [ 2 ] Congram R . K ., Potts C . N ., Van de Velde S . L . : An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem . INFORMS Journal on Computing, 14 (1) , 2002, 52 –67
• [ 3 ] Crauwels H .A.J., Potts C . N ., Van Wassenhove L . N . : Local Search Heuristics for the Single Machine Total Weighted Tardiness Scheduling Problem . INFORMS Journal on Computing, 10 (3) , 1998 , 341– 350
• [ 4 ] Den Basten M ., Stützle T ., Dorigo M . : Design of Iterated Local Search Algorithms an Example Application to the Single Machine Total Weighted Tardiness Problem. In : EvoWorsk shop LNCS 2037 ( J.W. Boerset al . ) 2001 , 441-51
• [ 5 ] Dongarra J.J. : Performance of various computers using standard linear equations software . Working paper. Computer Science Department, University of Tennessee US A 2001, http:// www.netlib.org /benchmark/performance.ps
• [ 6 ] Glover F ., Laguna M . : Tabu Search . Kluwer Academic Publishers, 1998
• [ 7 ] Grabowski J., Pempera J. : New block properties for the permutation flow-shop problem with application in TS . Journal of the Operational Research Society, 11 , 2001 , 210-220
• [ 8 ] Grabowski J., Wodecki M . : A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion . Computers and Operations Research, 31 , 2004, 1891-1909
• [ 9 ] Grabowski J., Wodecki M . : A very fast tabu search algorithm for the job shop problem . In : Metaheuristic Optimization via Memory and Evolution, Tabu Search and Scatter Search, (C . Rego, B . Alidaee (E ds )), Kluwer Academic Publishers 2005
• [ 10 ] Grosso A., Della Croce F ., Tadei R . : An enhanced dynasearch neighborhood for single-machine total weighted tardiness scheduling problem . Operations Research Letters, 32, 2004, 68–72
• [ 11 ] Lawler E . L . : A Pseudopolynomial Algorithm for Sequencing Jobs to Minimize Total Tardiness. Annals of Discrete Mathematics, 1 , 1977 , 331– 342
• [ 1 2 ] Lenstra J. K ., Rinnoy Kan A.G. H ., Brucker P . : Complexity of Machine Scheduling Problems . Annals of Discrete Mathematics, 1 , 1977 , 343 – 362
• [ 1 3 ] Matsuo H ., Otto S .W., Sullivan R . S . : A controlled search simulated annealingmethod for the single machine weighted tardiness problem . Working paper 87-12 - 2, Department of Management, University of Texas at Austin, T X US A 1987
• [ 1 4 ] O R Liblary http . // www.ms.ic.ac.uk / info.html
• [ 15 ] Rinnoy Kan A. H .G., Lageweg B .J., Lenstra J. K . : Minimizing total costs in one-machine scheduling . Operations Research, 25 , 1975 , 908–927