基于JIT的非等同并行多机调度问题的混合遗传算法

摘要/Abstract

摘要： 针对一类NP完全问题的多目标、非等同、并行多机作业调度问题，设计了一个混合遗传算法。该算法在设计过程中针对该问题的特点，设计了一种动态适应度函数；将求解单机问题最优解的有效算法混合在编码方案中，设计了一种不包括作业顺序的简单编码方案，从而降低了算法的实现难度，并提高了执行效率。数值仿真实验表明，该算法具有收敛速度快、优化效果好等特点，适合于求解较大规模的问题。

关键词: 作业调度, 遗传算法, 准时生产

Abstract: A hybrid genetic algorithm (HGA) is presented for the problem of minimizing the range of lateness and make-span on parallel non-identical machines, which is a NP-complete. There are two new method presented for the HGA. Firstly, a dynamic fitness function is introduced according to the requirement of the scheduling problem. Secondly, a simple coding method for the HGA is given. This new coding method does not include the ranking information of job list, and it embeds the optimal effective algorithm for solving the corresponding single machine problem, which makes the HGA easy programming and enhances the efficiency of the HGA. Numerical simulations illustrate that the HGA has the properties of fast convergence, and can be used to solve larger size problems.

Key words: job scheduling, genetic algorithm, JIT

中图分类号:

O224

黄德才，郭海东. 基于JIT的非等同并行多机调度问题的混合遗传算法[J]. .

HUANG De-cai,GUO Hai-dong. Hybrid Genetic Algorithm for Solving Job Scheduling Problem on Non-identical Parallel Machines Based[J]. .

参考文献

[1]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.]

[2]WANG Liping,CAO Liming.Genetic algorithm——theory, application&software implement[M]. Xi’an: Xi’an Jiaotong University Press, 2002(in Chinese ).[王立平，曹立明. 遗传算法——理论、应用与软件实现[M]. 西安：西安交通大学出版社，2002.]

[3]LIU Min,WU Cheng.Hybrid genetic algorithm method for identical parallel machine earliness/tardiness scheduling problem[J]. ACTA Automation 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 jop shop scheduling problem[J]. Operations Research and Management Science,1999,8(2):85-88(in Chinese).[姚伟力，杨德礼，胡祥培. 遗传算法对车间作业调度的研究[J]. 运筹与管理，1999,8(2):85-88.]

[5]ZHOU Zhang,ZHANG Huimin.The genetic algorithm for multi-objective job shop scheduling[J]. Systems Engineering-Thoery&Practice, 2001,21(8):1-5(in Chinese).[周涨，张惠民. 求解多目标作业排序问题的遗传算法[J]. 系统工程理论与实践，2001,21(8):1-5.]

[6]HUANG Decai,QIAN Neng. Generalized model and heuristic algorithm for a class job scheduling problem based on JIT technique[J]. Computer Integrated Manufacturing Systems—CIMS, 1999,5(5):65-68(in Chinese).[黄德才，钱能.基于JIT的一类作业调度问题的一般通用模型及解法[J]. 计算机集成制造系统—CIMS,1999,5(5):65-68.]

[7]GUPTA S，SEN T. Minimizing the range of lateness on a single machine[J]. Jour.Opl. Res.Soc.，1984,35(9):853-859.

[8]HUANG Decai, JING Ling, YANG Wannian. A heuristic algorithm based on JIT technique for scheduling on parallel machines[J]. Computer Integrated Manufacturing Systems—CIMS,1997,3(6):45-48(in Chinese).［黄德才，经玲，杨万年. 一个基于JIT的FMS作业调度问题的模型及解法[J]. 计算机集成制造系统—CIMS, 1997,3(6):45-48.］

[1]	陈年,金涛,王建民. 基于变异反馈的临床路径优化[J]. 计算机集成制造系统, 2021, 27(9): 2556-2564.
[2]	黎英杰,刘建军,陈庆新,毛宁. 多层级装配作业车间等量分批策略与调度算法[J]. 计算机集成制造系统, 2021, 27(8): 2307-2320.
[3]	王文中,张树生,余隋怀,陈登凯. 基于解构·重构思维的潜水器舱室布局优化[J]. 计算机集成制造系统, 2021, 27(7): 2045-2052.
[4]	王勇,周雪,刘永,许茂增. 基于车辆共享的多中心共同配送联盟优化[J]. 计算机集成制造系统, 2021, 27(6): 1820-1832.
[5]	张昊鹏,郭宇,汤鹏洲,黄少华,刘道元,李晗. 基于图像匹配的增强现实装配系统跟踪注册方法[J]. 计算机集成制造系统, 2021, 27(5): 1281-1291.
[6]	胡金昌,刘紫薇,马文凯,吴耀华. 考虑学习效应的单人作业车间多目标调度算法[J]. 计算机集成制造系统, 2021, 27(5): 1361-1370.
[7]	刘俊琦,张则强,王沙沙,曾艳清. 考虑不规则物流交互点的过道布置问题建模与优化[J]. 计算机集成制造系统, 2021, 27(4): 1155-1166.
[8]	裴小兵,李依臻. 新型混合改进遗传算法求解零等待流水车间调度问题[J]. 计算机集成制造系统, 2021, 27(3): 815-827.
[9]	李从东,章志伟,曹策俊,张帆顺. 复杂产品设计变更传播路径的多目标优选[J]. 计算机集成制造系统, 2021, 27(3): 842-856.
[10]	杨小明,徐子奇,金雯,舒帆. 复合拣选策略下堆垛机作业序列优化问题[J]. 计算机集成制造系统, 2021, 27(3): 933-942.
[11]	李丽丽,陈琨,高建民,李辉,冯增行,张建. 采用优化概率神经网络的质量异常识别方法[J]. 计算机集成制造系统, 2021, 27(10): 2813-2821.
[12]	薛玲玲. 作业车间调度的块结构邻域搜索遗传算法[J]. 计算机集成制造系统, 2021, 27(10): 2848-2857.
[13]	罗焕,陈浩杰,宋小欣,张剑. 带有缓存约束的作业车间调度求解方法[J]. 计算机集成制造系统, 2021, 27(10): 2880-2888.
[14]	张韵,钟慧超,张春江,李新宇,丛建臣. 基于机器学习的多策略并行遗传算法[J]. 计算机集成制造系统, 2021, 27(10): 2921-2928.
[15]	狄卫民,王然. 考虑多级设施中断的供应链选址—库存决策模型及优化算法[J]. 计算机集成制造系统, 2021, 27(1): 270-283.