面向柔性作业调度问题的启发性规则改进遗传算法

摘要/Abstract

摘要： 对柔性作业调度问题，提出了一种启发性规则的改进遗传求解方法，此方法从启发性规则出发产生初始调度解。通过对初始调度解进行比较而产生初始种群。对初始种群通过启发规则的改进遗传算法进行优化计算, 对染色体进行交叉、变异、交换和选择操作,应用启发式规则搜索关键工序并提高关键工序的交换、变异操作概率，在变异操作中利用启发式规则对变异过程加以引导，从而得到优化解。将此方法运用于一系列典型柔性调度问题进行了实验求解，并将求解结果与其他的计算方法进行了比较，表明此方法能提高求解效率，适合复杂的柔性作业调度问题求解。

关键词: 柔性作业调度, 启发式规则, 遗传算法

Abstract: The flexible job-shop scheduling problem (FJSP) is addressed and a hybrid genetic algorithm (GA) is proposed to solve this problem. A heuristic is used to create a set of relatively good schedules for the problem, from which the initial population is created by selecting the relatively good ones. Furthermore, priority rules are integrated into crossover, mutation, exchange, and selection to avoid that it converges to a local optimum. In this way, a better solution can be obtained. Benchmark FJSPs are used to test the proposed method and comparison with some existing approaches is done. Results show that it is effective and efficient for solving FJSPs.

Key words: flexible job-shop scheduling problem, heuristic, genetic algorithm

帅旗1，2, 姚锡凡2. 面向柔性作业调度问题的启发性规则改进遗传算法[J]. 工业工程, 2013, 16(1): 31-37.

Shuai Qi1,2, Yao Xi-fan2. A Hybrid Genetic Algorithm for Flexible Job-Shop Scheduling Problem[J]. Industrial Engineering Journal , 2013, 16(1): 31-37.

参考文献

［1］Zhang G H, Xin Y S. An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem［J］. Computers & Industrial Engineering, 2009,56(4): 1309-1318. ［2］Zhao H J, Hua P C, Jun T. An improved particle swarm optimization for multi-objective flexible job-shop scheduling problem［C］. Proceedings of 2007 IEEE International Conference on Grey Systems and Intelligent Services.Nanjing:IEEE,2007:1587-1592.  ［3］吴秀丽, 李苏剑. 柔性作业车间多品种小批量调度算法研究［J］. 中国机械工程，2010，21（4）:425-429. Wu Xiu-li, Li Su-jian. Research on batch scheduling problem in a flexible job shop［J］. China Mechanical Engineering，2010，21(4）:425-429. ［4］刘琼, 张超勇. 改进遗传算法解决柔性作业车间调度问题［J］. 工业工程与管理, 2009, 14( 2) : 59-66. Liu Qiong, Zhang Chao-yong. Flexible job-shop scheduling problem with improved genetic algorithm［J］. Industrial Engineering and Management, 2009, 14( 2) : 59-66. ［5］苏春, 王大侠. 基于改进遗传算法的偏柔性作业车间调度［J］. 工业工程, 2010,10(6): 61-65. Su Chun, Wang Da-xia. An improved genetic algorithm for partial flexible job-shop scheduling［J］. Industrial Engineering Journal, 2010,10(6): 61-65. ［6］Ju Q Y, Zhu J Y. Multi-objective flexible Job Shop scheduling of batch production［J］. Chinese Journal of Mechanical Engineering, 2007, 43 ( 8 ):148-154. ［7］晏鹏宇 ,车阿大,李鹏. 具有柔性加工时间的机器人制造单元调度问题改进遗传算法［J］. 计算机集成制造系统, 2010,16(2):404-410. Yan Peng-yu, Che A-da, Li Peng. Improved genetic algorithm for robotic cell scheduling problem with flexible processing times［J］. Computer Integrated Manufacturing Systems, 2010,16(2):404-410. ［8］Xia, W J, Wu Z M. An effective hybrid optimization approach for Multi-objective flexible job-shop scheduling problems［J］. Computers and Industrial Engineering, 2005, 48 (2): 409-425. ［9］白俊杰,龚毅光,王宁生. 多目标柔性作业车间分批优化调度［J］. 计算机集成制造系统, 2010，16（2）:397-403. Bai Jun-jie, Gong Yi-guang, Wang Ning-sheng. Multi-objective flexible Job Shop scheduling with lot-splitting［J］. Computer Integrated Manufacturing Systems, 2010，16（2）:397-403.〖ZK)〗 ［10］牛群, 顾幸生. 基于启发式规则的新型进化算法在流水车间调度中的应用［J］.华东理工大学学报,2006,32(12):1472-1477. Niu Qun, Gu Xing-sheng. An improved evolutionary algorithm based on heuristic rules for flow shop scheduling［J］. Journal of East China University of Science and Technology, 2006,32(12):1472-1477. ［11］肖志娇,常会友,衣杨.启发式规则与GA结合的优化方法求解工作流动态调度优化问题［J］.计算机科学，2007，34（2）：157-161。 Xiao Zhi-jiao, Chang Hui-you Yi Yang. An optimization method of workflow dynamic scheduling based on heuristic GA［J］. Computer Science, 2007，34（2）：157-161。 ［12］Kacem I, Hammadi S, Borne P. Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems［J］. IEEE transactions on systems, man, and cybernetics, Part C, 2002, 32(1): 1-13. ［13］Horn J, Nafpliotis N. A niched Pareto genetic algorithm for multi-objective optimization ［J］. Evolutionary Computation,1994,27(1):82-87. ［14］Murata T, Ishibuchi H, Tanaka H. Genetic algorithms for flow shop scheduling problem［J］. Computers & Industrial Engineering,1996,30(4):1061-1071. ［15］Kacem I，Hammadi S，Borne P. Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic［J］.Mathematics and Computers in Simulation,2002,60(3):245-276.

[1]	张正敏, 管在林, 岳磊. 基于Lévy Flight的混合GA在柔性作业车间调度问题中的性能分析[J]. 工业工程, 2021, 24(4): 83-92.
[2]	王晓军, 王博, 晋民杰, 杨春霞, 白新利. 改进多种群遗传算法的AutoStore系统多AGV调度优化[J]. 工业工程, 2021, 24(4): 112-118,167.
[3]	王莹莹, 吴立云. 基于改进NSGA-II的多项目多技能人力资源调度研究[J]. 工业工程, 2021, 24(3): 130-138.
[4]	曾创锋, 刘建军, 陈庆新, 毛宁. 求解一类无关并行机调度的遗传迭代贪心算法[J]. 工业工程, 2021, 24(2): 110-118.
[5]	黄露, 纪延光. 考虑顾客延误损失的配送中心选址双层规划问题研究[J]. 工业工程, 2021, 24(2): 141-147.
[6]	王冰怡, 张锦. 考虑网点共享与变更的多级快递网点选址问题[J]. 工业工程, 2021, 24(2): 155-165.
[7]	马跃如, 文铮, 易丹. 考虑老年人满意度的多目标居家养老护理员路径优化[J]. 工业工程, 2021, 24(1): 74-81,103.
[8]	王玖河, 高辉, 刘欢. 基于遗传算法的共享助力车调度问题研究[J]. 工业工程, 2021, 24(1): 90-96.
[9]	吴斌, 宋琰, 程晶, 董敏. 基于密度峰值聚类的VRPTW问题研究[J]. 工业工程, 2020, 23(5): 58-66,74.
[10]	王苏林, 邱菲尔, 陈凡, 刘川昆, 鹿腾, 王芷芸. 基于贪心遗传的地下物流节点选择规划研究[J]. 工业工程, 2020, 23(5): 88-95.
[11]	侯艳, 黄康焕, 张亿仙, 伍乃骐. 原油一次加工过程的多目标调度优化[J]. 工业工程, 2020, 23(4): 131-139.
[12]	王泽, 杨信丰, 刘兰芬. 考虑电量消耗的车辆调度优化研究[J]. 工业工程, 2020, 23(4): 140-147.
[13]	曾垂飞, 刘建军, 陈庆新, 毛宁. 装配作业车间分批调度问题的算法对比[J]. 工业工程, 2020, 23(4): 174-182.
[14]	张巍, 李鹏翔, 仝自强, 岳毅蒙. 基于损坏车辆分布预测与损益阈值分析下的共享单车回收研究[J]. 工业工程, 2020, 23(3): 132-137.
[15]	张国辉, 胡一凡, 孙靖贺. 改进遗传算法求解多时间约束的柔性作业车间调度问题[J]. 工业工程, 2020, 23(2): 19-25,48.