Algorytmy lokalnego przeszukiwania dla zagadnienia przepływowego z maszynami równoległymi i wymaganiami bez magazynowania

• Autorzy: Bożejko W. , Grabowski J. , Pempera J.

Warianty tytułu

EN

The local search algorithms for flow-shop problem with parallel machines and no store constrains

• Języki publikacji: PL

Abstrakty

PL

W niniejszej pracy rozważa się dwustanowiskowy problem przepływowy z maszynami równoległymi oraz ograniczeniami bez magazynowania z kryterium Cmax. Przedstawiono warunki związane z dopuszczalną kolejnością wykonywania zadań oraz nową definicję ruchu, tzw. ruch z korekcją. Proponowany ruch może być zastosowany w algorytmach lokalnego przeszukiwania. W pracy przedstawia się algorytmy bazujące na technikach przeszukiwania z zabronieniami, przeszukiwania genetycznego oraz symulowanego wyżarzania. Test komputerowy pokazuje przewagę zaproponowanego ruchu nad standardowymi ruchami stosowanymi do przepływowych problemów szeregowania zadań z maszynami równoległymi.

EN

The paper deals with two stages flow-shop scheduling problem with parallel machines, no store constrains and the makespan criterion. There are presented and discussed some conditions associated with the processing order and new definition of the move i.e. the move with correction. This move can be applied in any local search algorithms. The algorithms based on tabu search, genetic search and simulated annealing are presented. Computational experiments shown advantage proposed move over standards moves intend to flow-shop scheduling problem with parallel machines.

Słowa kluczowe

PL

maszyny równoległe

EN

parallel machines

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2001
• Tom: T. 5, z. 1/2
• Strony: 87--93
• Opis fizyczny: Bibliogr. 8 poz., rys., tab.

Twórcy

autor

Bożejko W.

autor

Grabowski J.

autor

Pempera J.

• Instytut Cybernetyki Technicznej, Politechnika Wrocławska

Bibliografia

• [1] Glover E: Tabu Search. Part I, ORSA Journal of Computing, 1, 1989, 190-206
• [2] Glover F.: Tabu Search. Part II, ORSA Journal of Computing, 2, 1990, 4-32
• [3] Aarts E.H.I., van Laarhoven P.J.M.: Simulated annealing: a predestrain review of th theory and some aplications. Deiijver P.A., Kittier J. (eds), Pattem Recognition and Application, Berlin, Springer 1987
• [4] Nowicki E., Smutnicki C.: The flow shop with parallel machines: A tabusearch approach. European Journal of Operational Research, 106, 1998,226-253
• [5] Nowicki E.: Metoda tabu w problemach szeregowania zadań produkcyjnych. Monografie, prace naukowe Instytutu Cybernetyki Technicznej Politechniki Wrocławskiej 1999
• [6] Pempera J.: Algorytmy szeregowania zadań w pewnym dyskretnym procesie produkcyjnym. Raporty Instytutu Cybernetyki Technicznej Politechniki Wrocławskiej 117,2000 (praca doktorska)
• [7] Reeves C.R., Yamada T.: Genetic algorithms, path relinking and the flowshop sequencing problem. Evolutionary Computation, 6,1998,45-60
• [8] Smutnicki C.: Optimization and control in just-in-time manufacturing systems. Monografie, prace naukowe Instytutu Cybernetyki Technicznej Politechniki Wrocławskiej 1997