基于遗传算法的柔性车间调度优化

郭 庆， 张明路， 孙立新， 刘 轩

(河北工业大学机械工程学院， 天津 300131)

车间生产调度作为关键技术和核心内容在离散柔性制造生产计划中起主要作用[1]，因为每个企业车间的生产资源是有限的，并且工件的加工也会受到设备工艺的限制，如何合理安排每个工件的每个生产步骤在哪台设备上加工，以确保所选定的目标的最佳性能，这就是调度的目的。该问题的特征在于显著的离散性、复杂性、多重约束和不确定性。传统作业车间生产调度很难达到最佳的排产效果，这样就会造成生产效率低下，浪费生产资源，增加企业生产成本。因此，用来实现柔性车间调度的智能算法亟需设计，进而可以提高生产效率，提高企业的市场竞争力。

柔性车间生产排产调度问题(flexible job shop scheduling problem，FJSP)是传统作业车间生产调度问题(job shop scheduling problem，JSP)的扩展。FJSP 这个问题在1990年由Bruker等[2]提出，在JSP中，每道工序是预先确定的，并且其生产设备和生产时间也是预先确定的。而在FJSP中，每道工序的生产设备是不确定的。每道工序都有加工设备集，可在其中挑选任一设备进行加工，并且不同生产设备生产同道工序所花费时间不同，这增加了该类调度问题的灵活性，且在实际生产中为常见情况，所以解决该问题势在必行。

目前，解决 FJSP 的常用方法有禁忌搜索(taboo search,TS)，模拟退火(simulated annealing，SA)，遗传算法(genetic algorithm，GA)和粒子群优化(particle swarm optimization，PSO)等[3-6]。其中，遗传算法因其良好的鲁棒性、通用性和计算机优势而被广泛应用。武韶敏等[7]研究出了基于矩阵编码的方法对遗传算法进行改进，并且详细描述了初始种群的生成方法。崔琪等[8]在搜索方面采用混合变邻域的方法对遗传算法进行了改进。姚丽丽等[9]提出一种启发式正序排产算法，该方法采用调度规则与逻辑约束两层改进处理的作为总体排产方法。

现针对柔性车间生产调度问题，提出一种灵活的车间调度模型，并对该模型进行详细的求解。针对模型结构的特殊性，采用一种新的编码思想进行染色体的双层编码，获得具有较高质量和多样性的初始种群；将MATLAB编程应用到解码和适应度函数的计算中，加快求解效率和降低问题的复杂性；给出了相应的选择操作设计，交叉操作采用多交叉机制，变异操作结合种群分割的思想实行两种变异机制，进一步改善算法的全局和局部搜索能力；并且添加检查操作增强优化过程的可行性。最后通过一个6×6调度问题的仿真实例对算法的有效性进行验证并绘制甘特图。

1 FJSP的数学模型

1.1 问题描述

FJSP描述如下：n个工件{N1,N2，…,Nn}在m台设备{M1,M2,…,Mm}上加工。工件i的总工序为ni，每个工序的顺序都已确定，而且每个工件工序都有加工设备集，可挑选集合中任何设备加工该道工序，但生产时间因生产设备不同而不同。调度目的是在整个生产计划中，为每道工序选择最合适的设备，并确定每台设备最佳生产顺序和启动时间，以保证最大完成时间(makespan)最小化，总设备负荷最小和临界设备符合最小。

1.2 数学模型

在建立FJSP数学模型之前，做出如下基本假设：①任何设备在同一时刻不能处理两个生产步骤；②任一工件必须严格按照自己的工序顺序进行加工；③任一工件必须严格在自己的加工设备集里加工；④不同的工件的生产步骤之间没有约束条件，优先级相同；⑤生产开始后，不能中断，并且能正常生产完成；⑥设备与工件的开始时间都允许在0时刻开始。

为建模方便，现将FJSP问题表述为：n个工件{N1,N2，…,Nn}在m台设备{M1,M2，…,Mm}上加工。工件i的总工序为ni，则所有工件集的总生产步骤为Num=sumni。上述基本约束条件下，针对最大完成时间(makespan)最小化，总设备负荷最小和临界设备符合最小。设oij为工件i的第j道工序；M[i,j]为工件i的第j道工序的可用设备集合；

xijk为判定函数。

FJSP数学模型如下。

(1)最小化完工时间：

(1)

式(1)中：f1为第1个目标函数；CM为所有设备的完工时间；Ck为第k台设备上的完工时间；k为设备索引，k=1,2，…，m；m为设备总数。

(2)各台设备的加工时间：

(2)

式(2)中：Wk为第k台设备上的工作负荷；n为工件总数；ni为工件i的总工序；i、h为工件索引，i、h=1,2，…，n；j、g为工件序列索引，j、g=1,2，…，ni；Tijk为工件i的第j道工序在设备k上的加工时间。

则总设备负荷最小，即全部设备的总加工时间：

(3)

式(3)中：f2为第2个目标函数；WT为全部设备总加工时间。

(3)临界设备负荷，即加工负荷最大的设备：

(4)

式(4)中：f3为第3个目标函数；WM为设备临界负荷。

s.t.

Cij-Ci(j-1)≥Tijkxijk,j=2,…,ni;∀i,j

(5)

式(5)中：Cij为工件i的第j道工序的完成时间。

[(Chg-Cij-thgk)xhgkxijk≥0]∨[(Cij-

thgk)xhgkxijk≥0],∀(i,j),(h,g),k

(6)

式(6)中：thgk为工件h的第g道工序在设备k上的开始加工时间。

(7)

Cij≤Cmax,i=1,2,…,n

(8)

Sij≥0,Cij≥0

(9)

式(9)中：Sij为工件i的第j道工序的开始加工时间。

式(5)确保了工作顺序的先后约束；式(6)限定每台设备每次只能处理一道工序；式(7)表示可以从每道工序的加工设备集里选择一台设备进行加工；式(8)限定了每一个工件的完工时间不可能超过总完工时间；式(9)限定了所有参数变量的非负性。

2 FJSP的遗传算法实现

遗传算法(genetic algorithm)是一种基于自然物种进化规律的算法，即适者生存。遗传算法过程如图1所示。

图1 遗传算法过程Fig.1 Genetic algorithm process

2.1 编码设计及初始化

遗传算法解决任何问题的首要关键都是编码，其次便是解码，解决FJSP问题也不例外。由于FJSP模型的特殊性，采用双层编码的方式，对第一层染色体编码，为所有工件所有工序进行排序，对另一层染色体编码，为每道工序的加工设备编号，并最终通过MATLAB编程得以验证方法可行。

M{i,j}表示工件i的第j道工序的加工设备集，T{i，j}表达工件i的第j道工序被不同生产设备加工的时间集。假设n=4，ni=4，则M、T如表1、表2所示。

表1 M加工设备集Table 1 M processing equipment collection

表2 T加工设备时间集Table 2 T Processing equipment time collection

两层编码即两条染色体，分别命名为X、Y染色体，接下来分别对X、Y进行编码。

X染色体代表随机安放每个工件的每个工序，并保证每个工件的工序的先后顺序，由于n=4，ni=4，则Num=16，则X染色体长度为16，X染色体编码过程如下。

第1步将1～16随机排序，代表所有工序随机排列，得初始染色体{5 8 4 2 9 7 10 13 1 11 16 15 3 6 12 14}。

第2步将初始染色体{5 8 4 2 9 7 10 13 1 11 16 15 3 6 12 14}按照先后顺序4个为一组进行分组，每一组代表一个工件的4个工序，得子染色体{5 8 4 2} {9 7 10 13} {1 11 16 15} {3 6 12 14}。

第3步将每个子染色体在各自内部进行大小排序，得子二代染色体{2 4 5 8}{7 9 10 13}{1 11 15 16}{3 6 12 14}。

第4步将子二代染色体{2 4 5 8}{7 9 10 13}{1 11 15 16}{3 6 12 14}合并成中间染色体Z{2 4 5 8 7 9 10 13 1 11 15 16 3 6 12 14}。

第5步对Z染色体中的值的位置编号，并将编号根据Z染色体1～16序列编码数字以形成X染色体，表3中1～4表示工件1的4道工序，5～8代表工件2的4道工序，以此类推。例如“8”在Z染色体中是第4个位置，则在X染色体的第8位置编码为4。X染色体如表3所示。

表3 Z-X转换表Table 3 Z-X conversion form

该编码方式可以有效地避免工序错乱的情况出现，确保每一个工件按照各自的工艺流程加工完成，大大提高了染色体的可行性，有助于保证种群质量。

Y染色体代表依照X染色体的工序排序，加工每道工序的具体设备编号，Y染色体编码过程如下。

第1步依照X{9 1 13 2 3 14 5 4 6 7 10 15 8 16 11 12}顺序确定可加工该工序的生产设备集{[M6,M8],M4,[M1,M4],[M1,M2,M3],[M8,M9],

M3,M2,M3,M7,M4,[M2,M6],[M5,M7,M8],[M2,M3],M7,M5,[M4,M6]}。

第2步将生产设备集内部重新进行编码，得新染色体{[1,2], 1,[1,2],[1,2,3],[1,2], 1,1,1,1,1,[1,2],[ 1,2,3],[1,2], 1,1,[1,2]}。

第3步在各自的设备集中随机挑选设备加工该道工序，最终得到Y染色体，即{1,1,2,3,2,1,1,1,1,1,2,3,1,1,1,1}。该编码方式是为后续在时间集中采集设备加工时间提供便利。

重复以上编码流程，直到形成完整的初始种群NP。

2.2 适应度定义和选择策略

选择的目的就是实现适者生存，高质量的亲本遗传给下一代。

在本FJSP模型中，目标函数是寻求最大的完工时间的最小值，为了概率筛选，令fit=1/makespan，其中fit为适应度，makespan为最大完工时间。makespan是根据Y染色体中选择的加工设备而定的。Y染色体为{1,1,2,3,2,1,1,1,1,1,2,3,1,1,1,1}，依照T{i，j}对应的时间，得TY={2,3,3,3,2,2,3,6,4,5,4,2,2,3,1,2}。

假设n=4，ni=4，定义z来表示工件i的第j道工序，当z=1是表示工件1的第1道工序，z=2表示工件2的第1道工序，z=5表示工件1的第2道工序，以此类推。当z取值遍历[1,16]后makespan的取值便得出，计算过程如下：

Tz=T{i,j}(z),z∈[1,16]

(10)

式(10)中：Tz为Y染色体在T{i,j}加工设备时间集中选取对应加工时间。

Mz=M{i,j}(z),z∈[1,16]

(11)

式(11)中：Mz为根据X染色体选取M{i,j}加工设备集中的设备编号。

Ts=max[machtime(Mz),parttime(i)]

(12)

式(12)中：Ts为Mz和i中取最大值。

machtime(Mz)=Ts+Tz

(13)

式(13)中：machtime(Mz)为编号为Mz的设备加工第z道工序后经历的时间。

parttime(i)=Ts+Tz

(14)

式(14)中：parttime(i)为工件i加工完第z道工序后经历的时间。

makespan=max(machtime)

(15)

式(15)中：makespan为最大完工时间。

选择采用轮盘赌选择法(roulette wheel selection)，实现选择公式Pi=fi/sumfi，其中n是种群大小，Pi是个体i被选择概率，fi是个体适应度值，即由各个适应度的值在总体适应度的比率确定。

2.3 交叉

交叉是选择两个亲本个体，在两个亲本上选择相同长度的染色体片段进行替换，最后重建新一代个体。根据FJSP的特点，设计了3种交叉机制，即单段交叉、两段交叉和三段交叉，可提高遗传算法的全局搜索能力，提高种群质量，实现种群进化。

图2 3种交叉机制图Fig.2 Three cross mechanism diagrams

2.4 变异

变异操作也是关键的一步。其既可以使遗传算法具有局部搜索能力，也可以保持群体多样性，以防止不成熟得收敛。为了使变异操作过程具有方向性和目的性，引入了种群分割的概念[10]，基于种群分割的思想实行两种不同的变异机制，以此来实现更加有效的变异操作。根据适应度函数计算种群各个染色体的适应度值并取种群适应度平均值，将高于平均值的染色体定义为优质染色体，赋予变异概率Pm1，实行两点变异机制，如图3(a)所示；将低于平均值的染色体定义为劣质染色体，赋予变异概率Pm2，实行翻转变异机制，如图3(b)所示。种群分割可以有效地避免无意义的变异，提高了遗传算法的局部寻优能力。

图3 两种变异机制图Fig.3 Two variant mechanism dia

2.5 检查

遗传算法的过程中本无此操作，但由于编码的特殊性，会在交叉和变异的流程中出现不可行解，如图4中子代染色体Xnew1、Ynew1、Xnew2、Ynew2由于工序重复导致该染色体不能继续遗传给下一代并且必须被淘汰，这样通过检查程序的筛选，确保最终得到的最优解符合遗传规则，是可行的。

图4 两个父代XY交叉图Fig.4 Two parent XY cross graphs

2.6 终止条件

通过数代后的求解，当群体中最佳适应度满足要求，或者不再上升，即式(1)取得最小值，再或者迭代次数到达了预先设置的值时，算法停止运行。

3 应用案例分析

现对一个n=6，m=10，ni=6的FJSP进行仿真。接下来是M{i，j}和T{i，j}，如表4、表5所示。

表4 M{i，j}加工设备集Table 4 M{i，j} processing equipment collection

表5 T{i，j}加工设备时间集Table 5 T{i，j} processing equipment time

遗传算法中的运行参数为：种群大小NP=40，最大进化代数maxgen=200，交叉概率Pc=0.8，变异概率Pm1=0.2，Pm2=0.6，代沟Gap=0.9。

基于以上技术及参数，现用MATLAB R2018a进行模拟仿真，结果如图5所示。图5中，纵坐标是加工设备编号，横坐标是加工时间，J[i，j]为工件i的第j道工序。

图5 调度甘特图Fig.5 Scheduling Gantt chart

经过混合改进遗传算法优化之后，与传统遗传算法方式进行对比，在收敛速度方面有着明显的改善，对比结果如图6所示。

图6 求解收敛图Fig.6 Solving convergence

4 结论

基于JSP模型，建立了FJSP的数学模型，并采用混合改进的遗传算法对模型求解优化。由于FJSP本身的相对复杂性，提出了一种新的编码思想用于双层染色体编码，得到了优质的初始种群；算法交叉过程中只用了3种不同的交叉机制，增强了交叉流程的有效性；变异操作引进了种群分割的思想，根据不同的变异概率选择不同的变异机制；但两层编码结构具有一定的特殊性，可能导致交叉变异之后出现不可行解，因此新添加检查操作，对交叉和变异之后的不可行解进行排除以确保种群生存能力。最后测试应用实例结果表明该算法不仅是正确有效的，而且明显提高了收敛速度，加强了最优解的正确性。