An electoral quantum-behaved PSO with Lévy flights for permutation flow shop scheduling problem

• Autorzy: Li D. , Deng N.

Warianty tytułu

PL

Algorytm wyborczy PSO z kwantowym zachowaniem z lotem Levy’ego do problemu szeregowania zmian przepływów magazynowych

• Języki publikacji: EN

Abstrakty

EN

Permutation flow shop scheduling problem (PFSSP), a NP-hard combinatorial optimization problem, has strong engineering background of finding the optimal processing sequence and time of jobs on machines under the constraints of resources. Recently, several approaches based on Particle Swarm Optimization (PSO) have been developed to solve the PFSSP, and the experimental results show that they are efficient. To solve this issue, a novel variant of quantum-behaved particle swarm optimization algorithm for permutation flow shop scheduling is proposed in this paper. This algorithm is a combination of quantum-behaved PSO, electoral mechanism, and a disturbance generated by Lévy flights. Inspired by the election behavior in society, an electoral and cooperative mechanism is imported to get the elite particles from the primitive sub-swarms respectively. Moreover, the character unequal hop length of Lévy flights provides a method to escape the local optima efficiently. The numerical results on the Taillard's benchmark also show it outperforms other related algorithms.

PL

Problem szeregowania zmiany przepływów magazynowych (PFSSP) jest silnie nie–wielomianowym (NP) problemem optymalizacji kombinatorycznej. Ma ważny inżynierski aspekt w wyznaczaniu optymalnej kolejności procesu i czasu pracy maszyn, wymuszonej zmianą zasobów. Ostatnio, do rozwiązania PFSSP, zastosowano szereg przybliżeń opartych o algorytm optymalizacji rojem cząstek (PSO) a wyniki praktyczne pokazują, że są to rozwiązania efektywne. W prezentowanym opracowaniu, do szeregowania przepływów magazynowych, zaproponowano nowy wariant algorytmu optymalizacji rojem cząstek z zachowaniem kwantowym (QPSO). Algorytm jest kombinacją QPSO, mechanizmu wyborczego i zakłóceń generowanych rozkładem lotów Levy’ego. Do wyłonienia cząstek elitarnych z prymitywnego pod-roju wykorzystano, inspirowany zachowaniami wyborczymi w społeczeństwie, mechanizm wyborczy i współpracy. Ponadto, unikalny charakter długości skoków lotów Levy’ego pozwala skutecznie uniknąć optimów lokalnych. Wyniki numeryczne, przeprowadzone na danych testowych Taillard’a, także wskazują na przewagę nad innymi porównywalnymi algorytmami.

Słowa kluczowe

EN

particle swarm optimization (PSO); quantum-behaved; Lévy flights

PL

optymalizacja rojem cząstek; szeregowanie przepływów magazynowych; loty Lévy'ego

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2013
• Tom: R. 89, nr 1b
• Strony: 138--142
• Opis fizyczny: Bibliogr. 16 poz., schem., tab., wykr.

Twórcy

autor

Li D.

• Anhui Science and Technology University

autor

Deng N.

• Hubei University of Technology

Bibliografia

• [1] Gupta J.N.: A functional heuristic algorithm for the flowshop scheduling problem, Operational Research Quarterly, 22(1971), 39-47
• [2] Koulamas C.: A new constructive heuristic for the flowshop scheduling problem, European Journal of Operational Research, 105(1998), 66-71
• [3] Nawaz M., Enscore E., Ham I.: A Heuristic Algorithm for the m- Machine, n-Job flow-Shop Sequencing Problem, Omega, 11(1983), 91-95
• [4] Tasgetiren M.F., Sevkli M., Liang Y.C., Gencyilmaz G.: Particle Swarm Optimization Algorithm for Permutation Flowshop Sequencing Problem, LNCS, 3172(2004), 366-385
• [5] Yu B., Jiao B., Gu X.: An Improved Cooperative Particle Swarm Optimization and Its Application to Flow Shop Scheduling Problem, Journal of East China University of Science and Technology (Natural Science Edition), 35(2009), 468-474
• [6] Sun J., Feng B., Xu W.B.: Particle Swarm Optimization with Particles Having Quantum Behavior, Proc. Congress on Evolutionary Computation, 325(2004)
• [7] van den Bergh F., Engelbrecht A.P.: A cooperative approach to particle swarm optimization, IEEE Transactions on In Evolutionary Computation, 8(2004), 1-15
• [8] Li D., He Q.: A version of cooperative multi-swarm PSO using electoral mechanism to solve hybrid flow shop scheduling problem , Przeglad Elektrotechniczny, 88(2012), 22-26
• [9] Coelho L.D.S: Novel Gaussian quantum-behaved particle swarm optimiser applied to electromagnetic design, Science, Measurement & Technology, IET 1(2007), 290-294
• [10] Liu J., Sun J., Xu W.B.: Design IIR Digital Filters Using Quantum-Behaved Particle Swarm Optimization, Advances in Natural Computation, LNCS, 4222(2006), 637-640
• [11] Yang X.S.: Engineering Optimization: An Introduction with Metaheuristic Applications, John Wiley and Sons, (2010)
• [12] Zhang J., Zhang C., Liang S.: A diversity-guided particle swarm optimizer-the ARPSO, Expert Systems with Applications, 37(2010), 5827-5834
• [13] Riget J., Vesterstroem J.: A diversity-guided particle swarm optimizer-the ARPSO, Master’s thesis, Department of Computer Science, University of Aarhus, (2002)
• [14] Tasgetiren M.F., Liang Y.C.: A binary particle swarm optimization algorithm for lot sizing problem, Journal of Economic and Social Research, 5(2003), 1-20
• [15] Taillard E.: Benchmarks for basic scheduling problems, European Journal of Operational Research, 64(1993), 278-285
• [16] Lian Z., Gu X., Jiao B. : A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan, Chaos, Solitons & Fractals, 35(2006), 851-861