徐 雨，黄海松，胡 涞

（贵州大学现代制造技术教育部重点实验室，贵州 贵阳 550025）

1 引言

车间作业调度问题（job shop scheduling problem，JSP）是企业制造系统中的一个关键环节，其通过合理的安排零件加工时间和次序、合理的分配现有资源来制定在生产过程中的生产计划。JSP问题直接关系着企业管理及其生产效率。有效的优化JSP问题，能够降低企业生产成本、提高生产资源的利用率、快速响应市场的需求，从而提高企业竞争力。JSP属于NP（nondeterministic polynomial）问题[1]。目前应用在车间作业调度问题的优化算法主要有免疫算法[2]、遗传算法[3-4]、粒子群算法[5]、蚁群算法[6]和模拟退火算法[7]等，而且这些算法在JSP方面都拥有杰出的成果。免疫遗传算法（Immune genetic algorithm，IGA）是一种免疫算法与遗传算法相结合的混合算法，其相比较于一般的遗传算法，在种群进化过程中，免疫遗传算法通过免疫操作能有效的提高算法的搜索能力和加快算法的收敛速度。免疫遗传算法已经被应用到多个研究领域，车间调度问题[2]也包括在其中。文献[8]对免疫算法的产生和发展进行了概述，且对免疫算法的发展前景进行了展望。文献[9]中设计了抽取和接种疫苗的免疫操作，即将加工机器的基因片段作为疫苗，并以加工机器为基准接种疫苗，此算法有效的提高了算法的准确性与收敛效率，但算法在求解较大规模的车间问题时偏差较大。文献[10]中设计一种改进的优先操作交叉算子，同时重新设计了免疫算子，该算法能对较大规模的车间调度问题得到很好地解决，但随机运算次数过多，运算时间较长。文献[11]中将免疫遗传算法和模拟退火算法结合使用，利用分解策略对车间调度进行求解，该算法在抑制种群退化，防止算法陷入局部最优和加快算法的收敛速度方面做出了贡献，但就精英个体选择方面考虑欠佳。为此，将模拟退火算法的局部搜索理论与免疫遗传算法的全局性、多样性和自适应性结合起来，互相取长补短，形成性能优良的全局寻优的混合免疫遗传算法，并设置了自适应精英选择操作，最后将其应用在作业车间调度问题的求解中。

2 车间作业调度问题描述

车间作业调度问题（JSP）主要研究：n个工件，在m台机器上加工完成，每个工件i的工序数为oi，每个工件的不同工序在不同的机器上加工完成，其相应的加工时间也各不相同。假设：（A）同一机器，可以加工多道工序，但是同一时刻最多只有一个工件在上面加工。（B）每个工件的每道工序加工机器和时间已知。（C）工序开始加工后，不能中断加工。（D）不同工件的工序加工没有先后顺序的要求。（E）同一工件在加工过程中，有预设的加工顺序。数学符号定义，如表1所示。

表1 数学符号定义Tab.1 Mathematical Symbol Definition

3 求解JSP问题的改进IGA算法

3.1 编码与解码

遗传算法在车间作业调度问题（JSP）方面的编码方式主要有两种，即间接编码与直接编码。其中，间接编码的染色体是由一组工件的分配规则编码而成，其调度方案则是由分配规则序列得到的。而直接编码的染色体直接由一个调度方案编码而成。

考虑到直接编码方式编码和解码方式简单、柔性高和防死锁等优点，采用一种基于工序的直接编码方式[12]。直接编码过程就是：在求解有m台机器加工n个工件的JSP问题时，假设每个工件有m道工序，这些工序分别在m台机器上加工，所以编码的染色体组成的基因个数为n*m，每条染色体都可视为一个调度方案，染色体中同一工件的加工工序序号相同。在一条染色体中，若同一工件的加工工序序号第k次出现，则这个第k次出现的基因表示这一工件的第k道工序。例如：一个3×3的JSP问题，如表2所示。可将它的一个工序序列设为［3 1 1 2 3 2 2 3 1］。其中，1，2，3分别表示工件wp1，wp2和wp3，工序序列中从左到右三个1分别表示工件wp1的第一道工序，第二道工序和第三道工序，2和3同1类似。

表2 一个3＊3的JSP问题Tab.2 A 3＊3 JSP Problem

解码就是将计算机语言转化到实际问题的一种映射过程，在车间作业调度问题中，解码就是将染色体转化成一个调度方案。采用的解码方法是一种插入式贪婪解码算法[13]。贪婪解码过程为：首先按照染色体上加工工序的从左到右依次降低工序的优先权重，然后安排染色体上的工序序列的第1道工序进行加工，再然后依次安排各工件剩余工序，并将其插入到对应机器上可行的最佳加工时刻加工，最终达到所有的加工工序都安排在对应机器上最佳可行的时刻加工。例如：上述的3×3的调度问题，其中一条染色体为［3 1 1 2 3 2 2 3 1］，对应加工时间序列为［1 3 2 2 3 2 3 3 4］，机器序列表述为［2 1 3 2 3 1 3 1 2］，该染色体通过贪婪式解码后可得到：机器1上的工件加工顺序为1-3-2，机器2上的工件加工顺序为2-1-3，机器3上的工件加工顺序为2-3-1。使用贪婪解码方法与半主动解码方法，如图1、图2所示。由图可知使用一般解码方法的时间为11，而使用贪婪解码的时间为10。

图1 贪婪解码方法Fig.1 Greedy Decoding Method

图2 半自动解码方法Fig.2 Semi-Automatic Decoding Method

3.2 精英保留策略

在抗体评价过程中，一方面提高了适应度高的个体的选择概率，而另一方面又降低了浓度高的个体的选择概率。而在抑制高浓度的个体过程中，很容易丢失最优解。所以利用精英保留策略来保留已获得的优质的进化成果。传统的精英保留策略只保留某一固定数量适应度最高的个体，这种保留策略不利于算法的收敛，且容易导致算法陷入局部最优。基于此问题提出了一种自适应精英保留策略。

为了确定种群进化程度，引入了成熟度的概念。若单个抗体v的适应度和浓度分别为Agv，Cv，则成熟度为：

式中：M—种群进化的成熟度；α—常数，为了加权适应度与浓度的响。

精英保留在种群的成熟度较低的时候应该保留较多的精英个体，加快收敛速度，成熟度较高时，选择较少精英个体，提高种群的多样性。所以，其保留精英个体数的公式为：

式中：Ne—精英保留个体数；N—抗体总数；b—预设正整数，防止初期保留太多精英个体，导致算法陷入局部最优；ceil—向上取整。

3.3 变异算子

为了有效的提高算法的收敛速度和避免算法陷入局部最优，该算法将变尺度变异与自适应概率变异进行了融合，提出了混合变异算子。其中，自适应变异概率为：

式中：pm—变异概率；farg—群体的平均适应度值；fmax—群体最大适应度值；f—变异个体适应度值；取pc1=0.1，pc2=0.001。

在算法早期，种群大多数是由随机产生的，离最优解相差甚远，种群中的大多数抗体的适应度低，大概率的采用反转变异可以提高算法在早期的查找效率。在算法后期，种群抗体的适应度高，如果也采用反转法变异将会产生过多的冗余信息。为了避免盲目搜索，提高算法执行效率，又不至于陷入局部最优，该算法采用基于自适应变异概率的小步成熟机制的换位变异法进行变异操作。

混合变异算子的流程为：

（1）计算当代种群平均适应度与需要变异抗体的适应度。

（2）比较（1）中两适应度的大小，若变异抗体适应度大于平均适应度，选择小步成熟机制的换位法变异；若变异抗体适应度小于等于平均适应度，则采用反转变异法

（3）根据自适应变异公式计算变异概率，开始变异操作。

3.4 免疫算子

3.4.1 疫苗的提取与接种

免疫操作分两步进行，即提取疫苗和接种疫苗。适当的进行疫苗注射可以有效的避免种群退化和提高种群的适应度，从而大大加快了算法的收敛速度和提高算法的寻优能力。

这里算法所采用的疫苗提取方法为基于加工机器的基因片段提取疫苗[8]。

提取疫苗的流程为：

①将上代抗体中亲和力最大的若干个体抽取出来。

②将抽取出来的抗体按加工机器打碎成基因片段，将所得到的基因片段保存在疫苗库中。

接种疫苗是利用前面提取的疫苗来修改所选的部分个体染色体的某些位置的某些基因，从而有效的避免种群退化和提高种群的适应能力。

疫苗接种操作如下：

（1）将父代种群的部分个体选取出来。

（2）随机选取疫苗库中的疫苗作为注射疫苗。

（3）取第（1）步操作中的未注射疫苗的一个个体作为疫苗注射对象。

（4）将疫苗的基因顺序代替注射对象同一机器所对应位置基因的顺序。

（5）重复（2）到（4）步操作，直到第（1）步操作所选取出来的个体全部注射疫苗。

3.4.2 抗体评价及退火免疫选择

以抗体v的繁殖概率ev即免疫选择率作为个体的评价标准。繁殖概率是由抗体的亲和度与该抗体的浓度共同决定的。利用繁殖概率这种选择机制选择抗体既有效的鼓励了适应度高的个体，又适当的抑制了浓度高的抗体，其计算公式为：

为了更好地接受适应度高的抗体，并且适当的抑制浓度高的抗体，提出了基于抗体评价的模拟退火选择。

模拟退火选择可以分为检测抗体和选择抗体两步来进行。第一步，检测抗体，检测注射疫苗的抗体的适应度并将其适应度值与旧抗体的适应度值进行比较，若新抗体适应度更高，则以抗体的繁殖概率选取新抗体进入下一代；若旧抗体适应度更高，则说明出现了种群退化现象，需要进入第二步操作。第二步是利用模拟退火的Metropolis接受准则来决定接受新抗体的概率。即①若Δfv=

式中：T0—退火初始温度；γ∈（0，1）—降温系数；Tk—当前退火温度；p—Tk温度下的接受概率；Δfv—新个体适应度与旧体适应度之差；fvs—新个体适应度值；fv（s-1）—上一次迭代中旧个体适应度值。

3.5 算法流程

算法流程图，如图3所示。

图3 算法流程图Fig.3 Algorithm Flow Chart

（1）设置算法参数并随机初始化种群。

（2）设置迭代次数为0，计算种群的适应度、浓度以及期望繁殖概率。

（3）自适应精英选择精英个体，更新记忆库，对种群进行免疫遗传操作。

（4）进行选择操作，自适应交叉。

（5）判断抗体适应度是否大于平均适应度，若是，则计算变异概率pm2执行换位变异；若不是，则计算变异概率pm1执反转变异。

（6）退火选择，更新退火温度，更新种群。

（7）判断是否达到最大迭代次数，如果未到达进入下一次迭代，如果达到进入（8）。

（8）判断退火温度是否达到结束温度，若未达到返回（2），若达到输出最优解，结束算法。

4 计算结果和比较分析

为验证算法的有效性与高效性，下面用Muth和Thompson提出的著名的MT06作为该算法的测试基准。利用该算法不同参数对MT06问题仿真试验20次，取最优的算法参数，参数设置如下：种群规模为 47；交叉概率（0.6～0.9），初始值为 0.9；变异概率为0.01；阙值T为0.95；初始温度为10000；衰减系数为0.90；迭代次数为110。使用MATLAB2010b在Windows环境下运行。算法收敛曲线，如图3所示。由图4可知，混合免疫遗传算法在第四十次迭代就完成了收敛，找到最优值，说明了算法的高效性；最佳工件加工顺序图，如图5所示。得到最短生产时间为55s，达到最优，说明了算法的有效性。

图4 收敛曲线图Fig.4 Convergence Curve

图5 工件加工甘特图Fig.5 Workpiece Processing Gantt Chart

基于MT06问题的不同算法的比较，如表3所示。就MT06问题而言本算法比一般的IGA，SA算法得到最优解的概率要高很多，而且平均偏差仅为2.03%；不同算法性能比较，如表4所示。对于MT20问题，这里算法比其他算法得到的结果更优，对MT06和MT10问题，虽然各个算法都能得到最优值，但这里算法的出错率更低。综上所述，这里算法前期能够快速收敛，后期能够跳出局部收敛，防止“早熟”，显示了其良好的全局寻优能力。

表3 基于MT06问题的不同算法的比较Tab.3 Comparison of Different Algorithms Based on MT06 Problem

表4 不同算法性能比较Tab.4 Comparison of Performance of Different Algorithms

5 结论

通过对免疫遗传算法及模拟退火算法的了解，结合了两者的优点，提出了一种混合免疫遗传算法并用其求解了著名的JSP问题。通过仿真试验结果证明了算法的可行性和高效性。具体表现为：（1）算法通过对MT06问题的仿真，生成了最优的调度方案。其中，最大完成时间达到了最优的55s，说明了算法的可行性；算法在第四十次就达到了收敛，说明了算法的高效性。（2）就MT06问题而言，混合IGA算法比普通的SA算法和IGA算法击中最优解的概率更高，而且偏差更小。（3）在求解相对复杂的MT10问题时，混合IGA算法比普通的SA算法和IGA算法离最优解更近，离最优解相差只有1s。