FPD-GA求解多目标柔性作业车间调度问题

王 博，陆宝春

（南京理工大学 机械工程学院，江苏 南京 210094）

1 引言

长久以来，如何利用生产调度优化技术提高制造系统生产率、缩短产品加工周期一直是生产制造与管理领域的核心问题。作为传统作业车间调度问题的延伸，柔性作业车间调度问题（Flexible Job Shop Scheduling Problem，FJSP）打破了加工设备唯一性的约束，允许工序在可用设备集中的任一台上加工，更加符合车间生产实际的同时也增加了该问题的求解难度[1]。近年来，蚁群算法[2]、免疫算法[3]、禁忌搜索算法[4]以及粒子群算法[5]等智能启发式算法越来越多的被用于求解FJSP，并取得较好的效果。

遗传算法（Genetic Algorithm）由于其稳定的计算性能和突出的全局搜索能力被广泛用于求解FJSP。但局部寻优能力差，易过早收敛的缺点使传统遗传算法在求解该问题时准确性不高。因此，学者们不断地致力于改进传统遗传算法使其快速准确地获得最优解。文献[6]设计了一种非支配排序遗传算法用于提高求解FSJP的寻优能力；文献[7]结合遗传算法与瓶颈移动法解决柔性车间调度问题；文献[8]在免疫算法的基础上融入遗传算子提出了一种遗传免疫算法。

定点扰动-遗传算法（FPD-GA）为了避免算法早熟并增强局部搜索能力，一方面用复合选择策略代替比例选择算子，保证优良个体遗传的同时降低劣势个体淘汰率，维持了种群的多样性；另一方面定量分析种群收敛程度[9]，并融合模拟退火算法和免疫算法，设计定点扰动机制，避免算法陷入局部最优。最后通过实例验证改进算法的可行性。

2 FJSP数学模型建立

车间调度问题可描述为：离散制造车间共有m台机器｛W1，W2，…，WM｝，需完成n个工件｛J1，J2，…，Jn｝的 p 道工序，每道工序Oij的加工设备不唯一，并且相同工序在不同设备上的加工时间不相同。优化调度的目标是为每道工序安排最合适的设备，并在工序不干涉的前提下规定各台设备的工件加工次序，使整个制造系统达到最佳状态。同时，加工过程中应满足以下约束条件：

（1）在某一时刻，工件Ji的某道工序Oij只能在指定的机器Wk上加工，并且加工时间tijk已知。

（2）不同工件的工序相互独立，同一工件的各道工序按规定的工艺流程依次进行。

（3）在t=0时刻所有设备可以被使用，所有工件可以被加工。

针对实际生产需要，选择以下目标为制造系统的性能指标，并构建多目标适应度函数：

（1）最小化工件最大完工时间。设Di为工件Ji的完工时间，其目标函数可表示为：f1=Min｛Max｛Di，i=1，2，…，n｝｝

（2）最小化设备最大负荷。设Lk为机器Wk的生产负荷，采用设备的工作时间表述其生产负荷，该目标函数可表示为：

（3）最大化设备使用率。最大化设备使用率在于使设备负荷均衡化，采用所有设备中最大与最小工作时间的差表述机床负荷均衡化：f3=Min（Max（Lk）-Min（Lk））

已有的算法研究中，多目标适应度函数的设计策略主要有加权策略、目标设计策略和非劣解等级优先策略。考虑到兼顾各个性能指标的同时尽可能的减小计算量，采用加权策略在可行域中寻找最优解，并用以上三个目标函数构建多目标适应度函数：

F=ω1f1+ω2f2+ω3f3

3 FPD-GA求解FJSP

3.1 FJSP中遗传算子设计

3.1.1 编码与解码

对于柔性车间调度问题，染色体编码在反映出工件加工顺序的同时，还要体现各道工序所在的加工设备，基于工序或操作的单一编码形式很难实现该问题的求解。因此采用双倍染色体编码形式，即一对相互关联染色体对应一个调度解，其中第一条染色体采用基于工序的编码，用于确定所有工件各道工序的加工次序，另一条染色体为基于分配机器的编码，用于为工序染色体分配加工设备。通过工序和机器染色体共同表达柔性车间的调度解。一个（3×5）调度问题编码方式，如图1所示。

图1 双倍染色体编码Fig.1 Form of Double Chromosome Encoding

针对上述的编码方式，在解码时首先将双倍染色体解码为机器矩阵和加工时间矩阵，然后按照工序染色体序列，安排每道工序到对应机器染色体指定机床的最佳加工时刻，最终得到调度解。

3.1.2 交叉算子

交叉操作是通过随机交换两个个体的部分基因，从而形成具有更优秀基因组合的新个体的过程。由于编码的特殊性，为了避免非法解的出现，采用基于染色体对的多父代交叉操作。具体实施步骤：（1）将所有工件划分为两个互补的非空子集G1和G2，并在种群中随机选取三个父代个体 P1、P2、P3；（2）对 P1进行顺序操作，去除 P1中所有属于G1的基因信息并用0代替，得到新染色体对，同理，去除P2中所有属于G2的基因信息，得到新染色体对；（3） 对 P3进行顺序操作，用P3中属于G1的基因信息按次序替换中的0基因位，得到子代个体C1；同理得到子代个体C2。

3.1.3 变异算子

为了保证变异操作后解的可行性，将该操作分为工序染色体变异和机器染色体变异两部分。对工序染色体采取插入式变异：随机生成两个不同的整数S1和S2，将第S1位的基因插入到第S2位的基因前，得到新的工序染色体；对于机器染色体：遍历整条染色体，查询每一个基因位的取值是否包含在对应工序的可用机器集内，如不包含，则在该可用机器集内随机抽取一台机器编号替换当前基因，由此得到可行的机器染色体。

3.2 遗传算法的改进

在求解柔性制造车间调度问题时，采用传统遗传算法通常会出现局部搜索效率低，过早陷入局部收敛等问题。分析出现问题的原因有两个：（1）比例算子使个别优势个体大量遗传，导致种群多样性急剧下降；（2）进化后期的种群个体趋于相似，交叉与变异操作不容易破坏父代个体性状，算法难以跳出局部最优。

针对上述分析原因，FPD-GA通过改进选择操作、设计定点扰动策略两个方面改进传统遗传算法。

3.2.1 复合选择策略

传统遗传算法采用的比例选择操作能够使种群快速地逼近最优解，但也淘汰掉了可能包含优良基因片段的劣势个体，使种群过早的陷入收敛状态。为了避免这一现象的发生，FPD-GA采用精英保留和轮盘赌的复合选择策略，在保证优良个体遗传的同时降低劣势个体淘汰率，维持了种群的多样性，其步骤：（1）计算个体x的适应度值Fi和种群整体适应度平均值；（2）当 Fi＜时，该个体x被保留；当Fi≥时，以一定概率p接受x，其中p=1/e（Fi-¯F）；（3）以轮盘赌的方式抽取大于平均适应度的个体，补充种群达到要求的种群规模。

3.2.2 定点扰动策略

算法进化后期，优势个体大量集中于最优解附近，种群进入收敛状态，但此时无法判断种群是否收敛于全局最优解，为了避免种群早熟收敛，提出定点扰动策略。

定点扰动策略的设计以模拟退火算法思想为基础，借鉴了免疫算法的疫苗接种机制。当种群处于收敛状态时，强制改变种群中优势个体的基因片段，不同于模拟退火算法的随机扰动，该策略通过计算优势群体等位基因的相似度，改变指定基因位上的基因，并选择性地保留扰动后的个体，驱使群体向最优解进化。但过于频繁地定点扰动会干扰正常的进化趋势，不利于算法快速寻优，因此，在对GA收敛状态多次分析的基础上，FPD-GA引入种群收敛度指标（其中为小于群体平均适应度值的个体的适应度平均值，Fmin为当代种群的最小适应度值），用于判断种群是否进入收敛状态，并选择性地触发定点扰动机制。

具体步骤：（1）计算种群收敛度指标Δ，当Δ小于收敛系数ε时，触发定点扰动机制；（2）对所有个体的适应度值从小到大排序，抽取适应度值前20%的个体组成精英群体Q；（3）计算Q中工序染色体第i个基因位上等位基因的相似度ηi，即ηi=nmax/nQ（i=1，2，…，np）。其中nmax—染色体第i位上出现频率最高基因的频数；nQ—Q中工序染色体总数；np—工序染色体基因数；（4）对ηi从小到大排序，设定前r个基因位为扰动基因位，对工序染色体扰动基因位上的基因进行位置互换，对机器染色体扰动基因位上的基因进行单点变异；（5）对扰动后的个体，计算适应度值，若≤Fi，则用扰动后的个体代替原个体，若＞Fi，以概率 Pt接受扰动后的个体。其中

图2 FPD-GA流程图Fig．2 Flow Diagram of FPD-GA

FPD-GA流程图，如图2所示。FPD-GA的主要实现步骤如下：

（1）设定参数。设定种群规模N，迭代最大次数T，交叉概率Pc，变异概率 Pm，扰动系数 r，收敛系数 ε，适应度函数权重 ω1、ω2、ω3；

（2）初始化种群。随机产生由工序染色体和机器染色体组成的种群个体，并设迭代次数t=0；

（3）适应度值评价。计算每个个体的适应度值Fi，并获得最小适应度值Fmin和适应度平均值F¯；

（4）检查算法终止条件。如果t≥T，输出最优解Fmin，否则执行步骤（5）；

（5）选择操作。执行复合选择操作，得到新的种群；

（6）交叉操作。对满足交叉概率的种群个体进行多父代交叉操作；

（7）评价种群收敛程度。计算当前种群收敛度Δ，当Δ＜ε时，转入步骤（9），否则执行步骤（8）；

（8）变异操作。以设定的变异概率对选中个体进行变异，返回步骤（3）；

（9）定点扰动操作。按照定点扰动策略对精英群体执行定点扰动。

（10）令 t=t+1，返回步骤（3）；

4 实例验证与结果分析

为了验证改进算法的有效性，以某液压油缸零部件生产车间A小组生产计划为实例，测试改进算法。该实例中共有9个工件，每个工件有4道工序（车、铣、钻、镗），共有12台设备，其中M1、M2、M3、M4、M5、M6 可用于车，M4、M5、M6、M7、M8 可用于铣，M4、M5、M9、M10 可用于钻，M5、M6、M11，M12 可用于镗。工序加工时间表，如表1所示。

表1 工序加工时间表Tab.1 Schedule of Procedure

设种群规模N=60，迭代次数t=1000，交叉概率Pc=0．8，变异概率Pm=0．05，扰动系数r=8，收敛系数ε=0．9，适应度函数权重ω1=0．4，ω2=0．3，ω3=0．3。利用 MATLAB 对实例进行仿真计算，并得到最佳调度方案。传统遗传算法（SGA）和FPD-GA收敛曲线，如图3、图4所示。SGA、自适应遗传算法（AGA）和FPD-GA的实例计算结果比较，如表2所示。采用FPD-GA计算实例的最佳调度优解，如图5所示。

图3 传统GA收敛曲线Fig．3 Convergence Curve of Traditional GA

图4 FPD-GA收敛曲线Fig．4 Convergence Curve of FPD-GA

通过对比图3图4可以看出：传统遗传算法在进化初期迅速进入收敛状态，优势个体大量遗传，平均适应度值变化平缓且不断趋近最小适应值，种群一直保持收敛状态；而FPD-GA在复合选择策略的影响下平均适应度值波动式减小，当进入收敛状态后触发定点扰动机制，使种群跳出局部最优值，不断朝全局最优值进化。通过表2数值对比，采用FPD-GA对实例求解，与其他算法相比，适应度函数分别减小了7.4%、3.7%，各项指标也明显优于SGA和AGA的计算结果，验证了FPD-GA的有效性。

表2 算法仿真计算结果对比Tab.2 Comparison of Simulation Results

图5 最佳调度方案Fig.5 Optimal Scheduling Scheme

5 结论

在应用遗传算法的基础上引入复合选择操作，并设计定点扰动策略，提出了一种融合遗传算法—FPD-GA。FPD-GA继承了遗传算法全局搜索能力突出的优势，同时克服了局部寻优能力差的缺陷，能快速地摆脱局部收敛的状态，向全局最优解的方向进化。通过生产实例验证，该方法在解的质量上有较大提升和改善，是一种高效求解FJSP的方法。