Diversified Particle Swarm Optimization for Hybrid Flowshop Scheduling

Journal of Optimization in Industrial Engineering

مقاله 9، دوره 12، شماره 2، مهر 2019، صفحه 107-119   

نوع مقاله: Original Manuscript

شناسه دیجیتال (DOI): 10.22094/joie.2018.671.1433

نویسنده

Javad Behnamian^*

Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran

چکیده

The aim of this paper is to propose a new particle swarm optimization algorithm to solve a hybrid flowshop scheduling with sequence-dependent setup times problem, which is of great importance in the industrial context. This algorithm is called diversified particle swarm optimization algorithm which is a generalization of particle swarm optimization algorithm and inspired by an anarchic society whose members behave anarchically to improve their situations. Such anarchy lets the algorithm explore the solution space perfectly and prevent falling in the local optimum traps. Besides, for the first time, for the hybrid flowshop, we proposed eight different local search algorithms and incorporate them into the algorithm in order to improve it with the help of systematic changes of the neighborhood structure within a search for minimizing the makespan. The proposed algorithm was tested and the numerical results showe that the proposed algorithm significantly outperforms other effective heuristics recently developed.

کلیدواژه‌ها

Particle Swarm Optimization؛ Scheduling؛ Sequence-dependent؛ Hybrid flowshop

مراجع

Ahmadi-Javid, A. (2011). Anarchic Society Optimization: A Human-Inspired Method. In 2011 IEEE Congress on Evolutionary Computation (CEC), 2586-2592.

Allahverdi, A. (2015). The third comprehensive survey on scheduling problems with setup times/costs, European Journal of Operational Research, 377(2), 345-378.

Behnamian, J. Fatemi Ghomi, S.M.T., & Zandieh, M. (2009). A multi-phase covering Pareto-optimal front method to multi-objective scheduling in a realistic hybrid flowshop using a hybrid metaheuristic. Expert Systems with Applications, 36(8), 11057-11069.

Behnamian, J. Fatemi Ghomi, S.M.T., & Zandieh, M. (2012). Hybrid flowshop scheduling with sequence-dependent setup times by hybridizing max–min ant system, simulated annealing and variable neighborhood search, Expert Systems: The Journal of Knowledge Engineering, 29 (2), 156–169.

Blackwell, T., & Bentley, P.J. (2002). Don’t push me! Collision-avoiding swarms. In: Proceedings of the IEEE congress on evolutionary computation, 1691–96.

Chen, C-C. (2011). Two-layer particle swarm optimization for unconstrained optimization problems, Applied Soft Computing, 11(1), 295–304.

Clerc, M. (2006). Particle swarm optimization. ISTE;

Coelho, L.S. (2008). A quantum particle swarm optimizer with chaotic mutation operator, Chaos, Solitons and Fractals, 37, 1409–1418.

Coelho, L.S. (2009). Reliability–redundancy optimization by means of a chaotic differential evolution approach , Chaos, Solitons & Fractals, 41(2), 594-602

Eberhart, R., & Kennedy, J. (1995). A new optimizer using particle swarm theory. In: Proceedings of the IEEE Sixth International Symposium on Micro Machine and Human Science, 39-43.

El-Abd, M. Hassan, H. Anis, M. Kamel, M.S., & Elmasry, M. (2010). Discrete cooperative particle swarm optimization for FPGA placement. Applied Soft Computing, 284-295.

Gaafar, L.K. Masoud, S.A., & Nassef, A.O. (2008). A particle swarm-based genetic algorithm for scheduling in an agile environment. Computers & Industrial Engineering, 55, 707–720.

García-Villoria, A., & Pastor, R. (2009). Introducing dynamic diversity into a discrete particle swarm optimization, Computers & Operations Research, 36(3), 951-966.

He, S. Wu, Q.H. Wen, J.Y. Saunders, J.R. R.C., & Paton, (2004). A particle swarm optimizer with passive congregation. Biosystems, 78, 135–47.

Jie, J. Zeng, J. Han, C., & Wang, Q. (2008). Knowledge-based cooperative particle swarm optimization. Applied Mathematics and Computation,  205 (2), 861-873.

Jina, Z. Yang, Z., & Ito, T. (2006). Metaheuristic algorithms for the multistage hybrid flowshop scheduling problem. International Journal of Production Economics, 100(2), 322-334.

Johnson, D.S. Aragon, C.R. Mcgeoch, L.A., & Schevon, C. (1989). Optimization by simulated annealing: an experimental evaluation; Part I, graph partitioning, Operations Research, 37(6), 865–892.

Karthi, R.  Arumugam, S., &  Ramesh Kumar, K. (2009). Discrete Particle Swarm Optimization Algorithm for Data Clustering Nature Inspired Cooperative Strategies for Optimization (NICSO 2008).

Koua, X. Liu, S. Zhang, J., & Zheng, W. (2009). Co-evolutionary particle swarm optimization to solve constrained optimization problems. Computers & Mathematics with Applications, 57, 11-12.

Król, D., & Drożdżowski, M. (2010). Use of MaSE methodology and swarm-based metaheuristics to solve the traveling salesman problem. Journal of Intelligent and Fuzzy Systems, 21(3), 221-231.

Kurz, M.E., & Askin, R.G. (2003). Comparing scheduling rules for flexible flow lines. International Journal of Production Economics, 85, 371-388.

Kurz, M.E., & Askin, R.G. (2004). Scheduling flexible flow lines with sequence-dependent setup times. European Journal of Operational Research, 159, 66–82.

Laskari, E.C. Parsopoulos, K.E., & Vrahatis, M.N. (2002). Particle swarm optimization for integer programming. In: Proceedings of the IEEE 2002 Congress on Evolutionary Computation, Honolulu (HI), 1582–1587.

Leon, V.J., & Ramamoorthy, B. (1997). An adaptable problem-space based search method for flexible flow line scheduling. IIE Transactions, 29, 115–125.

 Li, J-Q.,  Pan, Q-K. , & Wang, F-T. (2014). A hybrid variable neighborhood search for solving the hybrid flow shop scheduling problem. Applied Soft Computing, (24), 63–77.

Lozvbjerg, M. Krink, T. (2002). Extending particle swarms with self-organized criticality. In: Proceedings of the IEEE congress on evolutionary computation,1588–93.

Montalvo, I. Izquierdo, J. Pérez, R., & Tung, M.M. (2008). Particle swarm optimization applied to the design of water supply systems. Computers & Mathematics with Applications,  56(3), 769-776.

Naderi, B. Zandieh, M., & Aminnayeri, M. (2011). Incorporating periodic preventive maintenance into flexible flowshop scheduling problems. Applied Soft Computing, 11(2), 2094–2101.

Nawaz, M. Enscore, E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11, 91–95.

Parsopoulos, K.E. Vrahatis, D.K., & Tasoulis, M.N. (2004). Multi-objective optimization using parallel vector evaluated particle swarm optimization. In: Proceedings of the IASTED international conference on artificial intelligence and applications, 2, 823–828.

Parsopoulos, K.E., & Vrahatis, M.N. (2001). Particle swarm optimizer in noisy and continuously changing environments. In: Hamza MH, editor, Artificial intelligence and soft computing, 289–94.

Pinedo, M.L. (2012). Scheduling Theory, Algorithms, and Systems, Fourth Edition, Springer, NY.

Rios-Mercado, R.Z., & Bard, J.F. (1998). Computational experience with a branch-and-cut algorithm for flowshop scheduling with setups. Computers & Operations Research, 25 (5), 351–366.

Ruiz, R., & Stützle, T. (2008). An Iterated Greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives. European Journal of Operational Research, 187(3), 1143–1159.

Sadati, N. Amraee, T., & Ranjbar, A.M. (2009). A global particle swarm- based-simulated annealing technique for undervoltage load shedding problem. Applied Soft Computing, 9(2), 652–657.

Sha, D.Y., & Hs, C-Y. (2006). A hybrid particle swarm optimization for job shop scheduling problem. Computers & Industrial Engineering,  51(4), 791-808

Sun, T-H. (2009). Applying particle swarm optimization algorithm to roundness measurement. Expert Systems with Applications, 36 (2),  3428-3438.

Talbi, El-G. (2009). Metaheuristics: From Design to Implementation, Wiley Series on Parallel and Distributed Computing.

Tang, Y. Qiao, L., & Guan, X. (2010). Identification of Wiener model using step signals and particle swarm optimization. Expert Systems with Applications, 37(4), 3398-3404.

Tseng, C-T., & Liao, C-J. (2008). A particle swarm optimization algorithm for hybrid flow-shop scheduling with multiprocessor tasks. International Journal Of Production Research, 46(17), 4655-4670.

Wang, J. Kuang, Z. Xu, X., & Zhou, Y. (2009). Discrete particle swarm optimization based on estimation of distribution for polygonal approximation problems. Expert Systems with Applications,  36 (5), 9398-9408.

Wang, X., & Tang, L. (2009). A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers. Computers & Operations Research, 36(3), 907–918.

Wang, Y., & Liu, J.H. (2010). Chaotic particle swarm optimization for assembly sequence planning. Robotics and Computer-Integrated Manufacturing,  26(2), 212-222.

Xiang, T. Wong, K-w., & Liao, X. (2007). A novel particle swarm optimizer with time-delay. Applied Mathematics and Computation,  186 (1), 789-793.

Xie, X.F. Zhang, W.J., & Yang, Z.L. (2002). A dissipative particle swarm optimization. In: IEEE congress on evolutionary computation (CEC’02), HI, USA.

Xiong, Y. Cheng, H-Z. Yan, J-Y., & Zhang, L. (2007). New discrete method for particle swarm optimization and its application in transmission network expansion planning. Electric Power Systems Research,  77(3-4), 227-233.

Yang, Y. Xiaoxing, L., & Chunqin, G. (2008). Hybrid particle swarm optimization for multiobjective resource allocation, Journal of Systems Engineering and Electronics,  19(5), 959-964.

Yeh, W-C. Chang, W-W., & Ying Chung, Y. (2009). A new hybrid approach for mining breast cancer pattern using discrete particle swarm optimization and statistical method. Expert Systems with Applications,  36(4), 8204-8211.

Yin, P-Y. (2004). A discrete particle swarm algorithm for optimal polygonal approximation of digital curves, Journal of Visual Communication and Image Representation,  15(2), 241-260.