蝙蝠算法在PFSP调度问题中的应用研究

摘要/Abstract

摘要： 针对新生的启发式智能算法蝙蝠算法求解离散型生产调度问题存在的局限性，利用对蝙蝠算法重新编码以及初始化的方式来求解离散型生产调度问题。通过对经典的生产调度基准数据进行测试，并同较成熟的标准粒子群算法进行比较。结果表明，蝙蝠算法在解决离散的生产调度问题时，具有较好的优化性能。验证了蝙蝠算法求解离散性问题的有效性以及可行性。

关键词: 蝙蝠算法, ROV编码, NEH初始化, 置换流水车间调度, 粒子群算法

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

盛晓华，叶春明. 蝙蝠算法在PFSP调度问题中的应用研究[J]. 工业工程, 2013, 16(1): 119-124.

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.

参考文献

［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]	王玖河, 刘欢, 高辉. 基于粗糙PSO-BP神经网络的冷链物流服务商选择研究[J]. 工业工程, 2021, 24(2): 10-18.
[2]	李魁梅, 郑波. 考虑综合运输成本的多式联运路径优化问题[J]. 工业工程, 2020, 23(5): 67-74.
[3]	侯艳, 黄康焕, 张亿仙, 伍乃骐. 原油一次加工过程的多目标调度优化[J]. 工业工程, 2020, 23(4): 131-139.
[4]	王玖河, 韩希卓, 时国强. 考虑铁路分割线的物流园区功能区布局规划研究[J]. 工业工程, 2019, 22(5): 102-108.
[5]	蒋革, 冯定忠, 朱伟杭. 基于改进粒子群算法的高效船体分段制造优化[J]. 工业工程, 2018, 21(3): 65-74.
[6]	何立华，马芳丽. 基于混沌差分进化粒子群算法的模糊资源受限项目调度问题[J]. 工业工程, 2016, 19(5): 39-44.
[7]	李敬峰，叶艳，傅惠. 面向货物装卸需求的越库仓门分配和货车排序[J]. 工业工程, 2016, 19(2): 112-120.
[8]	桂达1, 朱海平1, 廖嘉伟1，杨馥铭1, 余志强2. 基于混合算法的飞机多层次装配计划优化及应用[J]. 工业工程, 2015, 18(6): 8-18.
[9]	钮建伟1，秦洁1，丁文英1，温薇1，于洋1，王道平2. 基于资源限制的多目标网络计划优化模型[J]. 工业工程, 2015, 18(6): 116-124.
[10]	刘炳辉，江小云. 切削参数的两阶段优化系统[J]. 工业工程, 2014, 17(6): 30-35.
[11]	彭建良，李仁健，李修琳. 基于混合粒子群算法的群岛泊位分配问题研究[J]. 工业工程, 2014, 17(5): 17-22.
[12]	于小兵1,2. 基于改进粒子群算法的多目标应急物资调度[J]. 工业工程, 2014, 17(3): 18-21.
[13]	胡常伟，陈新度，陈庆新，毛宁，陈新. 含不一致任务重量的同型熔炼炉批调度优化[J]. 工业工程, 2014, 17(3): 73-78.
[14]	郭云涛，宋红艳，白思俊. 粒子群算法在具有迭代关系资源受限项目调度中的应用[J]. 工业工程, 2013, 16(5): 74-78.
[15]	杨琴, 袁玲玲，梁红艳，李金奇，武思. 基于改进粒子群算法的电梯优化调度研究[J]. 工业工程, 2013, 16(2): 141-146.