求解作业车间调度问题的双倍体遗传算法与软件实现

摘要/Abstract

摘要： 作业车间调度问题是最困难的组合优化问题之一，也是计算机集成制造系统中的一个关键环节，在实际生产中具有广泛应用。为此，提出了双倍体遗传算法。该算法提供了一种记忆以前有用的基因块的功能，保留了某些低适应度染色体中的一些局部基因块，构成最优解中的基因片段，提高遗传算法的适应能力。与已有算法相比，基于双倍体遗传算法的作业车间调度方法，显著提高了搜索效率，改进了收敛性能。

关键词: 生产调度, 作业车间调度, 遗传算法, 组合优化

Abstract: Job-shop Scheduling Problem (JSP) is one of the most difficult combinatorial optimization problems. It is one of the most important links on CIMS and widely applied to the engineering. This paper proposes a double chromosomes genetic algorithm for job-shop scheduling problems. Because the function remembering the useful gene pieces is provided, and some gene pieces of chromosomes with lower fitness to form the gene pieces of optimal solution are kept, the adaptation of algorithm is increased. Compared with the existing algorithms, the efficiency of search is increased and the convergence is improved with the double chromosomes genetic algorithm.

Key words: production scheduling, job-shop scheduling, genetic algorithm, combinatorial optimization

中图分类号:

TP273

王万良，宋毅，吴启迪. 求解作业车间调度问题的双倍体遗传算法与软件实现[J]. .

WANG Wan-liang, SONG Yi, WU Qi-di. Double Chromosomes Genetic Algorithm and Its Realization for Job-shop Scheduling Problems[J]. .

参考文献

[1]WU Cheng. The theoretical background of contemporary integrated manufacturing systems: one type of complexity problems and its solution[J]. Computer Integrated Manufacturing Systems—CIMS, 2001,7(3):1-7(in Chinese). [吴澄.现代集成制造系统的理论基础——一类复杂性问题及其求解［J］.计算机集成制造系统—CIMS，2001,7(3):1-7.]

[2]YIN Wenjun, LIU Min, WU Cheng. Current status and prospect of evolutionary computation applied to production scheduling[J]. Computer Integrated Manufacturing Systems—CIMS, 2001,7(12)：1-6(in Chinese).[尹文君，刘民，吴澄.进化计算在生产线调度研究中的现状与展望[J].计算机集成制造系统—CIMS,2001,7(12):1-6.]

[3]WANG Wanliang, YANG Xudong, WU Qidi.Fuzzy scheduling model based on customer’s satisfactory degree and its application[J]. Information and Control, 2001, 30(4):301-304(in Chinese).[王万良，杨旭东，吴启迪.基于客户满意度的模糊调度模型及其应用［J］.信息与控制，2001,30(4):301-304.]

[4]WANG Wanliang, YAO Minghai, WU Yungao, WU Qidi.Hybrid flow-shop scheduling approach based on genetic algorithm[J].Journal of System Simulation, 2002, 14(7):863-865(in Chinese).[王万良，姚明海，吴云高，吴启迪. 基于遗传算法的混合Flow-shop调度方法[J]. 系统仿真学报，2002, 14(7):863-865.]

[5]WANG Wanliang, WU Qidi,XU Xinli. Hopfield neural network approach for job-shop scheduling problems[J].Acta Automatica Sinica, 2002, 28(5):838-844(in Chinese).[王万良，吴启迪，徐新黎. 基于Hopfield神经网络的作业车间生产调度方法[J]. 自动化学报, 2002, 28(5):838-844.]

[6]LI Xiu, LIU Wenhuang, JIANG Chengyu, WANG Ningsheng. The solving of job-shop scheduling problem based on genetic algorithm[J].Journal of System Simulation,2001,13(6):58-68(in Chinese).[李秀，刘文煌，姜澄宇，王宁生.用遗传算法解决生产线调度job-shop问题[J].系统仿真学报,2001,13(6):58-68.]

[7]FANG Jian, XI Yugeng. Agenetic-based algorithm for static job shop scheduling[J]. Journal of Shanghai Jiaotong University，1997,31(3):49-52(in Chinese).[方剑,席裕庚.基于遗传算法的Job Shop静态调度算法[J]. 上海交通大学学报, 1997,31(3):49-52.]

[8]CHENG R, GEN M, TSUJIMURA Y. A tutorial survey of job-shop scheduling problems using genetic algorithms-I［J］.Representation, Computers & Industrial Engineering,1996,30(4):983-997.

[9]CROCE F,TADEI R，VOLTA G.A genetic algorithm for the job-shop problem［J］.Computers and Operations Research, 1995, 22(1):15-24.

[10]GEN Mitsuo, CHENG Runwei.Genetic algorithms and engineering design［M］. New York：John Wiley & Sons,1996.

[1]	陈年,金涛,王建民. 基于变异反馈的临床路径优化[J]. 计算机集成制造系统, 2021, 27(9): 2556-2564.
[2]	秦旋,房子涵,张赵鑫. 考虑资源约束的预制构件多目标生产调度优化[J]. 计算机集成制造系统, 2021, 27(8): 2248-2259.
[3]	黎英杰,刘建军,陈庆新,毛宁. 多层级装配作业车间等量分批策略与调度算法[J]. 计算机集成制造系统, 2021, 27(8): 2307-2320.
[4]	王文中,张树生,余隋怀,陈登凯. 基于解构·重构思维的潜水器舱室布局优化[J]. 计算机集成制造系统, 2021, 27(7): 2045-2052.
[5]	郭羽含,于俊宇,刘万军,张宇,张美琪. 制造业可持续供应链网络建模及求解[J]. 计算机集成制造系统, 2021, 27(7): 2112-2133.
[6]	杨艳华,姚立纲. 基于时间递推建模及交叉熵算法求解柔性作业车间调度问题[J]. 计算机集成制造系统, 2021, 27(6): 1703-1713.
[7]	段建国,李豪晨,张青雷. 面向绿色制造的半组合式船用曲轴结构件生产车间多目标调度优化[J]. 计算机集成制造系统, 2021, 27(6): 1714-1727.
[8]	王勇,周雪,刘永,许茂增. 基于车辆共享的多中心共同配送联盟优化[J]. 计算机集成制造系统, 2021, 27(6): 1820-1832.
[9]	张昊鹏,郭宇,汤鹏洲,黄少华,刘道元,李晗. 基于图像匹配的增强现实装配系统跟踪注册方法[J]. 计算机集成制造系统, 2021, 27(5): 1281-1291.
[10]	马丽萌,乔非,马玉敏,刘鹃. 基于SO-GP的智能车间组合调度规则挖掘[J]. 计算机集成制造系统, 2021, 27(5): 1351-1360.
[11]	胡金昌,刘紫薇,马文凯,吴耀华. 考虑学习效应的单人作业车间多目标调度算法[J]. 计算机集成制造系统, 2021, 27(5): 1361-1370.
[12]	刘俊琦,张则强,王沙沙,曾艳清. 考虑不规则物流交互点的过道布置问题建模与优化[J]. 计算机集成制造系统, 2021, 27(4): 1155-1166.
[13]	裴小兵,李依臻. 新型混合改进遗传算法求解零等待流水车间调度问题[J]. 计算机集成制造系统, 2021, 27(3): 815-827.
[14]	李从东,章志伟,曹策俊,张帆顺. 复杂产品设计变更传播路径的多目标优选[J]. 计算机集成制造系统, 2021, 27(3): 842-856.
[15]	杨小明,徐子奇,金雯,舒帆. 复合拣选策略下堆垛机作业序列优化问题[J]. 计算机集成制造系统, 2021, 27(3): 933-942.