时间:2024-05-04
曹 睿 侯向盼 金巳婷
(1.大连交通大学 大连 116028)(2.中车青岛四方机车车辆股份有限公司 青岛 266031)(3.沈阳铁路局通信段 沈阳 110001)
在柔性车间调度问题中,每一个部件中的每一道工序不止固定在一台机器上,可根据具体情况选择不同的机器加工,并且不同机器加工的时间有所不同,与传统的车间调度相比更具有灵活性[1]。本次设计利用改进的遗传算法对柔性车间部件生产完工最大时间最短作为性能指标,确立为目标函数,对种群初始化和交叉变异部分进行改进,提高全局的搜索效率,通过实例说明改进的遗传算法对柔性车间的调度优化问题有所改善[2]。
多目标柔性作业车间调度是指生产车间中在m台设备{M1,…Mn}上加工n个工件{1,…N},每个工件包含ni个事先确定加工顺序的工序,每道工序可以在多台设备上加工,每道工序不同的机器加工加工时间有所不同。本文主要考虑最大完工时间最短的性能指标[3],其目标函数的建立如下:
调度目标是为每道工序选择合适的机器、确定每台机器上各个工件工序的最佳加工顺序以及开工时间,使得工件的最大生产周期最短。除此之外,在工件加工过程中还需要满足下面的几个约束条件:1)工件i在机器j上的加工时间需要大于0;2)工件i的加工时间必须在规定时间范围内;3)对于特定的工件i,机器j必须先于机器m对其进行加工;4)任意工件的加工过程必须是连续封闭的[15]。
一个包含3个工件、5台机器的FJSP的问题描述如表1所示。
表1 3个工件、5台机器的柔性车间调度问题
柔性作业车间调度编码由两部分组成:一部分是基于机器分配的编码,对应机器选择子问题,确定所选择的加工机器;另一部分是基于工序的编码,对应工序先后加工的排序子问题,确定工序的先后加工顺序[4]。
以3×5柔性车间调度问题为例说明,第一层对工序顺序进行编码得到的加工序列:O11→O31→O21→O12→O22→O32→O23→O13,第二层编码是基于机器的编码可以获得工序对应的加工机器序列:M1→M3→M2→M3→M4→M5→M1→M2。
第一部分是所有工件加工时间
第二部分是机器在加工工件时的准备时间
表示上一工件结束加工时的拖延时间
根据车间的具体情况,在M个可用机器中选择k台性能优良、加工时间相对较短的机器作为一个小规模的初始群体,求出这k台机器的平均加工时间tA,将剩下的( M-K)台机器的加工时间tP与tA相比较,为保证初始种群的数量,根据实际情况设置一个tP与tA的差异范围Q,即若 |tA-tP|∈Q,则保留,否则,该机器淘汰,这样可以保证初始种群的适应度,提高搜索效率。流程图如图1。
图1 初始化流程图
在遗传算法中,适应度越高,被选择的几率就越大[8]。在本次设计中,将适应度函数表示成目标函数倒数的形式,即
其中min T表示目标函数,即最小生产周期,这样,当生产周期T最小时,适应度函数值最大,就表示这条加工路线的时间最短[6]。
首先将种群内个体按适应度大小从高至低排序,利用最优个体保存法将父代中的最优个体即适应度最高的个体直接保留进入到下一代[7]。
针对FJSP本文提出了两种交叉操作,第一种是POX交叉操作[11],用于染色体中工序的加工顺序的交叉;第二种是节点交叉操作用于染色体工序分配的机器的交叉。
工序染色体的交叉过程:
P1和P2为父代,交叉后产生子代C1和C2。首先将所有的工件分成两个集合J1和J2,子一代的染色体C1/C2继承父代中J1/J2内的工件对应的基因,子一代剩余的部分基因由父代剔除了C1/C2中剩余的基因来补充[9]。
机器染色体的交叉过程:
采用节点交叉法,即将整个染色体的基因串均匀分成三部分,这样在染色体上就会产生两个基因位点,选取每个基因位点两侧相邻的字符组成一个基因段进行交叉,这样既避免了基因交叉分布的不均匀性,又能提高全局搜索效率[14]。
第一部分变异时,在机器染色体基因串中随机选择一个位置,在此工序的机器集中随机选择一个与它不相等的整数,替换当前的基因[10],这样确保得到的解是可行解。
第二部分采用相邻交换变异法,以一定的概率随机选取两个位置的相邻基因串进行交换,与交叉操作类似[13]。
本次设计中,根据实际情况,采用设置最大迭代次数的方式来终止算法的执行[12]。
表2是以6×6的柔性作业车间各工件不同工序加工时间表为例。
表2 6×6柔性作业车间各工件不同工序加工时间
图2 问题收敛曲线图
图3 GA-A迭代曲线图
图4 GA-B迭代曲线图
通过图2两种遗传算法GA-A与GA-B适应度函数的收敛曲线图可知,本次所设计的遗传算法相对于传统算法而言,能够快速收敛,迅速搜索到最优解,且能够克服早熟现象,搜索有效稳定;通过对
遗传算法运行的参数设置如下:种群初始规模S=60,交叉概率Pc=0.8,变异概率Pm=0.01,最大进化代数X=50。将最小生产周期作为适应度函数,并按上述所设置的控制参数,分别基于传统遗传算法(GA-A)与本次所设计的遗传算法(GA-B)对上述实例进行仿真,经过Matlab多次运行仿真后,仿真结果如图2~4所示。比分析图3GA-A与图4GA-B两种算法的迭代仿真图像可知,本次所设计的遗传算法GA-B在30代以内便可收敛至最优解,而传统遗传算法GA-A迭代至70代时才收敛至最优解,说明算法GA-B在解决车间实际生产调度问题时更加有效。
我们致力于保护作者版权,注重分享,被刊用文章因无法核实真实出处,未能及时与作者取得联系,或有版权异议的,请联系管理员,我们会立即处理! 部分文章是来自各大过期杂志,内容仅供学习参考,不准确地方联系删除处理!