Permutacyjny problem przepływowy. Algorytmy równoległe symulowanego wyżarzania

Bożejko, W.; Wodecki, M.

Artykuł - szczegóły

Tytuł artykułu

Permutacyjny problem przepływowy. Algorytmy równoległe symulowanego wyżarzania

Autorzy

Bożejko W. , Wodecki M.

Identyfikatory

Warianty tytułu

Permutation flow shop problem. Parallel simulated annealing algorithms

Konferencja

XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych

Języki publikacji

Abstrakty

W pracy rozpatrywany jest permutacyjny problem przepływowy z minimalizacją czasu wykonywania zadań. Przedstawiamy algorytmy (sekwencyjny i równoległy) oparte na metodzie symulowanego wyżarzania. W ich konstrukcji wykorzystano idee bloków z drogi krytycznej oraz dolne oszacowania wartości funkcji celu, a także różne schematy schładzania oraz funkcje akceptacji. Algorytmy testujemy na przykładach zaczerpniętych z pracy Taillarda [22].

This paper deals with the classic permutation flow shop scheduling problem with the make-span criterion. We describe an approximation algorithms (sequential and parallel) based on simulated annealing method. We research various accepting functions and cooling schedules.We propose neighbourhood using so called blocks of jobs on a critical path and also using lower bound of cost function.

Słowa kluczowe

problem przepływowy wyżarzanie symulowane algorytm równoległy

Wydawca

Wydawnictwo Politechniki Śląskiej

Czasopismo

Zeszyty Naukowe. Automatyka / Politechnika Śląska

Rocznik

2002

Tom

z. 134

Strony

91--101

Opis fizyczny

Bibliogr. 22 poz.

Twórcy

autor

Bożejko W.

Politechnika Wrocławska, Wrocław

autor

Wodecki M.

Uniwersytet Wrocławski

Bibliografia

1. Aarts E.H.L., Laarhoven Statistical cooling: A general approach to combinatorial optimization problems, Philips J. Res., 40 (1985), s. 193-226.
2. Bozejko W., Wodecki M.: Solving Flow Shop Problem by Parallel Simulated Annealing, LNCS, Springer-Verlag, 2328, (2002), 236-247.
3. Cerny V.: Thermodynamical approach to travelling salesman problem: An efficient simulation algorithm, J. Optim. Theory Appl. 45, (1985), s. 41-51.
4. Cohn H., Fielding M.: Simulated Annealing: Searching for an optimal temperature schedule, SIAM J. Optim., 9 (1999), s. 779-802.
5. Garey M.R., Johnson D.S., Seti R.: The complexity of flow shop and job shop scheduling, Mathematics of Operations Research, 1, (1976), s. 117-129.
6. Grabowski J.: A new algorithm of solving the flow-shop problem, Operations Research in Progress, D. Reidel Publishing Company, (1982), s. 57-75.
7. Grabowski J., Pempera J.: New block properties for the permutation flow-shop problem with application in TS, Journal of Operational Research Society 52, (2001), s. 210-220.
8. Hajek B.: Cooling schedules for optimal annealing, J.Math.Oper.Res.,13 (1988), 311-329.
9. Ignall E., Schrage L.E.: Application of the branch-and-bound technique to some flowshop scheduling problems, Operations Research, (1965), 13/3, s. 400-412.
10. Ishibuchi H., Misaki S., Tanaka H.: Modified Simulated Annealing Algorithms for the Flow Shop Sequencing Problem, European Journal of Operational Research 81, (1995), s. 388-398.
11. Johnson S.M.: Optimal two and three-stage production schedules with setup times included, Naval Research Logistic Quertely, 1 (1954), s. 61-68.
12. Kirkpatrick S., Geliat C.D., Vecchi M.P.: Optimization by simulated annealing, Science 220,(1983), s. 671-680.
13. Lageweg B.J., Lenstra J.K., Rinnooy Kan A.H.G.: A General Bouding Scheme for the Permutation Flow-Schop Problem, Opns. Res. 26, (1978), s. 53-67. 14. Lundy M., Mees A.: Convergence of an annealing algorithm, Math. Programming, 34, (1986), s. 111-124.
15. Navaz M., Enscore E.E. Jr, Ham I.: A heuristic algorithm for the m-machine, n-job flowshop sequencing problem, OMEGA 11/1 (1983) s. 91-95.
16. Nowicki E., Smutnicki C.: A fast tabu search algorithm for the permutation flow-shop problem, European Journal of Operational Research 91, (1996), s. 160-175.
17. Ogbu F., Smith D.: The Application of the Simulated Annealing Algorithm to the Solution of the n/m/Cmax Flowshop Problem, Computers & Operations Research, 17(3), (1990), s. 243-253.
18. Osman I., Potts C.: Simulated Annealing for Permutation Flow-Shop Scheduling, OMEGA 17(6), (1989), s. 551-557.
19. Reeves C.: Improving the Efficiency of Tabu Search for Machine Sequencing Problems, Journal of Operational Research Society 44(4), (1993), s. 375-382.
20. Reeves C.: A Genetic Algorithm for Flowshop Sequencing, Computers & Operations Research 22(1), (1995), s. 5-13.
21. Taillard E.: Some efficient heuristic methods for the flow shop sequencing problem, European Journal of Operational Research 47(1), (1990), s. 65-74.
22. Taillard E.: Benchmarks for basic scheduling problems, European Journal of Operational Research 64, (1993), s. 278-285.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-article-BSL6-0007-0061