基于自适应遗传算法混合 Flow-shop的调度与仿真*

赵建峰,朱晓春,汪木兰,卞磊,吴春英

(南京工程学院 a.自动化学院;b.先进数控技术江苏省高校重点建设实验室,南京 211167)

0 引言

近几十年来,随着 CAD/CAM/CAPP/CNC、FMS、CIM等先进制造技术的发展,生产调度问题越来越受到许多学者的关注。这是因为在生产过程中存在着大量几何形状类似、加工工序相同的工件,因此许多生产过程就不是简单的平行设备或者流水线作业,而是多级多机的混合流水车间(Hybrid Flow-shop,HFS)生产。混合流水车间作业调度也称为柔性流水线作业调度,是一类复杂的车间作业排序问题,相当普遍地存在于现代制造工业中[1-3]。

混合流水车间调度问题(Hybrid Flow-shop Scheduling prob lem,HFSP)可描述为：假设有 N个独立的工件J={i=1,2,…,n},需依次通过 k道工序加工,在每道工序上有 mi≥1(i=1,2,…,k)台独立的并行机可履行该阶段任务,而每个工件的每道工序只需在一台机床上加工,任意两道工序间有无限的存储能力(即被加工工件在两道工序间可以等待任意时间)。记该问题为Fk(m1,m2,…,mk)‖Cmax,其中 k为工序数,mi(i=1,2,…,k)是每道工序上的并行机床数量,最大完工时间Cmax是目标函数。问题的解是确定并行机床的分配情况以及同一台机床上工件的加工排序,使最大完工时间 Cmax最小化。

HFSP本质上是大规模组合优化问题,是 NP-hard完全问题,传统的数学规划方法难以求解[4-5]。早期对于混合 Flow-shop的调度主要有分枝定界算法[6]、启发式算法[7]、混合整数规划等,但这些算法只能解决规模较小的调度问题,对于大规模甚至中等规模问题的求解仍然不很理想。近年来,神经网络、模糊逻辑、遗传算法等已被用来求解这种大规模调度问题[1-3,8-10],其中遗传算法具有效率高、全局寻优等功能而得到广泛应用。本文采用顺序自适应交叉遗传算法求解混合调度问题,该算法能够在优化过程中自动选择比较合适的交叉概率,从而提高了搜索范围和搜索效率,仿真结果表明了此算法对于求解混合调度问题的优越性。

1 HFSP的编码

构造混合流水车间调度问题遗传算法的关键是如何进行遗传算法的编码和寻找基于特定问题的遗传算子,使得不管在初期还是在进化过程中所产生的染色体都是可行的调度,这也是所有遗传算法应用中的难点。

假设要加工 N个工件,每个工件都要依次经过 k道工序加工,所有工序中至少有一个工序存在并行机。下面构造一个 K×N维的 HFSP的编码矩阵 AK×N为：

编码矩阵中的元素 aij(i=1,2…K;j=1,2…N)为整数区间[100,999]上的一个三位数,其中第一位数字表示第 j个工件在第 i道工序中在第 Intj(ai×j/100)台并行机床上加工,后两位数字的大小表示在该机床上的加工顺序,数字小的则优先加工。例如,随机产生矩阵 A2×10为 ：

矩阵 A2×10的下标 2×10表示 10个工件需经过 2道工序的加工。第一行的十个基因元素(103,209,221,197,134,229,187,145,185,298)表示第一道工序中 10个工件的加工编码,其中首位数字为 1的表示工件在第一台机床上加工,即工件 1(103)、工件4(197)、工件 5(134)、工件 7(187)、工件 8(145)、工件 9(185)在机床 1上加工,首位数字为 2的工件即工件 2(209)、工件 3(221)、工件 6(229)、工件 10(298)在机床 2上加工。后两位数字表示加工顺序,数字小的优先加工,在 1号机床的 6个工件中,因为 03＜34＜45＜85＜87＜97,所以机床 1上各工件的加工顺序为 1→5→8→9→7→4;同理机床 2上各工件的加工顺序为 2→3→6→10。如果该两位数字相等,则以排在前面的优先加工。

第二行十个基因元素(208,335,383,197,330,276,110,100,298,200)表示在第二道工序中工件的加工编码,编码方式与第一行十个基因相同,则工件 4(197)、工件 7(110)、工件 8(100)在第二道工序的第 1台机床上加工;工件 1(208)、工件 6(276)、工件 9(298)、工件 10(200)在第 2台机床上加工,工件 2(335)、工件 3(383)、工件 5(330)在第 2台机床上加工。同理由于 00＜10＜97,00＜08＜76＜98,30＜35＜83,所以第二道工序中 3台机床上工件的加工顺序为别为(8→7→4),(10→1→6→9)和(5→2→3)。

2 基于自适应遗传算法 HFSP的求解

2.1 初始群体的设定

(1)初始种群的产生

随机生成 n个编码矩阵 AK×N,组成 n条染色体,每条染色体由 K个小段组成,每个小段包括 N个基因,即由编码矩阵的每一行组成一个小段,则每条染色体含有 K×N个基因,每个基因的取值范围为[100,(mi+1)×100),其中 mi为单个工序中最大并行机床数。例如根据上述的编码矩阵 A2×10可以得到对应的 20个基因的染色体为：

(2)种群规模的确定

考虑到种群 n如果取的太大则会增加计算量,影响算法效率,n太小则会陷入局部解过早收敛,这里 n的取值根据编码矩阵 K和 N的大小决定。例如对于A2×10的编码矩阵,一般 n的取值为[20,30]。

2.2 适应度函数(fitness function)的设计

HFSP遗传算法求解的重点是获得目标函数即最大完工时间 Cmax,并取最大流程时间的倒数作为适应度函数。

本文以 10个工件在 2道工序上加工的车间调度为例进行说明,其中第一道工序有 2台并行机床,第二道工序有 3台并行机床,即该问题为 Fk(2,3)‖Cmax,编码矩阵为 A2×10。

令 ti,j,k表示工件的加工时间,ci,j,k表示工件的完工时间,lasti,j表示各工序各机床上工件开始加工的时间。其中 i表示工序号,j表示机床号,k表示工件编号。

首先将编码矩阵 A2×10中第一行的 10个数按大小赋给 B1,1,k和 B1,2,k(百位是 1的赋给 B1,1,k,百位是 2的赋给 B1,2,k),然后再将编码矩阵中第二行的 10个数按大小赋给 B2,1,k,B2,2,k和 B2,3,k(百位是 1的赋给 B2,1,k,百位是 2的赋给 B2,2,k百位是 3的赋给 B2,3,k)。例如：

依次取上式 B中的每一个数 bi,j,k,如果该数不等于 0,则表示工件 k的第 i道工序在第 j台并行机床上加工,其加工所需时间是 ti,j,k(即每个不为 0的 bi,j,k对应于一个 ti,j,k),再通过比较 bi,j,k后两位数字的大小决定工件 k在机床上的加工顺序,然后将每个不为 0的bi,j,k对应的 ti,j,k赋给 Ti,j,k,n,其中 n为工件 k在第 i道工序第 j台并行机床上的加工顺序。例如第一道工序第一台机床上 k个工件的编码 B1,1,k所对应的加工时间矩阵 T1,1,,k,n为 ：

其中行表示工件号 k,列表示加工顺序 n。第一道工序：

其中 j=1,2;k=1,2,…10;n=1,2,…10。

last1,j表示在第一道工序中第 j台并行机床上工件k之前工件的完工时间,这里即表示工件 k开始加工的时间,Ti,j,k,n表示加工工件 k所需要的时间,c1,j,k表示工件 k的完工时间,然后再将 C1,j,k赋给 last1,j,此时的last1,j对于第 k+1个加工的工件来说就是第 k个工件的完工时间,即第 k+1个工件开始加工的时间。

第二道工序：

式中 j=1,2,3;k=1,2,…10;n=1,2,…10。

工件 k开始加工的时间为 max{last2,j,c1,a1,k100,k},last2,j表示在第二道工序中第 j台并行机床上在加工工件 k之前的前一个工件的完工时间,c1,a1,k100,k表示工件k在第一道工序中的完工时间,其中 a1,k100表示工件k在第一道工序中加工的机床号。

则最大流程时间为：

适应度函数取为：

2.3 选择

为防止过早收敛,本文采用非线性排序来确定个体被选择(复制)的概率,首先将种群中各染色体按适应度值从好到坏进行排序,使得排在前面的适应度值较好的个体分配到的概率 pi也较大[9]。

其中 i为个体排序号;q为一个常数。

然后再采用轮盘赌选择法来确定哪些个体被选择进行交叉和变异。

2.4 交叉

交叉操作又称为基因重组。染色体之间是否进行交叉一般是通过生成[0,1]的随机实数 Rc来决定,如果 Rc小于设定的交叉概率 Pc,则第 i条染色体和第 i+1条染色体进行交叉操作,该方法称为基本遗传算法(simple genetic algorithm,SGA)。

在基本遗传算法中交叉概率 Pc是固定值,如果 Pc越大,新个体产生的速度就越快,但 Pc过大时适应度值高的优良个体也容易被破坏;而 Pc过小,则又会使搜索过程缓慢,以致停滞不前[9-10]。

为了解决该问题,本文设计了一种新的交叉方法,使得 Pc能够随着目标函数适应度值的变化而自动调整,即使目标函数适应度值高的个体取较低的 Pc,目标函数适应度值低的个体取较高的 Pc,从而使适应度值高的优良个体得到保存,而适应度值低的个体被淘汰,且每次的操作都是由第 i条染色体和第 i+1条染色体交叉完成,故称之为顺序自适应交叉遗传算法(sequence adaptive crossgenetic algorithm,SACGA)。

在 SACGA中,Pc按 照以下公式进行调整：

由于染色体编码由 2段组成,为了确保后代的合法性,这里采用分段交叉法。首先随机生成[1,K×N]的随机整数 Z,然后将两个相邻的编码矩阵 AK×N中第Z个至该段最后一个基因全部互换,完成一次交叉操作。即当 Z∈[1,10]时,第一段发生交叉;当 Z∈[11,20]时,第二段发生交叉。假设在 Z=6,发生交叉时,则：

2.5 变异

现将 A2×10中的每个基因元素 aij对应生成[0,1]的随机实数 Rm,如果 Rm小于设定的变异概率 Pm,则 aij发生变异操作。每个基因变异的取值范围是[100,(mi+1)×100)。

例如,在车间调度实例 A2×10中,第一道工序有 2台并行机床,第二道工序有 3台并行机床,则在两道工序中 aij的取值范围为[100,299]和[100,399],即：

此操作既保证了变异的充分随机性,又保证了变异后产生新个体的合法性。

3 南汽转向器某车间调度实例

现以南汽转向器某阀体生产车间为例,该车间主要生产 IVECO、MG3和 MG7等 10个品种的阀体工件。为了提高加工效率,该车间的加工工艺由原来的车→铣→磨优化为数控车→高速铣加工,以铣代磨,因此该车间共有 2台数控车床和 3台高速铣削加工中心。由于各机床加工能力的不同以及机床操作工人技能的差异等原因,各加工时间也不尽相同,由设计软件随机生成的加工时间如图 1所示。

图 1 各工件在各机床上加工时间

该阀体生产车间采用基本遗传算法(SGA)和顺序自适应交叉遗传算法(SACGA)进行生产调度安排,两种遗传算法的参数为：初始化种群大小 pop_size=20,选择参数 q=0.4,交叉概率 Pc=0.6,变异概率 Pm=0.01。经过 80代进化后目标函数的最小值和平均值变化曲线如图 2所示。由图 2可以看出,SACGA最小值变化曲线收敛得更快,求解质量和寻优效率均优于基本遗传算法,更有利于产生最优解。

SGA得到最好的染色体是[258,173,175,261,162,280,288,296,121,262,262,365,158,301,317,118,327,288,116,262],相应的甘特图如图 3所示。甘特图中包括工件在各级机床上的加工排序,加工开始、完成时间,以及所有工件的完工时间,即最大流程时间是 83分钟。

图 2 混合 Flow-shop遗传算法曲线

SACGA得到的最好的染色体是[136,269,294,299,299,128,298,288,168,131,361,254,194,364,386,183,280,355,197,271],相应的甘特图如图 4所示,最大流程时间是 80分钟,加工效率更高。同时,各并行机床的加工任务均匀,且各机床加工时间连续,机床的加工时间都相应缩短,减少了机床损耗,并节约了生产成本。当然,利用遗传算法得到的结果往往是近优值,而非最优值。但相对于人工经验调度来说,利用智能算法所得到的结果,一方面准确度得到了改进,另一方面也大大提高了排序效率。

根据南汽转向器某阀体生产车间的实际情况,运用 VB对实际加工情况进行虚拟仿真,如图 5所示,可以很直观地观察各工件的加工情况,运行效果良好。

图5 混合Flow-shop界面运行仿真

4 结束语

本文所提出的顺序自适应交叉遗传算法是在 Srinvivas和 Patnaik等在 1994年提出的自适应遗传算法的基础上发展起来的一种新的算法,该算法既有利于优良个体的保留,提高整个算法的收敛性;同时又提高了算法的寻优速度。实例分析及虚拟仿真结果表明,混合 Flow-shop顺序自适应交叉遗传算法所计算出的调度结果较基本遗传算法更为优越,具有较广的应用价值。本文主要研究了 10个工件在 5台机床上地生产调度,对于大规模的组合优化问题,是下一步研究的主要目标。

[1]Johnson SM.Op timal two-and three-stage production schedules with setup times included[J].NavalResearch Logistics-Quarterly,1954(1)：61-68.

[2]Gup ta JND.Two-stage hybrid Flow shop scheduling p roblem[J].Operational Research Society,1988,39(4)：359-364.

[3]Yang Jianbo.GA-based discrete dynam ic programming app roach for schedu ling in FMS environments[J].Sy-stems,Man and Cybernetics,Part B,IEEE Transactions,2001,31(5)：824-835.

[4]Hoogeveen JA,Lenstra JK.Preem ptive Scheduling in a Twostage Multiprocessor Flow Shop is NP-hard[J].European Journal of Operational Research,1996,89(1)：172-175.

[5]何龙敏,孙世杰,罗润梓.带成组加工的二阶段柔性流水作业问题[J].工程数学学报,2008,25(5)：829-842.

[6]O Moursli,Y A Pochet,Branch and bound algorithm for the hybrid flow shop[J],Int.J.Prod.Econ.2000,64：113-125.

[7]Guinet A.Scheduling hybrid flow shop to m inimize maximum tardiness or maximum completion t ime[J].I-nt JProRes,1996,34：1643-1654.

[8]Iyer SK,Saxenab B.Imp roved genetic algorithm for the permutation flow shop scheduling p roblem[J].Comput Oper Res,2004,31：593-606.

[9]王万良,吴启迪.生产调度智能算法及其应用[M].北京：科学出版社,2007.

[10]Srinvas M,Patnaik L M.Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms[J].IEEE Trans Systems Man and Cybernetics,1994,24(4)：656-667.