Application of Bat Algorithm to Permutation Flow-Shop Scheduling Problem

Abstract

Abstract: Permutation flow-shop scheduling problem (PFSP) is a typical combinatorial optimization problem. It is known that the existing bat algorithm is not suitable for solving discrete problems. To overcome this drawback, a new bat algorithm is proposed by modifying its code design and initialization. Then, the proposed algorithm is applied to the PFSP. The proposed method is tested by using classic scheduling benchmark problems and compared with standard particle swarm algorithm and quantum particle swarm algorithm. Simulation results show that the proposed algorithm outperforms the others.

Key words: bat algorithm, ranked order ralue(ROV) coding;Nawaz-Enscore-Ham (NEH) initialization, permutation flow shop scheduling, particle swarm algorithm

Sheng Xiao-hua, Ye Chun-ming. Application of Bat Algorithm to Permutation Flow-Shop Scheduling Problem[J]. Industrial Engineering Journal , 2013, 16(1): 119-124.

References

［1］Pinedo M. Scheduling: theory, algorithm and system［M］. 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2002. ［2］Garey M R, Johnson D S. Computers and intractability: a guide to the theory of NP-completeness［M］. San Francisco: Freeman, 1979. ［3］王陵，刘波.微粒群优化与生产调度算法［M］.北京：清华大学出版社, 2008:114. ［4］刘长平，叶春明.一种新颖的仿生群智能优化算法：萤火虫算法［J］.计算机应用研究,2011,28(9):3295-3297. Liu Chang-ping, Ye Chun-ming. Novel bioinspired swarm intelligence optimization algorithm：firefly algorithm ［J］. Application Research of Computers,2011,28(9):3295-3297. ［5］夏小威，廖振良.仿生智能算法在突发环境污染事件应急响应中的应用［J］.环境科学与管理,2010,35(12):1-3. Xia Xiao-wei, Liao Zhen-liang. Application of bionic intelligent algorithms on unexpected environmental pollution accident emergency response ［J］. Environmental Science and Management,2010,35(12):1-3. ［6］吕铁鑫，尹文生，朱煜.基于混沌粒子群算法的单台批加工设备调度［J］.机电一体化,2011,17(3):63-66. Lv Tie-xin,Yin Wen-sheng,Zhu Yu. Chaos particle swarm optimization based scheduling for single batch processing machine ［J］.Mechatronics,2011,17(3):63-66. ［7］赵俊生，李跃光，张远平.一种改进的量子蚁群算法及其应用［J］.计算机应用与软件,2010,27(7):133-135. Zhao Jun-sheng, Li Yue-guang,Zhang Yuan-ping. An improved quantum ant colony algorithm and its application ［J］. Computer Applications and Software,2010,27（7）:133-135. 〖HJ2mm〗［8］唐海波，叶春明，张新功.应用模拟植物生长算法求解置换流水车间调度问题［J］.计算机应用研究,2010,27(10):3670-3672. Tang Hai-bo, Ye Chun-ming,Zhang Xin-gong. Plant growth simulation algorithm for permutation flow shop scheduling to minimize makespan ［J］. Applications Research of Computer,2010,27（10）:3670-3672. ［9］蒋维，陈开.一种混合智能算法用于求解含保序约束的JSP［J］.计算机应用与软件,2008,25(12):70-72. Jiang Wei, Chen Kai. A hybird intelligent algorithm for solving JSP with order preserving constraints ［J］. Computer Applications and Software,2008,25（12）:70-72. ［10］程序，吴澄.一种复杂项目调度问题的混合智能算法［J］.计算机集成制造系统,2006,12(4):585-589. Cheng Xu, Wu Cheng. Hybrid algorithm for complex project scheduling ［J］. Computer Integrated Manufacturing Systems,2006,12（4）:585-589. ［11］Yang Xin-She. A new metaheuristic bat-inspired algorithm［C］.Nature Inspired Cooperative Strategies for Optimization.Berlin Heidelberg:Springer Berlin Heidelberg,2010,284:65-74.  ［12］Bean J C. Genetic algorithm and random keys for sequencing and optimization ［J］. ORSA Journal of Computing, 1994, 6(2):154-160. ［13］Nawaz M,Enscore E,Ham I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem ［J］.Omega，1983, 11(1):91-95. ［14］Kennedy J,Eberhart R.Particle swarm optimization ［C］.Proceedings IEEE International Conference Neural Networks. Perth, Australia, 1995:1942-1945. ［15］Sun Jun, Feng Bin, Xu Wenbo. Particle swarm optimization with particles having quantum behavior［C］. Genetic and Evolutionary Computation.Seattle,USA:Springer,2004:19-23. ［16］Taillard E. Benchmarks for basic scheduling problems ［J］. European Journal of Operational Research, 1993,64(2):278-285. ［17］Carlier J. Ordonnancements a contraintes disjonctives ［J］.〖JP3〗RAIRO.Recherche Operationelle/Operations Research,1978,12(4):333-351. ［18］Reeves C R. A genetic algorithm for flowshop sequencing ［J］.Computer Operational Research,1995,22(1):5-13.

[1]	WANG Zhen, GUO Jianquan. Research on Remanufacturing Closed-loop Supply Chain Considering Supply Disruption in Uncertain Environment [J]. Industrial Engineering Journal, 2021, 24(1): 140-146.
[2]	LI Kuimei, ZHENG Bo. A Research on the Route Optimization of Multimodal Transport Considering Comprehensive Transport Cost [J]. Industrial Engineering Journal, 2020, 23(5): 67-74.
[3]	LI Jingfeng, YE Yan, FU Hui . A Research on Dock Assignment and Truck Sequence in a Cross-docking System Considering the Unloading/Loading Sequences of Cargos [J]. Industrial Engineering Journal , 2016, 19(2): 112-120.