An Application of Hierarchical Genetic Strategy in sequential scheduling of permutated independent jobs

• Autorzy: Kołodziej J. , Rybarski M.
• Konferencja: Evolutionary Computation and Global Optimization 2009 / National Conference (12 ; 1-3.06.2009 ; Zawoja, Poland)
• Języki publikacji: EN

Abstrakty

EN

The aim of this paper is to present an implementation of Hierarchic Genetic Strategy (HGS) in solving the Permutation Flowshop Scheduling Problem (PFSP). We defined a hierarchic scheduler based on HGS structure for the exploration of the wide and complicated optimization landscape studied by Reeves. The objective of our work is to examine several variations of HGS operators in order to identify a configuration of operators and parameters that works best for the problem. From the experimental study we observed that HGS implementation outperforms existing schedulers in many of considered instances of a static benchmark for the problem.

Słowa kluczowe

EN

Hierarchical Genetic Strategy; HGS; genetic algorithm; evolutionary algorithm; EA; evolutionary computation; permutation flow shop scheduling problem; PFSP; optimization

PL

algorytm genetyczny; algorytm ewolucyjny; obliczenia ewolucyjne; optymalizacja

• Wydawca: Oficyna Wydawnicza Politechniki Warszawskiej
• Czasopismo: Prace Naukowe Politechniki Warszawskiej. Elektronika
• Rocznik: 2009
• Tom: z. 169
• Strony: 95--102
• Opis fizyczny: Bibliogr. 12 poz., tab., rys.

Twórcy

autor

Kołodziej J.

autor

Rybarski M.

• University of Bielsko-Biała, Department of Mathematics and Computer Science, ul. Willowa 2, 43-309 Bielsko-Biała, Poland,

Bibliografia

• [1] J.E. Beasley. Or-library: Distributing test problems by electronic mail. European J. Operational Research, (41):1069-1072, 1990.
• [2] H.G. Beyer. The Theory of Evolution Strategies. Natural Computation. Springer Vlg., Berlin-Heidelberg, 2001.
• [3] T.D. Braun, H.J. Siegel, N. Beck, L.L. Boloni, M. Maheswaran, A.I. Reuther, J.P. Robertson, M.D. Theys, B. Yao, D. Hensgen, and R.F. Freund. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing, 61(6):810ℓ-837, 2001.
• [4] R. Gwizdała, J. Kołodziej and J. Wojtusiak. Hierarchical genetic strategy as a method of improving search efficiency. Advances in Multi-Agent Systems, R. Schaefer and S. Sędziwy (Eds.), UJ Press, Cracow, pages 149-161, 2001.
• [5] J. Kołodziej, F. Xhafa, and Ł. Kolanko. Hierarchic genetic scheduler of independent jobs in computational grid environment. In To Appear, editor, Proc. of ECMS09, 2009.
• [6] C.R. Reeves. Landscapes, operators and heuristic search. Annals of Operations Research, 86:473-490, 1999.
• [7] C.R. Reeves and T. Yamada. Genetic algorithms, path relinking and the flowshop sequencing problem. Evolutionary Computation, 6(1):230-244, 1998.
• [8] R. Schaefer and J. Kołodziej. Genetic search reinforced by the population hierarchy. FOGA VII, Morgan Kaufmann, pages 383-401, 2003.
• [9] T. Śliwiński and E. Toczyłowski. Algorytm harmonogramowania zadań podzielnych na maszynach równoległych przy uwzględnieniu przezbrojeń i ograniczeń zasobowych. In Proc. of XV National Conference of Automation 2005, Warszawa, 27-30.06.05, 2005.
• [10] E. Taillard. Benchmarks for basic scheduling problems. E. J. Of Oper. Res., (64):278ℓ-285, 1993.
• [11] T. Yamada and R. Nakano. Scheduling by genetic local search with multi-step crossover. In 4th PPSN, pages 960ℓ-969, 1996.
• [12] T. Yamada and C.R. Reeves. Permutation flowshop scheduling by genetic local search. In Proceedings of the 2nd IEE/IEEE International Conference on Genetic Algorithms in Engineering Systems (CALESIA'97), pages 232-238, 1997.