An Effective Hybrid Particle Swarm Optimization with Decline Disturbance Index for Expanded Job-shop Scheduling Problem

• Autorzy: Zhao F. , Tang J. , Zou J. , Di J.

Warianty tytułu

PL

Efektywna hybrydowa optymalizacja algorytmu mrówkowego z indeksem DD (Decline Disturbane) do rozwiązywania problemu EJSSP (Expanded Job-shop Scheduling Problem

• Języki publikacji: EN

Abstrakty

EN

In this paper, an improved particle swarm optimization with decline disturbance index (DDPSO), is proposed for expanded job-shop scheduling problem (EJSSP). To balance the exploration and exploitation abilities of DDPSO, both PSO-based global search and an adaptive local search are designed and applied simultaneously in the proposed DDPSO. An index was added when the velocity of the particle is prone to stagnation in the middle and later evolution periods. The modification improves the ability of particles to explore the global and local optimization solutions, and reduces the probability of being trapped into the local optima. Theoretical analysis, which is based on stochastic processes, proves that the trajectory of particle is a Markov processes and DDPSO algorithm converges to the global optimal solution with mean square merit. After the exploration based on DDPSO, neighborhood search strategy is used in a local search and an adaptive Meta-Lamarckian strategy is employed to dynamically decide which neighborhood should be selected to stress exploitation in each generation. Simulation results and comparisons with typical algorithms show the effectiveness and robustness of the proposed DDPSO.

PL

Opisano ulepszony al;gorytm mrówkowy z indeksem DDPSO do rozwiązywania problemu EJSSP (expanded job-shop scheduling problem). Dodano indeks kiedy szybkość cząstki jest podatna na stagnację w środku i końcowej części procesu ewolucji. Analiza teoretyczna bazująca na ;procesach stochastycznych dowodzi że trajektoria cząstki jest procesem Markova i algorytm DDPSO pokrywa się z rozwiązaniem globalnego optimum metodą średniokwadratową.

Słowa kluczowe

EN

particle swarm optimization (PSO); expanded Job shop scheduling problem; decline disturbance

PL

algorytm mrówkowy; EJSSP

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2012
• Tom: R. 88, nr 1b
• Strony: 34--38
• Opis fizyczny: Bibliogr. 32 poz., tab.

Twórcy

autor

Zhao F.

autor

Tang J.

autor

Zou J.

autor

Di J.

• School of Computer and Communication, Lanzhou University of Technology, Lanzhou, Gansu, China,

Bibliografia

• [1] J. Q. Fu, C. M. Ye, J. H. Xie, etc., “Research of improved hybrid quantum algorithm in job shop scheduling problems”, Computer Engineering and Applications, vol.45, No.30, pp48- 52, October 2009.
• [2] B. Cai, F. Mao, L. Fu, etc., “Hybrid algorithm of particle swarm optimization and stimulated annealing for job-shop scheduling”, Application Research of Computers, vol.27, No.3, pp856-859, 2010.
• [3] H. B. Yu, L. Wei, “Neural network and genetic algorithm-based hybrid approach to expanded job-shop scheduling”, Computers & Industrial Engineering, vol.39, pp337-356, 2001.
• [4] G. Chryssolouris, V. Subramaniam, “Dynamic scheduling of manufacturing job shops using extreme value theory”, Production Planning & Control, vol.11, No.2, pp122-132, 2000. 38 PRZEGLĄD ELEKTROTECHNICZNY (Electrical Review), ISSN 0033-2097, R. 88 NR 1b/2012
• [5] J. S. Smith, B. A. Peters, A. Srinivasan, “Job shop scheduling considering material handling”, International Journal of Production Research, vol.37, No.7, pp1541-1560, 1999.
• [6] N. Zribi, I. Kacem, A. EI Kamel, etc., “Assignment and scheduling in flexible job-shops by hierarchical optimization”, IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews, vol.37, pp652-661, 2007.
• [7] F. Ghedjati, “Heuristics and a hybrid meta-heuristic for a generalized job-shop scheduling problem”, IEEE Congress on Evolutionary Computation, pp1-8, July 2010.
• [8] I. Gonzalez-Rodriguez, J. J. Palacios, C. R. Vela, etc., “Heuristic local search for fuzzy open shop scheduling”, 2010 IEEE International Conference on Fuzzy Systems, pp1-8, 2010.
• [9] R. Zhang, C. Wu, “A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective”, vol.38, No.5, pp854-867, 2011.
• [10] C. Y. Zhang, P. G. Li, Z. L. Guan, etc., “A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem”, Computers and Operations Research, vol.34, pp3229-3242, 2007.
• [11] A. Baykasoglu, L. Ozbakir, A. I. Sonmez, “Using multiple objective tabu search and grammars to model and solve multiobjective flexible job shop scheduling problems”, Journal of Intelligent Manufacturing, vol.15, No.6, pp777-785, 2004.
• [12] M. Sakawa, R. Kubota, “Two-objective fuzzy job shop scheduling through genetic algorithm”, Electronics and Communications in Japan Part Iii-Fundamental Electronic Science, vol.84, No.4, pp60-68, 2001.
• [13] L. De Giovanni, F. Pezzella, “An Improved Genetic Algorithm for the Distributed and Flexible Job-shop Scheduling problem”, European Journal of Operational Research, vol.200, No.2, pp395-408, 2010.
• [14] J. A. Vazquez-Rodriguez, S. Petrovic, “A new dispatching rule based genetic algorithm for the multi-objective job shop problem”, Journal of Heuristics, vol.16, No.6, pp771-793, 2010.
• [15] C. Gutierrez, I. Garcia-Magarino, “Modular design of a hybrid genetic algorithm for a flexible job-shop scheduling problem”, Knowledge-Based Systems, vol.24, No.1, pp102-112, 2011.
• [16] D. Y. Sha, C. Y. Hsu, “A hybrid particle swarm optimization for job shop scheduling problem”, Computers and Industrial Engineering, vol.51, pp791-808, 2006.
• [17] D. Y. Sha, L. Hsing-Hung, “A multi-objective PSO for job-shop scheduling problems”, Expert Systems with Applications , vol.37, No.2, pp1065-1070, 2010.
• [18] F. Q. Zhao, Y. Hong, D. M. Yu, etc., “A hybrid particle swarm optimisation algorithm and fuzzy logic for process planning and production scheduling integration in holonic manufacturing systems”, International Journal of Computer Integrated Manufacturing, vol.23, No.1, pp20-39, 2010.
• [19] Y. W. Guo, W. D. Li, A. R. Mileham, etc., “Optimisation of integrated process planning and scheduling using a particle swarm optimisation approach”, International Journal of Production Research, vol.47, No.14, pp3775-3796, 2009.
• [20] G. H. Zhang, X. Y. Shao, P. G. Li, etc., “An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem”, Computers & Industrial Engineering, vol.56, No.4, pp1309-1318, 2009.
• [21] A. Manikas, Y.L. Chang, “A scatter search approach to sequence-dependent setup times job shop scheduling”, International Journal of Production Research, vol.47, No.18, pp5217-5236, 2009.
• [22] M. Saravanan, A. N. Haq, “A scatter search algorithm for scheduling optimisation of job shop problems”, International Journal of Product Development, vol.10, No.1-3, pp259-272, 2010.
• [23] C. Y. Peng, L. Gao, X. Y. Shao, etc., “General particle swarm optimization algorithm for job-shop scheduling problem”, Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems, CIMS, vol.12, No.6, pp911-917+923, 2006.
• [24] G. G. Yen, B. Ivers, “Job shop scheduling optimization through multiple independent particle swarms”, International Journal of Intelligent Computing and Cybernetics, vol.2, pp5-33, 2009.
• [25] B. Ivers, G. G. Yen, “Job shop optimization through multiple independent particle swarms”, in 2007 IEEE Congress on Evolutionary Computation, September 25, 2007 - September 28, 2007. Singapore: Inst. of Elec. and Elec. Eng. Computer Society, 2008.
• [26] A. Gomez, R. Cuevas, D. De La Fuete, etc., “New metaheuristic for the Job Shop Scheduling Problem with PSO”, in 2008 International Conference on Artificial Intelligence, ICAI 2008 and 2008 International Conference on Machine Learning; Models, Technologies and Applications, MLMTA 2008, July 14, 2008 - July 17, 2008. Las Vegas, NV, United states: CSREA Press, 2008.
• [27] M. R. Chen, X. Li, X. Zhang, etc., “A novel particle swarm optimizer hybridized with extremal optimization”, Applied Soft Computing, vol.10, No.2, pp367-373, 2010.
• [28] L. dos Santos Coelho, “Gaussian quantum-behaved particle swarm optimization approaches for constrained engineering design problems”, Expert Systems with Applications, vol.37, No.2, pp1676-1683, 2010.
• [29] K. Mahadevan, P. S. Kannan, “Comprehensive learning particle swarm optimization for reactive power dispatch”, Applied Soft Computing, vol.10, No.2, pp641-652, 2010.
• [30] R. C. Eberhart, Y. Shi, “Comparing inertia weights and constriction factors in particle swarm optimization”, in Proceedings of the 2000 Congress on Evolutionary Computation CEC 00, July 16, 2000 - July 19, 2000. California, CA, USA: IEEE, 2000.
• [31] Y. S. Ong, A. J. Keane, “Meta-Lamarckian learning in memetic algorithms”, IEEE Transactions on Evolutionary Computation, vol.8, No.2, pp99-110, 2004.
• [32] W. J. Xia, Z. M. Wu, “A hybrid particle swarm optimization approach for the job-shop scheduling problem”, The International Journal of Advanced Manufacturing Technology, vol.29, No.3-4, pp360-366, 2006.