□ 沈建涛 □ 黄宗南

上海大学 机电工程与自动化学院 上海 200072

置换流水车间作业调度 （Permutation Flow-shop Scheduling Problem，PFSP）是生产调度中的典型问题，其特点是工件的加工路线一致且在每台机器上的加工顺序都相同，属于NP-hard（非确定性多项式）问题。到目前为止，应用在该问题上的调度优化算法有很多，尤以智能算法应用研究最为广泛，诸如遗传算法、蚁群算法、模拟退火算法、免疫算法和混合算法等。

免疫遗传算法保留了遗传算法的搜索特性，又通过免疫机制在很大程度上避免了早熟收敛，提高算法的寻优速度。疫苗是免疫遗传算法的关键技术之一，有许多研究者在该方面做了不少研究［1-5］，但应用于流水车间作业调度问题的研究还较少。

本文用免疫遗传算法求解PFSP问题，在疫苗方面，提出双疫苗技术，以改善寻优速度和质量。

1 PFSP问题的数学模型

式中：σi为在某个加工顺序 π=（σ1，σ2，……，σn）中第 i个位置上的工件序号；n为工件总数；m为工序总数（或称机器数）；k 为机器序号；tσi,k为工件 σi在工序 k上的加工时间；Sσi,k-1为工件σi在机器k上的开工时间；Cσi,m为工件σi的总完工时间。

式（1）表示调度的目标，使作业σn在最后一台机器上的最大完工时间最小化，也就是生产力最大；式

该问题的数学模型如下：（2）表示工件的开工时间必须大于等于0；式（3）表示工件σi的第k道工序必须在第k-1道工序完成后才能开始；式（4）表示在同一台机器上不能同时加工不同的工件，即工件σi只有当工件σi-1在该台机器上加工完成后才能进行加工。

2 免疫遗传算法的设计

免疫遗传算法的操作流程如图1所示。

第一步，运行开始。确定数学模型中的目标函数、约束条件及免疫遗传算法运行参数。

第二步，编码和解码，产生初始种群。PFSP问题的编码方式采用基于工件的自然数编码方式，每个染色体由n个代表工件序号的基因组成。例如，对于5个工件的 PFSP 问题，假设工件的加工顺序是 J2、J5、J4、J1、J3，可将其编码为：（2 5 4 1 3），该条染色体则表示工件进入流水线的顺序为：工件2→工件5→工件4→工件1→工件3。而上述编码机制已经表示工件在各机器上的加工顺序，因此无需解码。

▲图1 免疫遗传算法的操作流程

第三步，确定由目标函数到个体适应度、浓度的评价规则。个体的适应度根据目标函数的方向与适应度值变化方向相同的原则，即要求总完工时间越小，适应度值越大，采用的适应度函数为目标函数的倒数，其中在总完工时间计算时依工序加工顺序，按照染色体中各基因顺序依次加工，计算过程中满足式（2）～式（4）要求的约束，获得式（1）的Cmax值；个体的浓度采用基于矢量距［8］的计算方法，个体矢量距越大，浓度越小。

第四步，记忆细胞库更新。提取出好的个体存入记忆细胞库中，淘汰其中适应度最差的个体。

第五步，遗传操作。选择操作，即个体的促进与抑制，用轮盘赌选择算子对个体选择并采用精英策略；交叉操作，即采用单点交叉算子；变异操作，即采用交换变异算子。

下一步进行免疫操作，包括双疫苗的构建与接种、免疫选择。

3 双疫苗技术

3.1 双疫苗的构建

常用疫苗提取方法［10］有：依据待求问题的先验知识；依据进化环境即染色体基因。本文采用最佳个体疫苗并进行改善，属于后者。

免疫疫苗的作用是利用局部特征信息加快寻找全局最优解的过程，而进化前期，种群的最佳个体的质量不够理想，导致最佳个体疫苗的接种效果不佳，影响算法的寻优速度，因此，采用一个较好的疫苗个体进行改善，以提高算法的寻优速度。

该疫苗在文中命名为前置疫苗，在进化初期，其质量相较于当前种群的最佳个体更优，而在当前种群的最佳个体质量优于该疫苗时，改由最佳个体作为疫苗。在此将两疫苗相结合，并称为双疫苗技术，相应的，最佳个体疫苗可称为单疫苗技术。

3.1.1 前置疫苗的制作方法选择

（1）前置疫苗的要求。个体质量越好的疫苗其接种效果就越好，越符合疫苗的要求，但是好疫苗的制作相当困难，计算时间也会随复杂程度的提高而增加，从而影响整个寻优过程所花费的时间。此外，最佳个体疫苗的质量会随着种群的进化越来越好。因此，前置疫苗只要质量适中、易制作且计算时间短即可。

（2）前置疫苗制作方法的选择。在求解PFSP问题的常用方法中，精确算法只适用于小规模问题，搜索算法虽优化性能高，但操作较复杂，且两者优化时间较长，而启发式方法的计算时间短且操作简单，能迅速找到一个近似最优解，依此制作疫苗，使算法寻优过程所花费的时间较少，因而选择启发式方法制作前置疫苗。

常用的启发式方法中，优先权法虽然在生产实践中也被应用，但其精确度不高；而启发式算法包括经典和混合两种：经典方法诸如Palmer法、CDS法、RA法、NEH法等，算法简单，能以较短的计算时间获得较好的解，其中NEH法已被证明是求解性能最佳的［9］；而混合启发式算法诸如LR-FPE、LR-BPE等，计算时间相对NEH法长［11］，依其制作疫苗则会使算法的计算时间较长。因此，综合考虑计算时间和求解质量的平衡性，本文选择NEH法作为前置疫苗的制作方法。

3.1.2 NEH算法制作前置疫苗

NEH算法获得工件加工序列的步骤为：第一步将n个工件按总加工时间进行降序排列；第二步单独考虑开始两个工件，并以极小化部分加工全长为目标将它们排序；第三步将初始排列中的第i个工件插入到前面i个可能位置中的一个位置，使部分加工全长最小，直至排序完毕，获得工件加工序列。

在双疫苗的免疫遗传算法的实现流程上，相比于图1，还需在开始后进行NEH疫苗的制作以及在最佳个体疫苗提取完毕后对两者进行比较，选择适应度值较优的疫苗个体。

3.2 疫苗接种

从遗传操作后的种群中选择一定数量的适应度较差的个体进行接种，接种时随机选择疫苗个体中的一个基因位上的基因，置换被接种个体相应位置的基因并修正染色体，接种完成后的免疫选择一般分为免疫检测和退火选择两步完成。

根据上述实现设计，用MATLAB软件编制采用双疫苗技术的免疫遗传算法，实现PFSP问题的求解。

4 实验分析

实验采用标准测试案例Rec07（20×10，20工件10机器），其标准最优解为1 566。

实验中的运行参数：种群规模50，交叉概率0.8，变异概率0.15，迭代次数500，选择概率调节系数0.5，记忆细胞库中个体为一个，疫苗接种个体比例为10%，退火温度为300℃；做5组实验，每组运算10次，且使用相同的初始种群。

NEH算法获得的Rec07问题的解为1 626，其调度方案为［18 13 10 1 17 19 9 2 12 3 8 4 5 15 11 16 6 7 20 14］，将该结果作为前置疫苗。

（1）总体数据分析。表1记录各组实验获得的最好解及其第一次出现的次数及世代数。

表1 两种疫苗的实验数据比较

▲图2 前置疫苗被使用世代总数内的比较统计

▲图3 Rec07问题最好解的甘特图

由表中数据可知，单疫苗和双疫苗的免疫遗传算法每组实验第一次运算能搜到解1 584，但后者寻找到该解的搜索次数更多，并快了102的世代数，这说明其寻优速度更快。此外，在5组实验中，双疫苗的免疫遗传算法最终搜索到的解更优。

（2）前置疫苗作用剖析。为比较两种疫苗的接种效果差异，统计前置疫苗被使用世代总数内的接种成功比例和接种成功个体参与进化的比例。设疫苗的接种成功个数之和为A，每代接种个体数之和为B，接种成功个体参与交叉操作的个数之和为C。

由式（5）和式（6）可知，接种成功比例越高，说明接种成功的个体数越多，而参与进化比例越高，则说明接种成功的个体参与交叉的个体数越多。

表2 前置疫苗被采用的世代总数

表2表示NEH制作的前置疫苗在第一次运算时被采用的世代总数，依此统计相应指标如图2所示。

由表2可知，前置疫苗在第一次运算中均得到了使用，达到了预期效果。从图2可以看出，前置疫苗的接种成功比例（◆P）及接种成功个体参与进化的比例（▲Q）均更高，说明其接种效果更好，从而促使了寻优速度的加快。

综上所述，在Rec07问题上，前置疫苗的作用使双疫苗的免疫遗传算法的寻优速度更优。最好解1 572的调度方案之一［17 13 18 12 9 1 8 10 6 3 4 5 2 7 15 19 11 16 14 20］的甘特图如图3所示。图中横坐标表示工序号，纵坐标表示加工用时，图中的数字代表工件号，线段长度代表工件的加工时间。

5 结论

本文提出一种双疫苗技术，进化前期由NEH算法制作前置疫苗，在当前种群最佳个体质量优于该个体质量时，改由最佳个体疫苗进行接种。通过对置换流水车间调度标准案例的求解测试，显示了该方法在寻优速度和解的质量方面均优于只采用最佳个体单疫苗的免疫遗传算法。

［1］ 黄雨田,于彩燕,段富，等.免疫算法解决车间生产调度问题方法综述［J］.计算机工程与科学,2010,32（6）:135-137.

［2］ Soheil Samii,Yanfei Yin,Zebo Peng et al.Immune Genetic Algorithms for Optimization of Task Priorities and FlexRay Frame Identifiers［C］.15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications，Beijing,China,2009.

［3］ 庞留勇,曹炬,张燕.基于动态疫苗库的免疫遗传算法解决车间调度问题［J］.计算机工程与科学,2010,32（2）:124-127.

［4］ 信宁宁,黄宗南.基于最短处理时间疫苗的免疫遗传算法优化 FJSP 问题［J］.机械设计与研究,2013,29（3）:53-55.

［5］ 张顺,徐震浩,顾幸生.用改进的协同免疫算法求解Flow Shop 调度问题［J］.东南大学学报（自然科学版）,2012（A1）:157-162.

［6］ 方贤进,李龙澍,钱海.基于人工免疫的网络入侵检测中疫苗算子的作用研究［J］.计算机科学,2010,37（1）:239-242.

［7］ 吕岗,陈小平,谭得健.免疫算法抗体浓度调节定义的改进［J］.数据采集与处理,2003（1）：44-48.

［8］ 黎群.流水车间作业排序中的改进NEH算法［J］.系统工程方法理论应用,1999,8（4）:68-71.

［9］ 黄友锐.智能优化算法及其应用［M］.北京：国防工业出版社,2008.

［10］王凌.车间调度及其遗传算法［M］.北京:清华大学出版社,2003.