当前位置:首页 期刊杂志

混合差分进化算法求解柔性作业车间调度问题①

时间:2024-07-29

宁桂英, 曹敦虔

(1.柳州工学院数理教学部,广西 柳州 545616;2.广西民族大学理学院,广西 南宁 530006)

0 引 言

柔性作业车间调度问题(Flexible Job-shop Scheduling Problem,FJSP)是由Brucker[1]在1990年首次提出的,该问题是传统作业车间调度问题(Job-shop Scheduling Problem,FSP)的延伸和拓展。与传统作业车间调度问题不同的是,在柔性作业车间调度问题中,每个工件有多道工序,每道工序可以选择加工的机床有多台,不同机床加工工序所需要的时间不同,所以柔性作业车间调度问题可以看成是多工件多工序排列在多机器上加工的高维规划问题,是一种复杂的NP-hard问题[2]。该问题更符合企业生产中的实际问题调度的需要,因此,对该问题的研究具有重要的理论意义和应用价值。FJSP问题自提出以来,一直是国内外学者们所关注的热点问题,迄今为止,对该问题已有大量的研究,在众多的研究中,经典的具有代表性的算法有分支界定算法,但该方法的复杂度会随着问题规模的增大而成指数级增长,因此不能满足实际问题的需要。近年来,随着智能算法的兴起,越来越多的学者开始关注用智能算法解决此类问题,并取得了一定的成果,如张超勇等提出了柔性作业车间调度问题的两级遗传算法[3];戴月明等提出了骨干双粒子群算法求解柔性作业车间调度问题[4];吕聪等提出柔性车间调度问题的协作混合帝国算法[5];李帆等提出改进蝙蝠算法柔性作业车间调度问题研究[6];王芳等提出求解柔性流水车间调度问题的高效分布估算算法[7]。在以上的研究中可以发现,学者们开始将用于研究连续性问题的智能算法设计为研究离散型的调度问题,主要考虑对算法的改进和与其他算法的混合以提高算法的局部搜索能力,防止算法限于局部极优。

针对柔性车间调度问题的特点,提出了混合差分进化算法(Hybrid Differential Evolution Algorithm,简称HDEA)求解柔性作业车间调度问题。首先对差分进化算法进行特殊的编码和解码,以适合求解离散型问题;然后在变异的过程中,采用双向变异策略,利用概率值,将遗传算法的变异和差分进化算法的变异有机结合,增强了种群的多样性,防止限于局部极值,利用差分进化算法的变异策略,将全局搜索能力和局部搜索能力进行有效平衡,提高了收敛速度和精度,同时根据问题的特点,采用遗传算法的改进交叉方式,即采用随机变位交叉的方式,在保证生成的新个体是有效解的同时也增加了种群的多样性。对14个经典测试算例和2个实际案例进行了仿真,仿真结果表明,提出的算法在求解柔性车间调度问题时具有良好的性能和较好的计算精度和收敛速度。

1 柔性作业车间调度问题模型

1.1 符号定义

为描述问题的方便,对使用的符号含义作如下说明:

M为可供加工的机器总数目;N为待加工的工件总数目;pi为工件i的工序数;Oij为工件i中的第j道工序;Tijk为第i个工件的第j道工序在机器k上加工时间;Sijk为第i个工件的第j道工序在机器k上开始加工时间;Cijk为第i个工件的第j道工序在机器k上加工结束时间;Ci为每个工件的完工时间;

1.2 柔性作业车间调度问题描述:

所研究的FJSP问题描述为:

N个不同的工件在M台机器上加工,每个工件有pi道工序,每道工序可选择在不同的机器上加工,同一道工序在不同的机器上加工对应时间可以不同,该问题研究的目的是寻找一种合适的调度方案,使最大完工时间(makespan)达到最小,即为每个工件的每道工序选择可加工的机器,同时为每台机器合理安排加工顺序。

对以上问题基于以下假设建立数学模型:

(1)初始时刻所有待加工工件都可被加工,所有机器均可用;

(2)不同工件之间没有加工顺序约束,同一工件中有工序顺序约束;

(3)一道工序只能在可加工的机器中选择一台机器加工,且只能被加工一次;

(4)一台机器在同一时刻只能加工一道工序;

(5)不考虑工序加工过程中被中断情况,不考虑在加工以外的其他耗时。

基于以上假设,建立的数学模型为:

(1)

(2)

Ci=Ci,pi

(3)

Si,(j+1)≥Ci,j

(4)

(5)

Sijk≥Crlk

(6)

其中,式(1)为目标函数,表示使所有工件完工时间的最大值达到最小;式(2)表示工件的最后完工时间是该工件的开始加工时间与实际加工时间之和;式(3)表示工件的最大完工时间是该工件最后一道工序的完成时间;式(4)表示同一工件的工序有顺序要求;式(5)表示一道工序只能在一台机器加工,且只能被加工一次;式(6)表示一台机器在同一时刻只能加工一道工序,其中Crlk表示在机器k上前一工作的完工时间。

2 差分进化混合遗传算法

差分进化算法采用实数编码,操作简单,鲁棒性强,比现存的许多智能算法在收敛速度方面更具竞争力,且已被证明具有很好的全局搜索能力。遗传算法作为一种成熟的智能算法,目前在许多方面已得到广泛应用,而且已取得很好的效果,但在收敛速度上遗传算法不具优势。在遗传算法中,变异算子是遗传算法的主要操作,能增加算法局部搜索能力和种群多样性,因此考虑将遗传算法的变异操作引入差分进化算法中,结合这两种算法的优势,以解决柔性车间调度问题。

2.1 双向变异策略

对基本差分进化算法的变异策略,结合DE/rand/1/bin变异方式和DE/best/1/bin变异方式的特点,提出一种新的变异方式,变异公式为:

vij(t+1)=λxij(t)+(1-λ)xbest,j(t)+

F(xp1,j(t)-xp2,j(t))

(7)

采用这种变异策略,第一:能保证在进化过程中λ由1逐渐线性变化到0,当λ=1时,上式变成DE/rand/1/bin,此时算法具有良好的全局搜索能力;当λ=0时,上式变成DE/best/1/bin,此时算法具有良好的局部搜索能力;第二:标准差分进化算法的变异算子选取[0,1]之间的具体数值,而变异因子F的设置,在进化前期具有较大的变异因子,增加种群多样性,随着进化代数的增加,在进化后期,保留最好解的条件下进行局部搜索,这种自适应的设置大大提高收敛速度和精度。

在提出的算法中,采用双向变异策略,随机确定选择何种变异:首先随机生成一个随机数,当该随机数大于变异概率Pm时,采用(7)式的差分进化变异,否则,采用遗传算法的随机交换两个基因位的变异。

2.2 交叉方式的改进

针对离散型调度问题的特点,借鉴遗传算法交叉的理念,用新的交叉方式,将个体采用随机位交叉的交叉方式,此时对变异后的新群体分成两组进行两两配对,对每一对个体A和B,随机选择一个交叉位r(1≤r≤M), 将两个个体的前r个基因交换。交换过程为了保证个体的有效性,采用下面方法进行:比如要交换A(j)和B(j),则在A中寻找B(j)在A中的位置k,将A(j)和A(k)交换,这实际上是个体内部基因位交换,即工件各工序之间的一个重新排列,保证了个体的有效性。例如:以3工件9工序为例,A和B为交叉前的编码个体,若随机产生的r=3,则交换A和B的前三个元素,因为B的第一个元素是3,对应着A中的第一个3的位置,所以实际交换的是A的第一个和第三个元素,同样的方法交换剩余两个元素,交换后得到新的个体A1如下图所示:

可以看出,对编码A实施交叉,实际上是A内部个体位之间的交换,保证了生成个体的有效性。对B也实施同样的交叉,交换后得到新的个体B1如上图所示。

2.3 编码和解码

根据求解FJSP问题的需要,设置了特殊的编码和解码方式。首先对FJSP的编码分为三个部分:工序编码向量,机器编码向量和时间编码向量。其中工序的编码向量为所有工件工序的总长度之和,由于每道工序所能选择的机器和每台机器对应加工的时间是已知的,所以一旦工序编码确定,根据编码去选择可加工的机器编码,此时对应的时间编码就确定了。在进化过程中,只有工序编码参入变异、交叉操作,机器编码和时间编码不参入进化操作,而是采用贪婪的搜索方式,根据工序编码寻找对应的每个工序可使用的机器编号,而且在选择机器时,总是在可选择机器中选择加工该工序结束时刻最早的,如果有多台可选择机器同时结束加工时间,则选择加工时间最少的机器进行加工,这样减少解码时间,提高了效率。现以3工件3机器为例给出具体的编码和解码方法,每个工件的工序数,加工时间和可加工机器如下表1:

表1 3工件3机器对应加工时间

上表中3工件总共有7道工序。

对应工序编码方式为:

1112233

当工序对应编码选择(7)式进行变异操作后,生成新的个体为

0.150.961.3720.481.671.85

解码方法:

将新生成的个体编码进行升序排列,记录排序后的各分量在原来个体中的位置,再将变异前的个体相应位置上的分量放在排序后的位置上,升序后的个体和对应位置如下表:

0.150.480.961.371.671.8521523674

解码后的个体为:

1211332

这种解码方式保证变异操作之后个体的有效性。

3 差分进化混合遗传算法求解柔性车间调度问题步骤

step1: 设置种群规模M,最大进化代数T,变异概率Pm,选择式(1)为适应度函数,随机生成工序初始编码;

step2: 按照2.1双向变异策略进行变异操作,对依概率选择了(7)式变异后的个体,需要按照2. 3进行解码,解码后与参入遗传算法的随机交换两个基因位变异后的个体一起构成新的种群;

step3: 将step2中新的个体按照2.2进行交叉操作;

step4: 选择:比较交叉后的新个体和原来旧个体的适应度值,选择适应度值较优的进入下一代;

step5: 判断是否达到最大进化代数,若是,则进化终止,输出最优解,否则,转到step2。

4 实例仿真及结果分析

为了测试算法在柔性作业车间调度问题求解中的性能,首先选取 Kacem问题[9]提出的4个基准测试算例,这些算例通常被用来测试算法的性能。规模分别为4×6,8×8,10×10和15×10,其中4×6和8×8是部分柔性问题,4×6有12道工序,8×8有27道工序, 10×10和15×10是全柔性问题,10×10有30道工序,15×10有56道工序。设置种群规模为50,最大进化代数50代,通过实验测试观察:变异概率Pm∈[0.1,0.3]之间的随机数时,算法运行最佳。与比较的文献一致,每个算例独立运行10次,表2给出了10次中算法得到的最优解,并与文献算法所得结果进行了比较。

表2 Kacem问题计算结果与文献结果的比较

从表2可以看出,对被测试的四个问题,前三个算例本文算法都能很快找到最优解,文献[10],[11]最差,对于较大规模的算例四,算法找到结果仅次于文献[5],但收敛速度胜于文献[5],文献[5]进化300代,由于文献[5]未给出更大规模的算例结论,所以也无法再与该算法比较。文献[13]的HGWO算法是目前看来比较好的算法,除了4×6 问题文献[13]没给出结果外,其它两个算例运行结果与本文一样,对于规模较大的问题四,进化50代的结果较文献[13]进化800代的结果优,说明改进后的算法不仅提高了解的质量,还提高了收敛速度。从整体上来看,提出算法在求解中小规模柔性作业车间调度问题上具有一定的优势。图1-图4给出了算法得到的调度甘特图。

图1 4*6问题的调度甘特图

图2 8*8问题的调度甘特图

图3 10*10问题的调度甘特图

图4 15*10问题的调度甘特图

为了进一步测试算法的性能,下面选取了经典的Brandimarte问题[14]测试算例中的MK01-MK10的10个测试数据,这10个算例有全柔性的,也有部分柔性的,现将每个算例独立运行20次,表3给出了算法在20次中找到的最好解,并与遗传算法GA,文献[12]的混合算法,文献[13]的HGWO算法,文献[17]的混合化学反应算法,文献[11]的启发式算法及文献[14]的算法进行了比较,并给出了这10个算例的上、下界[LB,UB],UB参看文献[14]。

表3 Brandimarte问题算例计算结果比较

在表3中:首先,从解的有效性上看,对10个算例,算法找到的最优解都在[LB,UB]内,说明解是有效的;其次,从解的精度上分析,MK06,MK10这两个算例在所有算法中看起来都很难找到理想的解,目前文献[17]的算法在求这两个的解上占优势,与理想最优解偏差分别为24和32,而算法除了在这两个解上略逊于文献[17]和文献[12]外,其余解都优于所有比较的文献解,说明算法求解精度高,鲁棒性强;对于所比较的算法都能找到最优解的MK03和MK08,在进化代数较少的条件下就找到了最优解,说明算法收敛速度快。另外,对于普遍较难优化的MK01,MK02,MK04,MK07,MK09,本文算法都给出了全新的解,是迄今为止找到的最好解,而且MK01, MK04,MK07都找到了文献[14]给出的理论最优解,这进一步说明了算法的有效性和优越性。

为了进一步测试提出算法在解决实际问题中的性能,选取了实际生产中的2个典型案例模型进行计算,其中案例2是一个规模较大的案例,数据也较大。

案例1:假设某汽车发动机厂要对金进行加工,在加工过程中需要加工12个工件,每个工件有三道工序,分别为车、刨和磨,共36道工序,该车间有车床3台、刨床2台,磨床4台,不同机床加工时间参考文献[15]。

案例2:选取具有较大规模的钢铁生产的过程,有12个工件,每个工件有四道工序:炼钢—精炼—连铸—轧制,共要完成48道工序,现有3台炼钢炉、3台精炼炉、2台铸机和2台轧机,各机器的加工时间参考文献[15]。

对这两个实际应用案例,参数设置与前面设置相同,每个案例与所比较文献一样,独立运行10次。表4给出了算法运行10次得到的最好结果及平均值,并与文献中相应的结果进行了比较,图5-图6分别给出了案例1调度甘特图和案例2的进化曲线。

表4 实例1--实例2的计算结果的比较

图5 案例1的甘特图

图6 案例2的进化曲线图

从表4可以看出:对于解决所提的两个实际问题,从解的质量上分析,算法能找到问题的最优解,文献[15]的GA算法对两个问题都没找到最优解,文献[16]对案例1没能找到最优解;从稳定性上分析,在运行10次的平均解上,算法略胜于文献[16] ,对案例2,文献[15]只给出运行一次的解;从收敛速度上分析,文献[15]和[16]找到这两个最优解的进化代数均为10000次代,而算法为50代。因此,在解决实际问题中,所提算法同样具有很好的稳定性和鲁棒性,能够在较少的时间内快速找到问题的最优解。

5 结 语

针对柔性作业车间调度问题的求解特点,从特殊的编码、解码,从变异策略、交叉策略等方面对基本差分进化算法进行了改进,提出了求解柔性作业车间调度问题的差分进化混合遗传算法,用改进后的算法对14个经典测试算例和2个实际应用案例进行了仿真计算,仿真结果表明,提出算法具有很好的稳定性和鲁棒性,在计算性能上也有大大提高,对部分较难优化的经典测试算例给出了新的最优解,说明算法对求解柔性作业车间调度问题具有一定的指导作用,后续工作是进一步提高算法的性能以解决更大规模及多目标生产调度问题。

免责声明

我们致力于保护作者版权,注重分享,被刊用文章因无法核实真实出处,未能及时与作者取得联系,或有版权异议的,请联系管理员,我们会立即处理! 部分文章是来自各大过期杂志,内容仅供学习参考,不准确地方联系删除处理!