柔性作业车间调度问题(Flexible shop scheduling problem, FJSP)是作业车间调度的扩展, 也增加了求解的难度, 所以FJSP一直是国内外学者研究的热点^[1-4]。在FJSP中, 尽管每一个工件的工序是一定的, 但是每个工序的加工时间和所在的加工机器是不确定的。所以, 在FJSP中, 主要考虑的问题是工序所在的加工机器和各工序的加工顺序。常用的求解FJSP的智能算法有遗传算法^[5]、粒子群算法^[6]、免疫算法^[7]和蚁群算法^[8]等。遗传算法与其他算法相比较, 具有过程简单、鲁棒性好和全局搜索能力快等优点^[9], 因此遗传算法在FJSP中得到了广泛的应用^[10-12]。但是传统遗传算法也存在收敛速度慢和容易陷入局部最优等不足。因此, 在解决FJSP时, 国内外的学者对传统遗传算法进行了一定的改进以克服基本遗传算法的不足。根据FJSP的特点, 刘琼等人^[10]提出了一种改进的交叉变异方法并设计了一种初始解产生机制。张国辉等人^[11]采用一种随机和优化相结合的初始化种群方法。赵诗奎等人^[12]运用均匀设计原对遗传算法中的初始种群及适应度函数进行设计并将其应用到FJSP中。贺仁杰等人^[13]提出了一种求解柔性车间作业调度的知识型协同演化方法。文献[14]对遗传算法中的多父代交叉算子和多点变异方面进行改进并对FJSP进行优化研究。这些改进仅仅是针对柔性作业车间调度问题的, 没有将AGV的运输时间考虑进去。因此本文同时对既有AGV又有工件的柔性作业车间调度问题进行研究, 同时提出一种改进遗传算法, 不仅对遗传算法的缺点进行改善, 而且更接近实际的加工环境。在改进遗传算法中, 提出一种多段式编码方法, 即在两段编码的基础上加入末端基因, 可以加速淘汰质量差的基因, 提高进化速度。提出离散型遗传交叉和变异概率公式, 此公式具有较强的针对性, 可以对不同的车间调度产生不同的公式, 这种概率公式可以使得再次运行遗传算法时更快地获得最优解。

1 有AGV约束的柔性作业车间调度模型 1.1 柔性作业车间调度问题约束条件

有n个工件需要在m台机器上进行加工, 每个工件包含p(p≥1) 道工序, 每一个工件的工序是一定的, 但是每个工序的加工时间和所在的加工机器是不确定的。所以, 在柔性作业车间调度中, 主要考虑的问题是工序所在的加工机器和各工序的加工顺序。

在柔性作业车间调度的加工过程中的约束条件如下:

(1) 零时刻开始, 所有的工件有相同的加工优先级;

(2) 不同工件的工序没有加工顺序要求, 相同工件的工序需要按照一定的顺序进行加工;

(3) 同一时刻任一台机器只能加工一个工序;

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

(5) 一道工序的加工开始, 中间不能暂停和终止。

1.2 AGV调度约束

AGV主要负责把工件在各个机器之间进行传送, 本文主要考虑AGV运输工件所需要的时间。AGV的运输时间随机器的转移发生变化, AGV可完全满足工序的运输需要, 并且AGV在运输过程中互不影响。运输时间如表 1所示, 其中, M为加工机器, t_mn表示AGV从机器M_m运输到M_n所需的运输时间。

1.3 有AGV约束的柔性作业车间调度模型

有AGV约束的柔性作业车间调度模型中需考虑的约束条件如下:

(1) AGV装卸料的时间为0;

(2) AGV能够使得工序加工结束后能立刻被转移到下个机器加工下一道工序;

(3) AGV运输工件时不影响其它工件的加工;

(4) AGV在工件的第一道工序结束后开始工作;

(5) AGV的运输时间由运输相关的两个机器确定。

以最大化完工时间最小为目标建立有AGV小车约束的柔性作业车间调度的数学模型如下:

$ {\rm{Makespan}} = \min \left( {\mathop {\max \left( {{T_{me}}} \right)}\limits_{1 \le m \le M} } \right) $

(1)

$ {T_{ije}} = {T_{ijs}} + {t_{ij}} $

(2)

$ {T_{\left( {i + 1} \right)js}} \ge {T_{ije}} $

(3)

$ \sum\limits_{m = 1}^M {{x_{ijm}}} = \left\{ \begin{array}{l} 1\;\;\;\;工序在机器m上加工\\ 0\;\;\;\;工序不在机器m上加工 \end{array} \right. $

(4)

$ {T_{me}} = {T_{ms}} + {t_{ij}} $

(5)

$ {T_{{\rm{agvs}}}} = {T_{me}} $

(6)

$ {T_{ijs}} = \left\{ \begin{array}{l} {T_{{\rm{agve}}}}\;\;\;\;{T_{{\rm{agve}}}} > {T_{me}}\\ {T_{me}}\;\;\;\;\;{T_{{\rm{agve}}}} < {T_{me}} \end{array} \right. $

(7)

$ {T_{{\rm{agve}}}} - {T_{{\rm{agvs}}}} = {L_{mn}} $

(8)

$ N = \sum\limits_{i = 1}^h {\sum\limits_{j = 1}^k {{O_{ij}}} } $

(9)

式中:i为工件(i=1, 2, …, h), h为工件数; j为工序(j=1, 2, …, k), k为工序数; m为机器(m=1, 2, …, M), M为机器数; T_ms为机器m加工开始的时间(0＜m≤M); T_me为机器m加工结束的时间; T_agvs为小车开始运输的时间; T_agve为小车运输结束时间; L_mn为小车运输前后所在的机器为m和机器n转移时间; T_ijs为工件i(0＜i≤h)的第j道工序的开始时间; T_ije为工件i的第j道工序的结束时间; t_ij为工件i的第j道工序的加工时间; x_ijm=0表示工序O_ij不在机器m上加工, x_ijm=1表示工序O_ij在机器m上加工; N为工序总数; O_ij为工件i的第j道工序数。

式(1) 为最小完工时间; 式(2) 和式(3) 说明相同工件的工序需要按照一定的顺序进行加工, 且同一时刻任一台机器只能加工一个工序; 式(4) 说明同一时刻, 一道工序只能被一个机器加工; 式(5) 说明一道工序的加工开始, 不能暂停和终止; 式(6) 说明AGV能够使得工序加工结束后能立刻被转移到下个机器加工下一道工序; 式(7) 说明AGV运输工件时不影响其他工件的加工; 式(8) 说明AGV的运输时间由运输相关的两个机器确定; 式(9) 为所有工序总和。

2 改进遗传算法

本文提出改进遗传算法可对不同的调度情况确定不同进化过程中的交叉概率和变异概率。然后通过获得的概率公式推广到多种群遗传算法中, 这样可以加快进化速度, 并且避免陷入局部最优。具体流程图如图 1所示。

图中, 首先产生一个初始种群, 种群规模为Z, 然后利用传统遗传算法确定原始进化曲线, 其中初始交叉概率为p_c⁰, 初始变异概率p_m⁰。将获得的进化曲线分成b段, 多次重复进化过程获得一个适应于此调度的多组交叉和变异概率, 利用获得的概率数组, 确定离散的交叉和变异概率公式。然后随机生成n个种群并利用多种群遗传算法, 最终完成进化过程, 具体过程详见第3节。

3 改进遗传算法的设计方案 3.1 编码与解码 3.1.1 编码

在传统的遗传算法中, 无用的基因经常存在于进化过程中, 因此影响了进化速度。本文提出一种多段式编码(图 2), 可以使得一些对进化没有帮助的基因直接被淘汰掉。机器部分用于确定工序所在的加工机器, 工序部分用于确定各工件工序的加工顺序, 末端基因用于淘汰适应度满足要求但是对进化无用的基因。

以3个工件在3台机器上的柔性加工调度为例阐述所提出的编码方法, 工件的加工工艺及机器之间的转移时间分别如表 2和表 3所示。其中, O_ij表示工件i的第j道工序。

如果工序O₁₁-O₁₂-O₁₃-O₂₁-O₂₂-O₂₃-O₃₁-O₃₂-O₃₃对应的加工机器是M₁-M₂-M₃-M₁-M₂-M₃-M₁-M₂-M₃, 各工件的加工顺序是O₁₁-O₂₃-O₁₂-O₃₁-O₃₂-O₁₃-O₂₁-O₂₂-O₃₃, 那么机器编码部分为123123123, 工序编码部分为121331223。

末端基因采用与代数相同的位数, 如果有100代, 则末端基因取3位, 初始基因取001。在进行适应度计算时, 同时对基因从以下两个方面进行评价:各机器的负荷是否均匀; 基因在进化过程中的进化程度(随着代数的增加, 基因的改变程度)。对于质量差的基因将增加其末端基因的值, 当值超过一定量时, 此个体将被直接淘汰。

所以初始编码为123123123 121331223 001。

3.1.2 解码

任取一个合理的编码321321321 112233123 046, 其解码过程如图 3所示。

解码获得的调度甘特图和机器之间的转移时间分别如图 4和表 4所示。其中, 图 4中的L_mn为小车从第m个工件的第n道工序所在的加工机器转移到第m个工件的第n+1道工序所在的加工机器的转移时间。例:O₁₁所在的加工机器为M₃, O₁₂所在的加工机器为M2, L₃₂即为小车从M₃转移到M₂所需的时间。

3.2 选择操作

本文采用精英保留策略以避免最优解的流失。保留精英基因的同时要有效地淘汰垃圾基因, 特制定的选择操作如下:

(1) 直接保留N/10个适应度高的个体(N为种群规模);

(2) 从剩余的9N/10个个体中采用轮盘赌的方法保留N个个体;

(3) 对(2) 中获得的个体按照末端基因值排序, 并淘汰末端基因值最高的n/10个个体。

3.3 交叉操作 3.3.1 机器部分的交叉操作

机器编码部分采用多点交叉, 多点交叉可以使得交叉更加均匀和充分, 过程如下:

(1) 选取父代个体P₁, P₂;

(2) 在区间(0, 1) 之间随机产生一个实数a, 如果a < p_c(交叉概率), 则将P1的第b个基因与P2的第b个基因进行交叉替换。b的初始值为1;

(3) b=b+1;

(4) 重复步骤(2, 3) 直到b等于P₁中机器部分基因的个数;

以图 5为例, 其中P₁、P₂为父代, C₁、C₂为子代, 假设参加交叉的基因是第3、5和7位。

3.3.2 工序部分的交叉操作

采用改进的基于工序的交叉, 可以很好地防止非法解的产生, 并且可以保留优秀基因。过程如下:

(1) 选取父代个体P₁、P₂;

(2) 在区间(0, 1) 之间随机产生一个实数a, 如果a＜p_c(交叉概率), 则将P1中属于工件b的基因全部复制到子代C1中, b的初始值为1;

(3) b=b+1;

(4) 重复步骤(2, 3) 直到b等于P₁中工序部分基因的个数;

(5) 将P₁中其他基因复制到C₂中的相同位置;

(6) 将P₂中与C₁中属于不同工件的基因按照P₂中的顺序依次填充到C₁空余的基因位上;

(7) 将P₂中与C₂中属于不同工件的基因按照P₂中的顺序依次填充到C₂空余的基因位上;

假设P₁复制到C₁的基因属于工件1和工件3, 工序部分交叉如图 6所示。

3.4 变异操作

机器部分采用单点变异, 过程如下:

(1) 选取父代个体P₁;

(2) 在区间(0, 1) 之间随机产生一个实数a, 如果a＜p_m(变异概率), 则将P₁中的第b个基因随机替换为区间[1, c]之间的一个整数, b的初始值为1;

(3) b=b+1;

(4) 重复步骤(2, 3) 直到b等于P₁中机器部分基因的个数。

工序部分采用位置变异, 过程如下:

(1) 选取父代个体P₁;

(2) 在区间(0, 1) 之间随机产生一个实数a, 在区间[1, c]之间的随机产生一个整数d, 如果a < p_m(变异概率), 则将P₁中的第b个基因与第d个基因进行替换, b的初始值为1;

(3) b=b+1;

(4) 重复步骤(2, 3) 直到b等于P₁中工序部分基因的个数。

3.5 改进的交叉和变异概率公式

传统的遗传算法是根据大量的实验和经验确定交叉和变异概率, 但缺乏针对性。本文设计一种基于调度本身的离散式的交叉和变异概率公式, 过程如下:

(1) 利用传统遗传算法获得进化曲线图, 并将从开始到进化平稳的一段分成n等分;

(2) 确定第n(n=a+1) 段的交叉概率p_c=p_cⁿ及变异概率p_m=p_mⁿ, a的初始值为0;

(3) a=a+1;

(4) 重复步骤(1~3) 操作, 获得p_c¹, p_c², …, p_cⁿ;

最后得到离散的交叉和变异概率计算公式如式(10, 11) 所示。

$ {p_c} = \left\{ {\begin{array}{*{20}{c}} {p_c^1}&{n = 1}\\ {p_c^2}&{n = 2}\\ \vdots&\vdots \\ {p_c^n}&{n = n} \end{array}} \right. $

(10)

$ {p_m} = \left\{ {\begin{array}{*{20}{c}} {p_m^1}&{n = 1}\\ {p_m^2}&{n = 2}\\ \vdots&\vdots \\ {p_m^n}&{n = n} \end{array}} \right. $

(11)

3.6 适应度 3.6.1 适应度函数计算公式

适应度函数如式(12) 所示。

$ {\rm{fit}}\left( {f\left( x \right)} \right) = \left\{ \begin{array}{l} {C_{\max }} - {\rm{Makespan}}\;\;\;\;f\left( x \right) < {C_{\max }}\\ 0\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;其他 \end{array} \right. $

(12)

式中:fit(f(x))为适应度值; C_max为所有工件都在一个机器上加工时, 所需时间的最大值; Makespan为完工时间。

3.6.2 末端基因值的计算公式

随着代数的增加, 进化速度慢的个体和机器负荷不均匀的个体应该以更大的概率被淘汰。即末端基因值越大, 被淘汰的概率越大。末端基因值按式(13) 进行计算。

$ {t_G} = {t_g} + \frac{{{\rm{Makespan}}}}{{{T_{\max }}}} $

(13)

式中:t_G为当前末端基因值; t_g为原末端基因值; T_max为各工件加工总时间; Makespan为完工时间。

4 实验结果与分析

为了比较算法的性能, 使用同一个实例将本文提出的算法与传统遗传算法进行比较。试验中种群规模取N＝100, 种群数量取2, 进化代数G取60, 分段函数中的段数取N/10, 初始的交叉概率取0.6, 初始的变异概率取0.01。算例的6个工件在6台机器上的加工工艺如表 5所示, 这是典型的部分柔性调度问题。在表中, 符号“—”表示对应的工序不能在这台机器上进行加工。实例中小车运输时间表如表 6所示。

利用本文提出的改进遗传算法获得的进化曲线如图 7所示, 与传统的遗传算法的对比结果如表 7所示。此案例获得的柔性作业车间调度甘特图如图 8所示。从图 7和表 7可以看出, 本文提出的改进遗传算法所需的时间尽管比传统遗传算法时间长, 但是获得的最优解比传统遗传算法更好。因为利用传统遗传算法获得初始解, 所以运行总时间偏长。但是当概率公式确定以后, 再次运行时, 进化速度明显比传统遗传算法快, 从而提高了效率。

5 结束语

本文对有AGV约束的柔性作业车间调度进行了研究, 建立了柔性作业车间调度数学模型; 提出一种多段式编码, 可以使得一些对进化没有帮助的基因直接被淘汰掉; 提出一种分阶段的自适应交叉和变异概率公式及多种群遗传算法实现快速收敛及全局优化的效果。仿真算例验证了本文提出算法的有效性和可行性。