信息与控制
INFORMATION AND CONTROL
1999年 第28卷 第6期 Vol.28 No.6 1999



进化算法在job-shop调度问题中的应用研究

翁妙凤 王　直
　　摘　要：研究了应用进化算法(遗传算法(GA)和进化规划(EP))以及混合模拟退火进化算法(SAGA和SAEP)求解job-shop调度问题．仿真实验结果表明这四种算法是可行的．文中最后对它们的优劣作了比较．
　　关键词：进化算法，模拟退火法，调度问题
　　中图分类号：TP18　　　　　　文献标识码：B
A STUDY ON APPLICATION OF EVOLUTIONARY ALGORITHMS TO
JOB-SHOP SCHEDULING PROBLEMS
WENG Miao-feng WANG Zhi
(East China Shipbuilding Institute, Zhenjiang 212003)
Abstract:The improved methods solving job-shop scheduling problems using evolutionary algorithms (GA and EP) and combined evolutionary algorithms with simulated annealing algorithm (SAGA and SAEP) are discribed in this paper. Comuputer simulated results show that the four methods are possible. In the end, a comparison for their efficiency is presented.
　　Key words:evolutionary algorithms, simulated annealing algorithm, scheduling problem
1　引言
　　进化算法(遗传算法(GA)和进化规划(EP))以及混合模拟退火进化算法(SAGA和SAEP)是求解job-shop调度问题(JSP)的有效方法．四种算法均采用了统一简单的二维矩阵编码,使遗传操作在基因的移动区内进行基因交换,故算法的收敛速度非常快(见仿真)．
2　问题的描述
　　JSP的目标是,n个工件在m台机器上的加工路线不同,如何安排每台机器上工件的加工顺序,在满足不超期交货的条件下,使得n个工件总的完工时间最小．JSP的约束条件如下：
　　(1)设n个工件分成r类：J={J1, J2,…, Jn}, Ji∈[1, r]；每类工件的操作顺序不同．(2) m台机器M={M1, M2, …, Mm}各自能加工的操作不全相同且完成相同操作的加工时间也不相同．(3)机器加工各操作所需的安装时间与此机器前一加工操作有关．文中的安装时间是指刀具更换时间．(4)当机器最初和加工结束后处于空闲等待状态时,视为0操作；空闲等待时可以先更换刀具．(5)每类工件有各自的交货期限要求．(6)工件在零时刻都可得,且不考虑当加工完工件的每一操作放入相应缓冲区中的时间．
3　JSP的进化算法(GA和EP)实现
3.1 染色体(个体)的表示
　　GA和EP的染色体(个体)均用二维矩阵S=[sij]m×l表示,基因sij=0,1,…,l；其中m表示机器数, l表示n个工件的总操作数．任一非零矩阵元素(称非零元素)值均不相等,其表示n个工件的所有工序统一编号．如文中的仿真实例,将10个工件的总33个工序统一编号(见表1), l则等于33．在S中,无用零矩阵元素(称零元素)都在行右：即siki≠0，有siu=0(i=1,2,…,m;u=ki+1,…,l),(di为S中第i行上的非零元素个数)．
表1 10个工件的总33个工序统一编号表

123456789101112131415161718192021222324252627282930313233
A1C1B1D1A2C2B2D2A3C3B3D3B4D4E4B5D5E5B6D6E6B7A7F7B8A8F8B9A9F9B10A10F10

　　(注：表中字母A～F表示操作类型，其右上角数字表示工件号)
　　染色体(个体)满足可行解的约束条件为 ①机器约束：每一操作(非零元素)必须在可供使用的机器上加工．②操作顺序约束：对任一工件,其第1个工序在矩阵中的列号小于第2个工序的列号,中间工序的列号大于前一工序的列号而小于后一工序的列号,最后工序的列号大于前一工序的列号(文中所述工序次序,皆指同一工件而言)．
　　设sij, skf(j≠f)为一工件的二个工序．当sij-1=0时,称sij有空闲等待；当skf=sij－1且f＜j时,称skf为sij的前一工序；当skf=sij+1且f＞j时,称skf为sij的后一工序．
3.2 GA和EP的初始群体设定
　　(1)先给任一个体矩阵S置零,然后按如下步骤随机给l个矩阵元素置不同(1～l)的整数值,且满足可行解的约束条件：
for p:=1 to l do
　　{查表(如查表1)判p在工件中的工序次序；如果p是第1个工序则{根据p的操作类型,随机产生可供使用的行号(机器)i并在(1, 10)内随机产生列号j,置sij:=p},否则(即p为中间工序或最后工序){根据p的操作类型,随机产生可供使用的行号(机器)k,并在S中找到p的前一工序的列号g,在[g+1,l]中随机产生一列号f(g+1≤f≤l), 置skf:=p}}．
　　在建立初始群体时,由于顺序将1到l个工序给个体的基因置初值,每个工序的后一工序必定在该工序之后出现,故不必找后一工序的列号．
　　(2)通过立体搜索,前移个体矩阵中的非零元素
　　对个体矩阵S逐行(行号i从1到(i+1) mod m)逐列(列号j从1或断点到l)扫描非零元素sij,若sij是第1个工序则前移到本行的第1个零元素处(互换)并置前移标志,否则{判工序sij的前一工序(sij-1)是否前移过，若前移过则由j向左找(sij-1) 的列号f(f＜j),将sij前移到i行f列后的第1个零元素处(互换)；若(sij－1)未前移过则把sij作断点,扫描下一行},…直到S中的l个非零元素全部前移,而无用零都后移到行右．
3.3 GA和EP的个体适应值计算
　　在通过立体搜索,前移个体的非零元素过程中求得其适应值．设a(s′ij-1, s′ij),t(sij)和L(sij)分别为个体S中工序sij在机器i上的安装时间,运行时间和完工时间； s′ij-2,s′ij-1和s′ij分别为sij-2,sij-1和sij的操作类型；a(A, B)为操作A变为操作B的安装时间(换刀时间)； 令当j－1=0且sij为第一个工序时,s′ij-1=0, L(sij-1)=0；当j－2=0且sij为非第一个工序时, s′ij-2=0, sij-2=0, L(sij-2)=0．
　　(1) 求任一工序sij的完工时间L(sij)： ①sij为第1个工序：L(sij)=L(sij-1)+a(s′ij-1,s′ij)+t(sij)；②sij为非第1个工序：i)当sij-1=0 (有空闲等待)时,若sij-2≠0且L(sij-2)+min[a(s′ij-2,0)+a(0,s′ij)，a(s′ij-2,s′ij)]>L(sij－1)则L(sij)=L(sij-2)+min[a(s′ij-2,0) +a(0,s′ij), a(s′ij-2,s′ij)]+t(sij), 否则L(sij)=L(sij－1)+t(sij)；ii) sij-1≠0(无空闲等待)时, L(sij)=max+t(sij)．
　　(2)求任一机器i上最右(后)一个操作(非零元素)的完工时间Ti和任一工件k的完工时间LL(k)：Ti=L(sij), (sif≠0,有f＜u≤l时siu=0)．由工序统一编号表中查得任一工件k的最后一个工序x,求出x的完工时间L(x), 置LL(k)=L(x)．
　　(3)求染色体(个体)S的适应值．其中β为合适的惩罚系数, D(k)为工件k的交货时间．群体中求得的个体最小适应值,即为n个工件的加工时间．
3.4 GA的遗传算子
　　(1)选择算子(最佳个体保存)：将每代群体按适应值升序排序,取排在前20%(最佳)的个体复制到下一代 , 然后取排在前80%的个体进行交叉和变异．
　　为了使个体经交叉(变异)后能满足操作顺序约束要求,须先求需要移动的工序之移动区：设个体S中的元素sij的移动区为开区间(Wl,Wr)；Wl为sij的前一工序(sij－1)在S中的列号, Wr为sij的后一工序(sij+1)在S中的列号．只有Wr－Wl>2时才能对该个体进行交叉(变异),否则重选待移动工序(非零元素), 直到其移动区的长度>2时为止．
　　(2)交叉算子(实现两个数对的交换)：①根据交叉率(文中PC=1),随机地在匹配集中选取两个父个体A和B．在A中随机选取一个非零基因aij,获其移动区(a1,a2)；在B中找一个与aij值相等的基因bkf,获bkf的移动区(b1,b2)．②在(b1,b2)内随机产生一列号e(b1＜e＜b2),并随机产生可加工aij操作类型的行号(机器)g,找到bge的移动区(b3,b4)．若bkf在(b3,b4)内即b3＜f＜b4且行号k为bge的操作类型可加工的机器,置flag1=1．③在A内找与bge值相等的基因atv,获atv的移动区(a3,a4)．若有i) aij在(a3,a4)内即a3＜j＜a4且atv在(a1,a2)内即a1＜V＜a2,ii)行号i为工序atv的操作类型可加工的机器且行号t为aij的操作类型可加工的机器,置flag2=1．④若flag1与flag2=1, 则将数对aij与bge交换,atv与bkf交换．
　　(3)根据变异率(文中Pm=0.01),随机找一个交叉后的新个体S．在S中随机找一非零基因sij, 获sij的移动区(a1,a2),在(a1,a2)内随机产生一列号f(a1＜f＜a3)并随机产生一可加工sij的操作类型行号(机器)k．求得skf的移动区(a3,a4)包含sij(a3＜j＜a4)且行号(机器)i可加工skf的操作类型，则将数对sij与skf交换．
　　上交叉或变异算子产生的新个体均满足可行解条件,但还必须进行立体搜索,前移个体中的非零元素,使无效零移后,然后将这些新个体以及交叉和变异不成功的父个体放入下一代．
3.5 EP的选择算子和变异算子
　　(1)选择算子：置初始群体规模为偶数,将每代群体按适应值升序排序．取排在前50%(最佳)的个体复制到下一代 , 余下的个体进行变异．
　　(2)变异算子：进化规划只有变异算子而没有交叉算子,将需要变异的个体,随机选择如下6种变异算子(详见文献[3],基因只能在其移动区内移动)中的一种,进行变异：①Win(互换个体同行上的两个矩阵元素)；②Wbt(互换个体两个不同行上的矩阵元素)；③Sin(将个体中的一个非零元素与其移动区内同行零元素互换,WinSin)；④Sbt(将个体中操作数最多行上的一个非零元素与其移动区内的另一可加工其操作类型行上的零元素互换)；⑤Tin(将个体中某行最右一个有空闲等待工序的前一工序前移到其移动区内同行的第一个零元素处)；⑥Tbt(将个体中某行最右一个有空闲等待工序的前一工序移到其移动区内并可加工其操作类型之另一行上的第一个零元素处)．
　　上述变异算子产生的新个体均满足可行解条件,但还须将这些新个体进行立体搜索,前移个体中的非零元素,然后将这些新个体以及变异不成功的父个体放入下一代．
4　JSP的混合模拟退火进化算法(SAGA和SAEP)实现
　　由于模拟退火法(SA)在搜索过程中,随机接受某些劣化解,因而具有较强的全局搜索能力,能够跳出局部极小点．而上进化算法的最佳个体保存选择算子会导致局部最优个体急速增加,进化有可能过早收敛．因此文中混合使用SA和进化算法,即产生SAGA和SAEP来改善上GA和EP遗传操作后的选择机制(SAGA和SAEP的其它遗传操作分别同GA和EA)．文中的仿真实例中,初始温度T0=1,Tt+1=0.9Tt(每代降温率为0.9),由于收敛判据为1000代,故没有设置终止温度．接受概率依Metrolis准则：y2＜y1或exp(-(y2-y1)/T)＞ρ时子个体替换其父个体(y1是父个体的适应值, y2是子个体的适应值,T是温度系数,ρ是0和1之间均匀分布的随机数)．令①在交叉中,设i1和i2交叉成i3和i4,若i3的适应值,比i1的适应值小,则用i3替换i1,否则i3按概率替换i1；同样地,若i4的适应值比i2的适应值小,则用i4替换i2,否则i4按概率替换i2．②在变异中,设i1变异为i2,若i2的适应值比i1的适应值小,则用i2替换i1,否则i2按概率替换i1．将交叉或变异后替换过的父个体进行立体搜索,前移非零元素,然后将全部父个体保存到下一代中去．
5　仿真结果
　　设有10个工件在四台机器上加工；J1-J3为第1类工件, J4-J6为第2类工件, J7-J10为第3类工件．各类工件所需的操作为第1类：A, C, B, D；第2类：B, D, E；第3类：B, A, F．这3类工件的交货期限分别为190, 95, 181．10个工件的工序总数为33,其统一编号见表1．四台机器加工各操作所需安装时间见表2,各操作在机器上的运行时间见表3．表3还反映了四台机器各自能加工的操作类型．仿真实例的群体规模=100, 收敛判据=1000,惩罚系数β=2000(实验得到)．四种算法的调度结果(参见文献[3])略,仿真结果比较见表4 (CPU时间=算法得到最优解(收敛时)在586机上所需的时间(s))．
表2 四台机器加工各操作所需安装时间

　M1M2M3M4
0ABCF0BCDE0BDF0EF
002.52.01.82.101.51.41.82.201.31.71.201.92.1
A1.400.41.51.8
B1.31.700.60.91.701.82.00.81.801.51.8
C1.81.62.101.91.31.901.51.2
D　0.41.01.801.51.62.001.5
E1.51.51.41.30　1.802.1
F2.21.61.31.10　0.41.61.701.41.60

表3 各操作在机器上的运行时间

　ABCDEF
M117.2524.4518.68　13.88
M2　18.9515.7217.4518.67
M317.54　21.45　19.76
M4　15.4319.45

表4 四种算法的结果比较

　GAEPSAGASAEP
最佳适应值185.43187.01181.51180.72
收敛代数976772668869
CPU时间275(s)150(s)450(s)260(s)

(注：表2和表3中无数字的表项为无意义、非法表项) 
　　实验表明,这四种算法均能找到较为满意的调度结果,各工件的完工时间均能满足交货期限要求．由表4可知：①SAEP得到的解最优,即工件的加工时间(180.72)最短；而EP得到的解最差,即工件的加工时间(187.01)最长．②EP的CPU时间为150(S),收敛最快,而SAGA的CPU时间为450(S),收敛最慢．③混合模拟退火进化算法(SAGA和SAEP)得到的解均优于进化算法(GA和EP),但收敛速度均慢得多,SAGA的CPU时间为GA的1.64倍,而SAEP为EP的1.73倍．④进化规划(EP和SAEP)的收敛速度比遗传算法(GA和SAGA)快得多,GA的CPU时间为EP的1.83倍,SAGA为SAEP的1.73倍．从上比较结果分析,SAEP优于其它三种算法, 解最优 , 收敛也较快．
6　结论
　　(1)四种算法求解JSP都是有效可行的．(2)由于SA以一定的概率接受较差的个体,改进了进化算法的选择机制,克服了GA和EP的“过早收敛”问题,但进化算法比混合模拟退火进化算法的收敛速度快得多．(3)进化规划(EP或SAEP)的收敛速度比遗传算法(GA或SAGA)快得多．(4)文中用惩罚函数法处理了工件的交货期限约束；用抛弃不可行解法处理了机器约束和操作顺序约束．算法在对个体交叉和变异时,使需要移动的基因只能在其移动区内移动,进行基因交换,大大地提高了搜索效率,加快了遗传操作的速度,从而使算法收敛非常快(见表4),由此说明本算法求解JSP的有效性．
作者简介
　　翁妙凤(1941-),女,副教授．研究领域为计算机软件及人工智能．
　　王　直(1963-)，男，副教授．研究领域为自动控制．
作者单位：华东船舶工业学院　镇江　212003
参考文献
1　Golding D E Genetic Algorithms in Search, Optimize and Machine Learning. New York：Addiso Wesley, 1993，372～285
2 方剑等．基于事件驱动的Job Shop仿真调度系统．系统仿真学报,1997, 9(4)：42～50
3 翁妙凤．解Job-shop调度问题的混合模拟退火进化规划．信息与控制,1999, 28(2)：
收稿日期:1998-12-24
