Bloki w problemie przepływowym z minimalizacją sumy kosztów opóźnień

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

Warianty tytułu

EN

Blocks in the total tardiness flow shop problem

• Języki publikacji: PL

Abstrakty

PL

W najlepszych algorytmach metaheurystycznych rozwiązywania problemu przepływowego z kryterium Cmax są stosowane bloki z drogi krytycznej. Pozwalają one na eliminację ruchów generujących "gorsze" elementy otoczenia. W pracy przedstawiamy uogólnienie klasycznego bloku, które stosujemy w algorytmie poszukiwania z zabronieniami dla problemu przepływowego z minimalizacją sum kosztów opóźnień [FIIsigmaw(i)T(i)].

EN

Blocks are applied in the best metaheuristic algorithms of solving flow shop problem with the makespan (Cmax) criterion. It makes possible to eliminate moves which generates worse elements of a neighborhood. In this paper we present generalization of the classic block formulation, which we are applying in the tabu search algorithm to solving total tardiness flow shop problem [FIIsigmaw(i)T(i)].

Słowa kluczowe

PL

szeregowanie zadań; problem przepływowy; spóźnienie; przeszukiwanie z zabronieniami

EN

scheduling; flow shop problem; earliness; tardiness; tabu search

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

Twórcy

autor

Bożejko W.

• Instytut Informatyki, Automatyki i Robotyki, Politechnika Wrocławska

autor

Grabowski J.

• Instytut Informatyki, Automatyki i Robotyki, Politechnika Wrocławska

autor

Wodecki M.

• Instytut Informatyki, Uniwersytet Wrocławski

Bibliografia

• [1] Adenso-Dias B.: Restricted neighborhood in the tabu search for the flowshop problem. EJOR, 1992, 62, 27-37
• [2] Adrabiński A., Grabowski J., Wodecki M.: Permutacyjne zagadnienie taśmowe postaci FIISwiTi. Archiwum Automatyki i Robotyki, 1991, Tom XXXVI, Zeszyt 3-4, 459-47
• [3] Bertel S., Billaut J.C.: A genetic algorithm for an industrial multiprocessor flowshop scheduling problem with recirculation. EJOR, 2004, 159, 651-662
• [4] Bożejko W., Wodecki M.: Solving Flow Shop Problem by Parallel Simulated Annealing. 2002, LNCS 2328, Springer-Verlag, 236-244
• [5] Bożejko W., Grabowski J., Wodecki M.: Block approach-tabu search algorithm for single machine total weighted tardiness problem. 2006, Computers & Industrial Engineering, 50, 1/2, 1-14
• [6] Chung C, Flynn J., Kirca O.: A branch and bound algorithm to minimize the total tardiness for n-machine permutation flowshop problems,. EJOR, 2006,174(1), 1-10
• [7] Grabowski J., Wodecki M.: A Mery fast tabu search algorithm for the permutation flow shop problem with makespan criterion. Computers and Operations Research, 2004, 31, 1891-1909
• [8] Grabowski J., Wodecki M.: A very fast tabu search algorithm for the job shop problem, in: Rego C, Alidaee B., editors. Adaptive memory and evolution; tabu search and scatter search, Dordrecht, Kluwer Academic Publishers, 2005, 117-144
• [9] Hariri A.M.A., Potts C.N.: Branch and Bound Algorithm to Minimize the Number of Late Jobs in a Permutation Flowshop. EJOR, 1989, 38, 228-237
• [10] Hasija S., Rajendran C: Scheduling in flowshop to minimize total tardiness of jobs. International Journal of Production Research, 2004, 42(11), 2289-2301
• [11] Kim Y.D.: Heuristics for flowshop scheduling problems minimizing mean tardiness. Journal of the Operational Research Society, 1993, 44, 19-28
• [12] Kim Y.D.: Minimizing total tardiness in permutation flowshop. EJOR, 1995, 85, 541-555
• [13] Lenstra J.K., Rinnoy Kan A.H.G., Brucker P.: Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1977, 1, 343-362
• [14] Navaz M., Enscore E.E., Ham I.: A heuristic algorithm for the m-machine, n-job flowshop sequencing problem. OMEGA, 1983, 11(1), 91-95
• [15] Nowicki E., Smutnicki C: A Fast tabu serach algorithm for the job shop problem. Management Science, 1996,42,797-813
• [16] Onwubolu G., Davendra D.: Scheduling flow shop using differential evolution algorithm. EJOR, 2006, 171, 674-692
• [17] Pan J., Chen J., Chao C: Minimizing tardiness in a two-machine flowshop. Computers & Operations Research, 2002, 29, 869-885
• [18] Rajendran C, Ziegler H.: Scheduling to minimize the sum of weighted flowtime and weighted tardiness of jobs in a flowshop with sequence-dependent setup times. EJOR, 2003, 147(3), 513-522
• [19] Schaller J.: Note on minimizing total tardiness in a two-machine flow shop. Computers & Operations Research, 30(5), 2005, 3273-3281
• [20] Wodecki M.: Dwumaszynowy problem przepływowy z minimalizacją kosztów opóźnień. Pod red R. Knosali: Komputerowo Zintegrowane Zarządzanie, WNT, Warszawa, 1999, 471-80
• [21] Wodecki M.: A branch-and-bound parallel algorithm for single-machine total weighted tardiness problem. Advanced manufacturing technology, 2007 (accepted)
• [22] Valada E., Ruiz R.: New genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem, 2006 (submitted)
• [23] Valada E., Ruiz R., Millea G.: Minimizing total tardiness in the m-machine flowshop problem: a review and evaluation heuristics and metaheuristics. Computers & Operations Research, 200" (in press)