多目标置换流水车间调度的改进食物链算法

陈可嘉　周晓敏

福州大学，福州，350108

多目标置换流水车间调度的改进食物链算法

陈可嘉周晓敏

福州大学，福州，350108

针对目标函数为最小化最大完成时间和总延迟时间的多目标置换流水车间调度问题，提出了一种改进的食物链算法。该算法在食物链算法的基础上，引入基于Pareto最优解的快速非支配性排序和个体拥挤距离计算，增强了算法的寻优性能。对OR-Library三个典型算例的优化比较表明，该算法在解的质量上明显超越NSGA-Ⅱ算法。

置换流水车间调度；多目标优化；食物链算法；Pareto最优解

0　引言

流水车间调度问题作为许多实际流水线生产调度的简化模型，是生产调度中的一个重要研究对象。在实际生产中，生产者追求的目标并不是单一的，往往要求生产能够满足多个目标。因此，多目标流水车间调度问题更加符合生产制造的实际情况，具有研究的现实意义。Ishibuchi等[1]提出了基于局部搜索的遗传算法，求解了以最小化最大完成时间和最大延迟时间为目标的流水车间调度问题。Ravindran等[2]分析了最小化最大完成时间和最小化总流程时间的双目标流水车间调度问题，设计了三种启发式算法。Yagmahan等[3]采用蚁群算法，解决了以最小化最大完成时间和总流程时间为目标的流水车间调度问题。Lee等[4]针对目标函数为最小化加权延迟时间和最大完成时间的流水车间调度问题，给出了遗传算法。多目标置换流水车间调度要求每台机器上工件加工顺序相同，是一类典型多目标流水车间调度问题，受到了众多研究学者的关注。Pasupathy等[5]研究了以最小化最大完成时间和总流程时间为目标的置换流水车间调度问题，提出了基于Pareto最优解的遗传算法。Lemesre等[6]应用精确并行方法，解决了目标函数为最小化最大完成时间和总延迟时间的置换流水车间调度问题。Qian等[7]探讨了具有有限缓冲区的同时最小化最大完成时间和最大延迟时间的多目标置换流水车间调度问题，给出了混合差分进化算法。Dubois-Lacoste等[8]将最大完成时间、总完成时间、无加权总延迟时间、加权总延迟时间组合成五类双目标置换流水车间调度问题，设计了基于两阶段局部搜索和Pareto局部搜索的混合算法。Arroyo等[9]针对最小化最大完成时间、最大延迟时间、总流程时间的多目标置换流水车间调度问题，提出了基于贪婪随机自适应搜索的启发式算法。不难看出，智能算法已逐渐成为求解多目标流水车间调度问题的重要工具，对于智能算法的探索加快了复杂多目标置换流水车间调度问题的求解，使得结果更加贴近实际需求。

近年来，国内学者对多目标置换流水车间调度问题的关注也越来越多。杨开兵等[10]将遗传算法与局部搜索相结合，求解了带调整时间的以最小化最大完成时间和最大延迟时间为目标的置换流水车间调度问题。董兴业等[11]针对最小化最大完成时间和总流程时间的多目标置换流水车间调度问题，给出了局部搜索算法。秦艳[12]采用改进交叉策略的遗传算法，解决了加权形式的多目标置换流水车间调度问题。显然，国内学者在研究多目标置换流水车间调度问题时，注重对现有算法进行改进，从而完善算法性能，提高算法精度。

食物链算法是模拟生态系统中食物链现象而提出的一种新型人工生命算法，具有鲁棒性强、并行处理容易等优点，已在供应链计划[13]、分销网络优化[14]等问题中取得了良好的应用效果。食物链与流水车间之间具有链式结构相似性，食物链算法对于多目标置换流水车间调度优化问题有着独特的优势。然而，从国内外已有文献来看，将食物链算法应用于流水车间调度问题的研究相对较少，将食物链算法与多目标置换流水车间问题相结合的研究更少。基于此，本文设计了多目标置换流水车间调度的改进食物链算法，通过算例分析，验证了算法的有效性。

1　问题描述

1.1多目标优化问题

假设求解多目标最小化问题，多目标优化问题的数学形式可描述为[15]

(1)

其中，x为决策向量，y为目标向量，X为决策向量x形成的决策空间，Y为目标向量y形成的目标空间。F()为将x映射至目标向量空间的优化函数，gi(x)≤0(i=1,2,…,h)为x需要满足的h个约束条件。

定义1Pareto支配。设Xf为多目标优化问题的可行解集，F(x)={f1(x),f2(x),…,fk(x)}为目标向量，xk∈Xf，xl∈Xf，则称xkPareto支配xl(简称支配，记作xkxl)。当且仅当下式成立时，xkPareto支配xl：

(2)

定义2Pareto最优解。如果在某一集合中不存在其他解x′Pareto支配x，则称x为该集合中的Pareto非支配解(简称非支配解)；如果x为多目标优化问题整个可行解集中的Pareto非支配解，则称x为该问题的Pareto最优解。

定义3Pareto最优前沿。一个多目标优化问题所有的Pareto最优解对应的目标向量集合，构成了该问题的Pareto最优前沿。

1.2多目标置换流水车间调度问题

流水车间调度问题是研究m台机器上n个工件的流水加工过程，每个工件以相同顺序依次经过各台机器的加工，同时约定每个工件在每台机器上只加工一次，每台机器一次在某一时刻只能够加工一个工件，各个工件在各台机器上所需的加工时间已知。进一步，若约定每台机器上各个工件的加工顺序相同，则称其为置换流水车间调度问题。

本文多目标置换流水车间调度问题的优化目标是：确定各个工件在每台机器上的最优加工顺序，使得最大完成时间以及总延迟时间达到最小，最大完成时间越小意味着机器的利用率越高，总延迟时间越小意味着所有工件满足交货期的总体情况越好。

对于多目标置换流水车间调度问题有如下的数学模型：

(3)

s.t.C(1,1)=t(1,1)

(4)

C(1,j)=C(1,j-1)+t(1,j)

j=2,3,…,m

(5)

C(i,1)=C(i-1,1)+t(i,1)

i=2,3,…,n

(6)

C(i,j)=max{C(i-1,j);C(i,j-1)}+t(i,j)

(7)

i=2,3,…,n;j=2,3,…,m

Ci=C(i,m)=max{C(i-1,m);C(i,m-1)}+t(i,m)i=2,3,…,n

(8)

Cmax=C(n,m)

(9)

ti=max{0,Ci-di}i=1,2,…,n;j=1,2,…,m

(10)

s(i,j)+t(i,j)≤s(i+1,j)i=1,2,…,n;j=1,2,…,m

(11)

s(i,j)+t(i,j)≤s(i,j+1)i=1,2,…n;j=1,2,…,m

(12)

s(i,j)+t(i,j)=C(i,j)i=1,2,…n;j=1,2,…,m

(13)

s(i,j)≥0,C(i,j)≥0i=1,2,…n;j=1,2,…,m

(14)

式(4)～式(9)表示最大完成时间Cmax的计算过程；式(10)表示工件Ji的延迟时间等于工件Ji完成时间和交货期的差值与零之间的较大者；式(11)表示在某一时刻，机器Mj上最多只能加工一个工件；式(12)表示所有工件的工艺路线均相同；式(13)表示工件Ji在机器Mj上结束加工时间等于该工件在机器Mj上开始加工时间加上加工时间；式(14)为非负约束。

2　算法设计

2.1食物链算法介绍

食物链算法是根据生态系统中食物链这一重要的生态现象，借鉴行为生态学理论，利用具有一定自主推理且自主决策、能够与环境动态交互的人工生命来仿真食物链物种之间的捕食行为和进化特征，所构造的一类具有食物链形式的人工生命算法。食物链算法的基本步骤如下[13-14]：

清华大学老校长梅贻琦说过，“大学之谓，非大楼也”。现在大学房子越盖越豪华，但是教授越来越不像教授，学生越来越不像学生，大学精神不断沦落，大学校园弥漫的学术不端氛围，令人忧虑。高校、科研机构担负着传承文化、弘扬正义的职责。如果为人师表者学术道德失守，不仅有辱学术尊严，还会误导学生、搞坏学术风气。韩愈说，“师者，传道、授业、解惑也”。教师除了教给学生学问外，更有义务教给他们做人的道理、做学问的道德。如果教师自身学术不端，即使道貌岸然给学生讲学术道德，学生也听不进去。

(2)觅食。人工生命个体在邻域范围内进行觅食，寻找最优的食物资源。若找到，则设当前最优食物资源位置为局部最优解，并增加能量Ee。若当前局部最优解优于历史全局最优解，则更新全局最优解。若没有找到，则消耗能量Ep。所有人工生命个体都要完成一次觅食搜索。

(3)位置更新。所有人工生命个体移动到当前最优食物资源位置。

(5)循环控制。每完成一次人工生命集的新陈代谢，迭代次数K增加1。若迭代次数K

2.2改进食物链算法设计

多目标优化问题的传统处理方法是给各个目标附加权重，将多目标转化为单目标优化问题，从而求得唯一最优解。然而在实际多目标优化问题中，各个目标之间往往是相互制约、相互冲突的，同时决策者对于权重系数的选择存在主观因素，因此求解出多目标优化问题的Pareto最优解集，更加有利于决策者制定正确的决策。NSGA-Ⅱ是公认的最为有效的多目标进化算法之一[16]，它对NSGA进行了改进，采用快速非支配排序，将种群中的个体进行分层，降低了计算的复杂性；通过计算个体的拥挤距离，判断个体的分布是否均匀，提高了Pareto最优解的分布性。基于以上优点，本文引入NSGA-Ⅱ的快速非支配排序和个体拥挤距离计算，改进食物链算法，用于求解多目标置换流水车间调度问题。改进食物链算法的流程图如图1所示，具体计算步骤如下：

图1　改进食物链算法流程图

(1)初始化。定义N个人工生命个体，构成初始人工生命集。人工生命个体包括3个部分：第一部分采用基于工序的编码方法，n个元素是n个工件号随机排序形成的可行解；第二部分的2个元素为根据该可行解计算出的2个目标函数值；第三部分的2个元素分别是根据第二部分函数值进行快速非支配排序得到的个体等级数以及计算得到的个体拥挤距离，在初始化阶段，该部分为空，在新陈代谢阶段，该部分将被计算。例如，对于工件数量n=4、机器数量m=3的置换流水车间调度问题，加工时间矩阵t和交货期矩阵d(本文加工时间和交货期均为量纲一参量)为

(2)觅食。在算法的觅食阶段，对人工生命个体中第一部分的元素排序进行调整，并重新计算第二部分的目标函数值。本文采用可变邻域实现觅食，通过可变邻域，使得觅食的方向多样化，提高觅食的遍历性。可变邻域设置为δ=δinitial-mod(K,10)×(δinitial/10)，其中，δinitial为初始邻域，mod(K,10)为求K/10的余数。为了保证至少调整两个元素，通过计算max(2,δn)，确定人工生命个体中需要调整的元素个数。对于步骤(1)所生成的人工生命个体Gk1，假设δinitial=0.5，K=6，因此δ=0.2，max(2,δn)=2。随机选出2个元素，假设为元素“4”和元素“1”，对这两个元素随机排序，得到新人工生命个体Gk2：(1-3-4-2)-(32-14)-(null-null)。对新个体和原个体进行非支配排序，可以看出，新个体的两个目标函数值都比原个体的两个目标函数值小，新个体支配原个体，此次觅食成功，个体更新。若新个体的两个目标函数值，一个比原个体大，一个比原个体小，则这两个个体处于同一非支配等级上，个体不更新；若新个体的两个目标函数值都比原个体要大，原个体支配新个体，个体也不更新；对于这两种情况，原个体没有觅食成功。

(3)位置更新。当人工生命集中所有人工生命个体且完成觅食行为后，形成一个新的人工生命集，其中的人工生命个体实现了位置的优化和更新。

(4)新陈代谢。在算法的新陈代谢阶段，选取成熟的人工生命个体繁殖产生下一代新的人工生命个体，以弥补死亡的人工生命个体，使人工生命集中的个体数量保持不变。在选择成熟人工生命个体时，引入快速非支配排序及个体拥挤距离计算的方法，代替传统的适应值计算比较，以便能够更加有效地选出成熟人工生命个体。

非支配排序就是按照Pareto支配的定义，确定人工生命个体的非支配性。快速非支配排序，是将人工生命集中的人工生命个体按照非支配性进行分层，每一层人工生命个体的非支配性相同。具体过程为：首先，找出当前人工生命集中的所有非支配个体并分配等级1；然后，排除该层非支配个体集，对剩下的个体进行非支配个体集搜索并分配等级2；重复这个过程，直到人工生命集中的所有个体都被赋予相应的等级为止。

通过快速非支配排序及个体拥挤距离计算，实现人工生命个体第三部分等级数和拥挤距离2个元素的赋值，进而完成新陈代谢。对人工生命个体进行快速非支配排序，赋予等级数。将人工生命个体按照等级数从小到大排序，选取前N/2个人工生命个体，采用与觅食行为相同的策略，产生N/2个新人工生命个体。将N/2个新人工生命个体与原来N个人工生命个体混合，再次进行快速非支配排序，更新等级数。对同一非支配层中的人工生命个体，计算拥挤距离，将人工生命个体按照拥挤距离从大到小排序。通过非支配等级和拥挤距离的双重排序，淘汰排序靠后的N/2个人工生命个体，保留前N个成熟人工生命个体形成新一代的人工生命集。例如，对于步骤(1)生成的Gk1和步骤(2)生成的Gk2，采用快速非支配排序对它们分配等级数，由于Gk2的两个目标函数值都要小于Gk1，因此Gk2分配等级1、Gk1分配等级2。同时，由于Gk2优于Gk1，Gk2产生一个新人工生命个体Gk3：(2-1-3-4)-(33-21)-(null-null)。对Gk1、Gk2、Gk3三个人工生命个体再次进行快速非支配排序，Gk1和Gk2等级不变，Gk3分配等级2。假设三个人工生命个体的拥挤距离分别为0.6、0.7、∞，则Gk1：(4-3-1-2)-(36-15)-(2-0.6)；Gk2：(1-3-4-2)-(32-14)-(1-0.7)；Gk3：(2-1-3-4)-(33-21)-(2-∞)。因此三个人工生命个体的排序为：Gk2-Gk3-Gk1。按照新陈代谢原则，淘汰Gk1。

步骤(5)循环控制。通过以上步骤，人工生命集完成了一次循环过程，达到最大循环次数后，算法终止。非支配等级为1的所有个体就是算法找到的一组Pareto最优解。

3　算例分析

3.1Pareto最优解比较指标

本文采用以下两个指标对算法求得的Pareto最优解进行比较：

(1)Pareto最优解的个数。通过将每种算法求得的Pareto最优解的个数进行比较，可以看出不同算法的搜索能力。个数越多，表明算法搜索能力越强。

(2)C指标。采用文献[15]中的C指标评价两种算法产生的Pareto最优解集A和B，C指标的计算公式：

(15)

C(A,B)表示B的Pareto最优解被A的Pareto最优解占优支配的个数占B的Pareto最优解总数的比率，它的取值介于0到1之间。当B中任何点都被A中某些点占优支配时，C(A,B)=1。当B中所有点都不被A中任何点占优支配时，C(A,B)=0。一般C(A,B)≠C(B,A)。该指标反映了解的质量及算法的收敛性。

3.2算例结果分析

以文献[16]提出的NSGA-Ⅱ作为参照算法，它克服了NSGA的缺点，是目前公认的最为有效的多目标进化算法之一。设置两种算法的群体规模均为200，最大迭代次数均为500，NSGA-Ⅱ的交叉概率和变异概率分别为0.9和0.1，改进食物链算法的初始邻域为0.5。在Intel Core i3-2350M CPU 2.30 GHz处理器、2GB内存、Windows XP系统下，以MATLAB实现两种算法，分别对三个典型算例运算15次，合并各次的解集，剔除其中的劣解，获得三个典型算例最终的Pareto最优解集(图2～图4)。结果显示，改进食物链算法比NSGA-Ⅱ能够获得更多的Pareto最优解，同时改进食物链算法产生的Pareto最优解均在NSGA-Ⅱ产生的解的左下方，得出的结果要优于NSGA-Ⅱ。

图2　两种算法优化REC03算例获得的Pareto最优解集

图3　两种算法优化REC11算例获得的Pareto最优解集

图4　两种算法优化REC21算例获得的Pareto最优解集

将改进食物链算法与NSGA-Ⅱ两种算法优化三个典型算例的求解统计结果列于表1。从表1可以看出，对于三个典型算例，改进食物链算法求得的Pareto最优解个数均多于NSGA-Ⅱ。C指标结果更进一步表明，改进食物链算法获得的Pareto最优解集A与NSGA-Ⅱ获得的Pareto最优解集B相比，在B中任意一个Pareto最优解，A中都存在优于它的解。就单次平均计算时间而言，改进食物链算法求解三个典型算例的时间均稍长于NSGA-Ⅱ。这主要是由于为了寻找更多的最优解，改进食物链算法在觅食阶段对于Pareto最优解的局部搜索花费了较多时间。综合以上结果可知，在相同的条件下，虽然改进食物链算法的优化时间略长于NSGA-Ⅱ，但是改进食物链算法对多目标置换流水车间调度问题的寻优能力明显胜过NSGA-Ⅱ，从而验证了改进食物链算法求解多目标置换流水车间调度问题的有效性。

表1　求解统计结果

4　结语

多目标的置换流水车间调度问题更加符合实际的生产情况，具有重要的研究意义。本文根据流水车间与食物链具有相似链式结构的特点，提出了一种改进的食物链算法，并用于求解多目标置换流水车间调度问题。改进食物链算法采用可变邻域觅食，保证了搜索方向的多样性及遍历性；引进快速非支配性排序和个体拥挤距离计算，提高了求解多目标问题的优化性能。应用改进食物链算法对OR-Library三个典型算例进行求解，研究结果表明，本文给出的算法取得了比NSGA-Ⅱ更加理想的Pareto最优解集，具有较好的实际应用前景。

[1]Ishibuchi H, Murata T. A Multi-objective Genetic Local Search Algorithm and Its Application to Flowshop Scheduling[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 1998, 28(3): 392-403.

[2]Ravindran D, Haq A N, Selvakumar S J, et al. Flow Shop Scheduling with Multiple Objective of Minimizing Makespan and Total Flow Time[J]. International Journal of Advanced Manufacturing Technology, 2005, 25(9/10): 1007-1012.

[3]Yagmahan B, Yenisey M M. A Multi-objective Ant Colony System Algorithm for Flow Shop Scheduling Problem[J]. Expert Systems with Applications, 2010, 37(2): 1361-1368.

[4]Lee C K M, Lin D, Ho W, et al. Design of a Genetic Algorithm for Bi-objective Flow Shop Scheduling Problems with Re-entrant Jobs[J]. International Journal of Advanced Manufacturing Technology, 2011, 56(9/12): 1105-1113.

[5]Pasupathy T, Rajendran C, Suresh R K. A Multi-objective Genetic Algorithm for Scheduling in Flow Shops to Minimize the Makespan and Total Flow Time of Jobs[J]. International Journal of Advanced Manufacturing Technology, 2006, 27(7/8): 804-815.

[6]Lemesre J, Dhaenens C, Talbi E G. An Exact Parallel Method for a Bi-objective Permutation Flowshop Problem[J]. European Journal of Operational Research, 2007, 177(3): 1641-1655.

[7]Qian B, Wang L, Huang D X, et al. An Effective Hybrid DE-based Algorithm for Multi-objective Flow Shop Scheduling with Limited Buffers[J]. Computers & Operations Research, 2009, 36(1): 209-233.

[8]Dubois-Lacoste J, López-Ibáez M, Stützle T. A Hybrid TP+PLS Algorithm for Bi-objective Flow-shop Scheduling Problems[J]. Computers & Operations Research, 2011, 38(8): 1219-1236.

[9]Arroyo J E C, de Souza Pereira A A. A GRASP Heuristic for the Multi-objective Permutation Flowshop Scheduling Problem[J]. International Journal of Advanced Manufacturing Technology, 2011, 55(5/8): 741-753.

[10]杨开兵, 刘晓冰. 带调整时间的多目标流水车间调度的优化算法[J]. 工业工程与管理, 2008, 13(5): 1-5.

Yang Kaibing, Liu Xiaobing. Optimization Algorithm for Multi-objective Flow Shop Scheduling with Setup Times[J]. Industrial Engineering and Management, 2008, 13(5): 1-5.

[11]董兴业, 黄厚宽, 陈萍. 多目标同顺序流水作业的局部搜索算法[J]. 计算机集成制造系统, 2008, 14(3): 535-542.

Dong Xingye, Huang Houkuan, Chen Ping. Local Search Algorithm for Multi-objective Permutation Flowshop Sequencing Problem[J]. Computer Integrated Manufacturing Systems, 2008, 14(3): 535-542.

[12]秦艳. 改进交叉策略的GA在流水车间多目标调度中的应用[J]. 现代制造工程, 2010(12): 29-32.

Qin Yan. Application of GA with Improved Crossover Operators in Multi-objective Flow Shop Scheduling[J]. Modern Manufacturing Engineering, 2010(12): 29-32.[13]喻海飞, 汪定伟. 食物链算法及其在供应链计划中的应用[J]. 系统仿真学报, 2005, 17(5): 1195-1198.

YuHaifei,WangDingwei.Food-chainAlgorithmandApplicationtoSupply-chainPlanning[J].JournalofSystemSimulation, 2005, 17(5): 1195-1198.

[14]喻海飞, 汪定伟. 食物链算法及其在分销网络优化中的应用[J]. 东北大学学报(自然科学版), 2006, 27(2): 146-149.

YuHaifei,WangDingwei.Food-chainAlgorithmandItsApplicationtoOptimizingDistributionNetwork[J].JournalofNortheasternUniversity(NaturalScience), 2006, 27(2): 146-149.

[15]ZitzlerE.EvolutionaryAlgorithmsforMultiobjectiveOptimization:MethodsandApplications[M].Aachen:ShakerVerlag, 1999.

[16]DebK,PratapA,AgarwalS,MeyarivanT.AFastandElitistMultiobjectiveGeneticAlgorithm：NSGA-Ⅱ[J].IEEETransactionsonEvolutionaryComputation, 2002, 6(2):182-197.

[17]BeasleyJE.OR-Library[DB/OL]. (2012-06-12)[2013-09-13].http://people.brunel.ac.uk/～mastjjb/jeb/info.html.

[18]师瑞峰, 周泓, 上官春霞. 混合递进多目标进化算法及其在flowshop排序中的应用[J]. 系统工程理论与实践, 2006, 26(8): 101-108.

ShiRuifeng,ZhouHong,ShangguanChunxia.AHybridEscalatingMulti-objectiveEvolutionaryAlgorithmwithItsApplicationtoFlowShopProblems[J].SystemsEngineering-Theory&Practice, 2006, 26(8): 101-108.

(编辑郭伟)

Improved Food Chain Algorithm for Multi-objective Permutation Flow Shop Scheduling

Chen KejiaZhou Xiaomin

Fuzhou University,Fuzhou,350108

An improved food chain algorithm was proposed for permutation flow shop scheduling with multiple objectives of minimizing makespan and total tardiness. Fast non-dominated sorting and crowded distance estimation were introduced into the food chain algorithm to improve the optimization ability based on Pareto optimal solutions. Three typical OR-Library examples were selected to conduct comparison. Numerical results show that the designed algorithm can obtain much better solutions than NSGA-Ⅱ.

permutation flow shop scheduling; multi-objective optimization; food chain algorithm; Pareto optimal solution

2013-11-08

国家自然科学基金资助项目(70901021，71201033)；教育部新世纪优秀人才支持计划资助项目(NCET-11-0903)

F406.2DOI：10.3969/j.issn.1004-132X.2015.03.011

陈可嘉，男，1978年生。福州大学经济与管理学院教授、博士。主要研究方向工业工程、系统工程。周晓敏，女，1988年生。福州大学经济与管理学院硕士研究生。