改进的免疫模拟退火算法求解混合流水车间调度问题

黄 明，郝 倩，张春蕾，张志鹏

(大连交通大学 软件学院，辽宁 大连 116028)＊

0 引言

混合流水车间调度问题(Hybrid Flow-shop Scheduling Problem，HFSP)［1］，是由普通流水车间调度问题拓展而来的，具有多并行的flow shop问题，增加了求解问题的难度，是NP问题［2］.目前，针对混合流水车间调度问题已经提出了启发式方法［3］和分支定界法等，但这些算法通常只适用于求解小规模问题，并且很难保证解的质量.

免疫算法(Immune Algorithm，IA)是受生物免疫系统启发，在免疫学理论基础上发展起来的一种新兴的智能算法.它具有特有的自我调节机构，已经运用到多个研究领域，其中包括车间调度问题.文献［4］中提出了一种模糊免疫调度算法，该文献主要是对不确定条件下的流水车间调度问题的模型补进行分析，并用算法对该问题进行了求解，并未对算法进行太多的改进;文献［5］提出了一种双种群双倍体自适应免疫算法，并将算法应用到了多目标柔性作业车间调度问题中，虽然算法能够求得满意的结果，但是算法的结构设计复杂，运行效率不高;文献［6］将改进的免疫算法应用到了flow shop中，虽然算法提高了一定的自适应性，但是参数的设计比较复杂.文献［7］提出了一种混合免疫进化算法，但是种群规模的微小变化对算法的性能影响较大，也没有将该算法应用到车间调度中.虽然诸多的研究者对免疫算法进行了改进和优化，但是算法本身的基本问题并没有得到解决.免疫算法属于一种概率随机搜索算法，与其他进化算法一样，容易陷入局部最优，在算法后期，优秀的抗体产生新抗体时，优势不明显，从而使种群进化不明显.本文在免疫算法的基础之上，提出了一种改进的混合免疫算法，针对单一的算法往往表现出优化效果不佳的状况，借鉴免疫算法的自适应及群体多样性特点和模拟退火的局部搜索理论，将两者进行取长短，应用到混合流水车间调度问题的求解中.

1 混合流水车间调度问题描述

1.1 问题描述

典型的具有批处理功能的HFSP，至少有一个阶段的设备集大于1，HFSP的输入是待加工的工件，每个工件的加工路径相同，但是不同工件在不同设备上所需加工时间不同.

为保证模型的正确建立，HFSP通常要作如下假设:

(1)同一工件必须按其工艺顺序进行加工;

(2)一台设备同一时刻只能操作一个工件;

(3)工件在加工过程中不可被中断;

(4)工件可在每阶段的任意设备上加工.

1.2 建立数学模型

(1)约束条件:

1)顺序约束

ci，j≤ si，j+1，iϵ{1，2，…，n}，jϵ{1，2，…，m}

表示同一工件的前后工序需要满足的条件，只有前一工序加工完成后，才能进行下一工序的加工.

2)资源约束

ci，j=ck，j时，ci，j≤ sk，j或 ck，j≤ si，j，

其 中， i，kϵ{1，2，…，n}，jϵ{1，2，…，m}，ci，jϵMj.

表示第i和第k个工件的j工序安排在同一设备ci，j上，必须先完成前个工件的工序才能加工下件工件，即任一时刻该设备不能同时处理两个不同的工件.

3)时间约束

si，j≥ 0，iϵ{1，2，…，n}，j∈ {1，2，…，m}表示工件可以从零时刻开始加工.

ci，j=si，j+pi，j，iϵ{1，2，…，n}，jϵ{1，2，…，m}

同一阶段上，工序的开始时间与结束时间的关系，工序一旦开始加工就不会被中断.

(2)目标函数:

F=min max{cim，iϵ{1，2，…，n}}本文采用最大最小完工时间，即尽量使最后完工的工序完成时间最早作为调度目标.

模型中涉及到的具体参数:n为待加工工件数;m为加工工件所需的工序数，即阶段总数;Mj为第j道工序可供选择的并行设备数，j∈{1，2，…，m};pi，j为工件 i的第 j道工序的处理时间;si，j为工件i的第j道工序的开始处理时刻;ci，j为工件i的第j道工序的结束处理时刻;ci，j为工件i的第j道工序安排的设备.

2 改进的混合免疫算法

在免疫算法的早期，由于初始种群是随机产生的，所以其离最优解相差甚远，而在算法的后期已经接近最优解，如果在算法的早期和后期使用相同的变异方法会使得算法早期的收敛速度过慢且算法后期产生过多冗余的信息计算.免疫算法在进化过程中，会逐步积累具有优良性能的抗体，但是由于初始种群、进化环境、免疫算子和参数设定等因素的影响，经过一定代数的进化后，算法有可能进入一个局部平衡的状态，种群的抗体不会再有大的变化，导致算法不能求得全局最优解.

为加快算法的收敛速度，在算法的早期，采用反转法［8］对抗体进行变异，增大随机搜索的范围，较快获得接近最优解的可行解;而在算法后期，已经接近最优解时，采用小步成熟机制的换位法［9-11］对抗体进行变异.同时在算法的后期，以平均适应度值作为标准，把部分仍然未达到标准的个体从种群中分割出来，进行模拟退火选择，引导算法跳出局部最优.并且，改进算法在对高浓度抗体进行抑制时，为避免丢失已求得的最优解，采用精英保留策略.即在每次更新记忆库时，先将与抗原亲和度最高的若干个体存入记忆库，再进行后续操作.算法的整体流程可见图1.

图1 改进的混合免疫算法流程图

2.1 编码及解码设计

对抗体采用双层的整数编码方式，每个抗体表示全部工件的加工顺序.如果待加工的工件数为4，工序个数为2，则抗体为长度16的整数串.其中，抗体的前半部分编码表示所有工件在设备上的加工顺序，后半部分表示工件每道工序对应的加工设备号.

例如，对于分别有2个和3个并行设备的两级 HFSP，设备集M1={1，2}，设备集M2={3，4，5}，其中的一个抗体的编码为(2 3 4 1 1 2 3 4 1 2 2 1 3 2 1 1)

第一层编码:2 3 4 1 1 2 3 4

第二层编码:1 2 2 1 3 2 1 1

其中，第一层编码为前8位，表示工件的加工顺序为工件2→工件3→工件4→工件1→工件2→工件3→工件4;第二层编码为9～16位，表示工件各阶段对应的加工设备为设备1→设备2→设备2→设备1→设备5→设备4→设备3→设备3.

在免疫算法中，目标函数的取值不仅与可能解的数值有关，还与其在字符串中的编码位置相关.有效的编码方式可以表达更多的特征，增加抗体与抗原的匹配程度.本文的算法对抗体采用双层编码，每层编码均表示不同的含义，两层编码共同完整的表达了问题的解，提供了更多的解的信息，从而使每一个抗体都可以更准确的表达调度问题的解.

2.2 抗体评价标准的制定

在本算法中对个体的评价是以抗体的期望繁殖率为标准的.

算法中的期望繁殖概率设计由抗体的浓度和该抗体对应的适应度共同决定，抗体的期望繁殖概率决定了算法的选择机制.在进行选择时既鼓励了适应度高的抗体，又抑制了浓度高的抗体，从而有效了保证了种群的多样性.

一般的免疫算法在对抗体间的亲和力进行定义时，大多采用信息熵的方式.但是，基于信息熵的亲和力计算过程往往比较复杂，比较适合求解采用二进制编码的抗体，将此方法应用到整数编码的抗体上会有较大的误差.改进的算法采用的R位连续计算方式，该计算方式简单易行，加快了算法执行的效率，能够在一定程度上反应抗体之间的相似度.

2.3 精英保留策略

根据期望繁殖概率可以有效控制抗体的浓度，但是与抗原亲和度较高的个体也可能因为它的浓度过高而受到抑制，容易丢失最优解，所以采用精英保留策略，每次更新记忆库时先将与抗原亲和度特别高的若干个体存入记忆库中，然后再按照期望繁殖概率的大小从群体中选择抗体存入记忆库.

2.4 变异算子及模拟退火操作

在算法的早期迭代的过程中，为加快算法向最优解进化的速度，采用反转变异的方法.反转变异能够在解空间内进行大范围的成熟查找，提高算法在早期的查找效率.

在算法进行一定代数的反转变异以后，种群中的抗体基本已经接近最优解，成熟的反转变异法已经对算法不再适用，采用小步成熟机制的换位变异法，使得算法有效的避免盲目的搜索，提高了算法的执行效率.

免疫算法进化到一定程度之后可能达到某个局部的平衡状态，为避免此现象的产生，在算法后期加入模拟退火操作.模拟退火操作虽然能够增强算法的局部寻优能力，但是算法的执行效率也随之降低.为使种群质量更优，同时算法的效率更高，本算法对控制温度下降的函数参考文献［12］提到的一种自适应变温方法.当前温度可设为

T=ceil{T0［1-N/(M+1)］}

式中，N为当前迭代代数;ceil(*)表示对括号内的内容向下取整.

3 仿真测试和比较

为便于算法比较，选取文献［13］中使用的流水车间调度问题作为本文测试的对象.可以假设该调度问题加工工件数n=12，加工阶段m=3，各阶段对应的设备数为M1={1，2，3}、M2={4，5，6}、M3={7，8，9}.以文献［14］的最优子种群遗传算法，文献［15］遗传算法，以及文献［16］的免疫克隆选择算法作为比较对象，对算法进行性能分析.

本文所述的IASA算法，迭代次数M设为100，反转变异代数M1为30，种群规模sizepop为40，记忆库容量overbest为10，设置算法初始温度T0为1000，结束温度Tend为0.1，多样性评价参数Pm为0.6，交叉概率Pc为0.7，变异概率Pm为0.4，进行10次的仿真.文献［16］仅给出了ICSA一次实验的仿真结果，文献［14］、文献［15］给出了10次独立运行仿真结果，与本文算法相对比，结果如表1所示.

表1 统计结果比较

图2 免疫模拟退火算法收敛曲线

图3 工件加工甘特图

由表1可见，本文改进的混合免疫算法能得到的最优解为24，对应解的进化曲线和最优解的甘特图如图2和图3所示.从整体性能来看，改进的混合免疫算法能在10次独立运行中6次达到最小值，并且平均性能也优于其他三种算法.通过图2可以看出，本文算法在早期能够快速的进行收敛，提高了算法效率，同时又避免了早熟的现象，在搜索最优解方面也有较明显的优势.

4 结论

本文在对混合流水车间调度问题进行研究的基础上，针对有多台并行处理机的flow shop调度问题，建立了相应的调度模型，结合免疫算法和模拟退火算法的特点，提出了解决该问题的混合免疫算法，并对改进的算法进行了详细的分析.最后通过对典型的混合流水车间调度实例进行仿真实验，表明了算法可行性和有效性.进一步的研究工作是将免疫算法应用到多目标调度车间问题上.

［1］王凌.车间调度及其遗传算法［M］.北京:清华大学出版社，2003:138-145.

［2］唐立新，吴亚萍.混合流水车间调度的遗传下降算法［J］.自动化学报，2002，28(4):637-641.

［3］RIANE F，ARTIBA A，ELMAGHRABY S E.Sequencing a hybrid two-stage flow shop with dedicated machines［J］.International Journal of Production Research，2002，40(17):4353-4380.

［4］徐震浩，顾幸生.不确定条件下具有零等待的流水车间免疫调度算法［J］.计算机集成制造系统，2004，10(10):1247-1251.

［5］余建军，孙树栋，郝京辉.免疫算法求解多目标柔性作业车间调度研究［J］.计算机集成制造系统，2006，12(10):1643-1651.

［6］周安阳，戴青云，王美林，等.一种改进的免疫算法在车间调度中的研究［J］.中国制造业信息化，2012，41(19):16-18.

［7］刘星宝，蔡自兴，王勇，等.用于全局优化问题的混合免疫进化算法［J］.西安电子科技大学学报，2010，37(5):971-980.

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

［9］刘晓冰，吕强.免疫克隆选择算法求解柔性生产调度问题［J］.控制与决策，2008，23(7):781-785.

［10］常桂娟，张纪会.基于正交试验的免疫遗传算法在调度问题中的应用［J］.信息与控制，2008，37(1):46-51.

［11］ENGIN O，DOYEN A.A New Approach to Solve Hybrid Flow Shop Scheduling Problems by Artificial Immune System［J］.Future Generation Computer Systems，2004，20(6):1083-1095.

［12］李修琳，鲁建厦，柴国钟，等.基于混合遗传算法的混流混合车间协同调度问题［J］.中国机械工程，2012，23(8):937-938.

［13］王万良，姚明海，吴云高，等.基于遗传算法的混合Flow-shop调度方法［J］.系统仿真学报，2002，14(7):863-865.

［14］王金鹏，朱洪俊，周 俊.最优子种群遗传算法求解柔性流水车间调度问题［J］.计算机应用研究，2012，29(2):444-445.

［15］周辉仁，唐万生，魏颖辉.柔性Flow-Shop调度的遗传算法优化［J］.计算机工程与应用，2009，45(30):225-226.

［16］许爱军.基于免疫克隆选择算法的混合流水车间调度方法［J］.计算机应用于软件，2013，30(3):76-77.