基于JIT的并行多机问题的病毒进化遗传算法

摘要/Abstract

摘要： 为了解决提高顾客对完工时间满意度的提前/拖期调度问题，提出了一种将病毒进化遗传算法和单机问题的有效算法相结合的求解方法。在该方法中，病毒进化遗传算法采用整数编码，简化了算法的实现难度，提高了算法的执行效率。每个染色体都代表完成零件加工的机器编码的组合，通过病毒种群对主种群的病毒感染，提高了逃脱局部极点的搜索能力。在每一代种群中，调用单机问题的有效算法，使达到用户满意度的零件数最大。数值仿真实验表明，该算法具有收敛速度快、优化效果好等特点，且适合于求解大规模问题。

关键词: 病毒进化遗传算法, 零件排序, 提前/拖期, 并行机

Abstract: In order to solve the earliness-tardiness job scheduling problem of improving customers satisfaction toward completion time, an algorithm combining Virus Evolutionary Genetic Algorithm (VEGA) and single machine problem was presented. In this solution, due to VEGAs adoption of integral coding, it simplified the algorithms accomplishing difficulty and enhanced the algorithms execution efficiency. Each chromosome represented a combination of the machine coding about finished accessory processing, through virus generations infection on the main generation, the searching ability of escaping from the local apices was increased. With each generation, the effective algorithm used for transferring single machine problem has lessened the amount of user satisfactory degree accessory to the maximal scale. Numeric examples demonstrated that the genetic algorithm carrying the property of fast convergence. The solution gained by the genetic algorithm was pretty well.

Key words: virus evolutionary genetic algorithm, job scheduling, earliness and tardiness, parallel machines

中图分类号:

O224

郭海东，黄德才，沈良忠，陈强强. 基于JIT的并行多机问题的病毒进化遗传算法[J]. .

GUO Hai-dong，HUANG De-cai， SHEN Liang-zhong，CHEN Qiang-qiang. Virus evolutionary genetic algorithm for solving a multi-objective job-scheduling problem on paralle[J]. .

参考文献

[1]WU Yue, WANG Dingwei. Single-machine earliness/tardiness schedule problem to maximize the number of satisfied customer[J].Systems Engineering-Theory Methodology Appli cations,1998,7(3):45-49(in Chinese).[吴悦，汪定伟.单机作业极大化顾客满意数的提前/拖期调度问题[J].系统工程理论方法应用，1998,7(3):45-49].

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

[3]LIU Min, WU Cheng. Hybrid genetic algorithm method for identical parallel machine earliness/tardiness[J]. Acta Automatica Sinica,2000,26(2):258-262(in Chinese).[刘民,吴澄. 解决并行多机提前/拖后调度问题的混合遗传算法方法[J]. 自动化学报, 2000,26(2):258-262.]

[4]YAO Weili, YANG Deli, HU Xiangpei. A genetic algorithm for job shop scheduling problem[J].Operations Research and Management Science,1999,8(2):85-88(in Chinese).[姚伟力，杨德礼，胡祥培. 遗传算法对车间作业调度的研究[J]. 运筹与管理，1999,8(2):85-88.]

[5]KUBOTA N, SHIMOJIMA K. The role of virus infection in virus evolutionary genetic algorithm[A].Evolutionary computation[C].Nagoya,Japan：IEEE, 1996.182-187.

[6]HU Shicheng, XU Xiaofei,Zhan Dechen. A virus evolutionary genetic algorithm for large product structure optimization problem[J]. Computer Integrated Manufacturing Systems,2003,9(3):202-205(in Chinese).[胡仕成，徐晓飞，战德臣.大型产品结构问题的病毒进化遗传算法方法[J].计算机集成制造系统,2003,9(3)：202-205.]

[1]	孟荣华,李世红,罗强,饶运清. 基于十进制灰狼优化算法的金属板材切割调度问题[J]. 计算机集成制造系统, 2020, 26(第4): 1011-1018.
[2]	张嘉琦,曹政才,刘民. 融合代理模型和差分进化算法的并行机动态调度方法[J]. 计算机集成制造系统, 2017, 23(第1期): 75-81.
[3]	张博文,陆志强,张岳君. 基于系统可靠性的生产与维护计划联合决策[J]. 计算机集成制造系统, 2015, 21(第8期): 2079-2088.
[4]	杨宏安,王周锋,吕阳阳,席志成,王宏浩. 工序加工时间不确定条件下作业车间调度问题的区间数求解方法[J]. 计算机集成制造系统, 2014, 20(09): 2231-2240.
[5]	张刚志,周炳海+. 带换模约束的非等效并行机作业族调度方法[J]. , 2013, 19(12): 0-0.
[6]	李作成,钱斌,胡蓉,向凤红,车国霖. 求解一类异构并行机调度问题的分布估计算法[J]. 计算机集成制造系统, 2013, 19(09): 2202-2212.
[7]	王圣尧,王凌,许烨. 求解相同并行机混合流水线车间调度问题的分布估计算法[J]. 计算机集成制造系统, 2013, 19(06 ): 1304-1312.
[8]	李海宁,孙树栋,杨宏安. TS/MP混合算法求解作业车间JIT调度问题[J]. , 2012, 18(06): 0-0.
[9]	杨宏安，孙启峰，李锦远. 求解作业车间提前/拖期调度问题的一种新解码方法[J]. , 2011, 17(12): 0-0.
[10]	杨宏安,,孙启峰,,孙树栋,,郭杰,. 基于遗传算法的作业车间提前/拖期调度问题[J]. , 2011, 17(08): 0-0.
[11]	展勇，邱长华，祝海涛. 基于网络流的多并行机可中断开放车间调度算法[J]. , 2011, 17(05): 0-0.
[12]	展勇，邱长华，祝海涛. 基于网络流的多并行机可中断开放车间调度算法[J]. , 2011, 17(05): 0-0.
[13]	曾强,，杨育，王小磊,，文颖. 并行机作业车间等量分批多目标优化调度[J]. , 2011, 17(04): 0-0.
[14]	赵振，刘钢，严隽薇，刘敏+. 基于双线性链表编码的并行机大规模调度遗传算法[J]. , 2011, 17(02): 0-0.
[15]	方叶祥，，曹爱军，李东波+. 锻造多属性有条件相容并行组批优化[J]. , 2010, 16(08): 0-0.