求解置换流水车间调度问题的Memetic算法

苏志雄，伊俊敏

(厦门理工学院管理学院， 福建 厦门 361024)

求解置换流水车间调度问题的Memetic算法

苏志雄，伊俊敏

(厦门理工学院管理学院， 福建 厦门 361024)

针对以最小化最大完工时间为目标的置换流水车间调度问题，建立了0-1型混合整数线性规划模型。在对模型进行Benders分解的基础上，提出了问题的求解策略，进而设计了一种Memetic调度算法，并探讨了基于组合规则的种群初始化方法和混合遗传操作。为了提高算法的搜索效率，采用了更加高效的适应度值计算方法以及两种邻域搜索方法。最后，基于Benchmark算例的仿真实验结果表明了该算法的有效性，可以找到26个算例中的17个最优解(65.38%)，且其平均相对误差的均值仅为0.88%。

生产调度；置换流水车间；Memetic算法；邻域搜索

由于此类调度问题的NP难特性[1]，精确算法只能求解很小规模的算例，而启发式算法[2-5]可以在很短的时间内获得调度解，但是其求解质量和通用性较差。因此，近期的研究重点更多地集中在元启发式算法[6-11]。遗传算法作为一种常用的元启发式算法，具有鲁棒性、通用性、隐含并行性等特点，在求解PFSP上取得了较好的效果。然而，传统的遗传算法存在进化停滞和计算时间长等问题，故本文在问题分析和已有算法研究的基础上，提出了一种将遗传算法与邻域搜索相结合的Memetic算法(memeticalgorithm,MA)，其关键在于种群初始化策略、遗传操作、邻域搜索算法的设计。最后，通过基于benchmark算例的对比实验对其有效性进行了验证。

一、 PFSP的数学模型

1.符号说明

为了叙述方便，引入下列符号：i为机器编号，i∈{1,…,m}；j为工件编号，j∈{1,…,n}；k为排列中的位置编号，k∈{1,…,n}；π为所有工件的一个排列，即工件加工顺序方案，π={π1,π2,…,πn}；pij为工件j在机器i上的加工时间；Pik为工件πk在机器i上的加工时间；xjk为1，如果工件j位于排列π中的第k个位置，否则为0；Cik为工件πk在机器i上的完工时间；Cmax为最大完工时间，即makespan。

2.模型的建立

基于上述符号说明，本文建立如下所示的0-1型混合整数线性规划模型(以下称为[P]模型)：

minCmax，

(1)

s.t.Cmax=Cmn，

(2)

Cik≥Ci,k-1+Pik,∀i,k，

(3)

Cik≥Ci-1,k+Pik,∀i,k，

(4)

(5)

(6)

(7)

xjk∈{0,1},∀j,k，

(8)

Cik≥0,∀i,k;Ci0=0，∀i;C0k=0，∀k。

(9)

上述模型中：式(1)表示目标函数为最小化最大完工时间；约束(2)表示最后一个工件在最后一个机器上的完工时间为Cmax；约束集(3)表示资源约束，即在同一机器上前一工件加工完，下一工件才能开始加工；约束集(4)表示同一工件前一道工序完成后下一道工序才能开始；约束集(5)表示pij与Pik之间的关系，Pik取决于排序变量xjk；约束集(6)表示排列中的每一位置有且仅有一个工件；约束集(7)表示每一个工件有且仅有一个位置；约束集(8)～(9)表示变量的取值范围。

二、 模型的求解思路

根据Benders分解[12]，将模型[P]的所有变量分成二元变量、连续变量两部分,固定二元变量x，令v(x)=min{(1)|(2)-(5),9}，则模型[P]可以表示为以下等价形式(以下称为[P1]模型)：

minv(x)，

s.t.(6)-(8)。

[P1]称为原问题[P]的投影问题，二元变量x称为投影变量。若给定[P1]的一个可行解，则工件加工顺序方案π被唯一确定，进而可以确定工件π(k)在机器i上的加工时间Pik；此时，可以通过求解下述线性规划模型来计算v(x)(以下称为[P2]模型)：

minCmax，

s.t.(2)-(5),(9)。

由上述模型分解可以看出：[P1]的每个可行解都对应着一个工件加工顺序方案；给定[P1]的一个可行解，通过求解子问题[P2]可以确定最优完工时间进而得到完整的调度解(原问题[P]的可行解)。此外，由于[P1]的可行解易于表示为染色体，可以通过Memetic算法在外层搜索遍历二元变量空间来优化工件加工顺序；在内层通过求解[P2]来确定满足约束条件的最优连续解，并以f=1/Cmax作为染色体的适应度函数。

三、 模型的求解方法

Memetic算法是一种模拟人类文化进化的群体智能优化算法，是基于种群的全局搜索与基于个体的启发式局部搜索的结合，它是元启发式算法研究领域中的一个热点，相应的伪代码见文献[13]。

1.染色体编码

编码是Memetic算法的首要问题，本文采用排列编码，即取所有工件编号的排列作为解的表示，比如6个待加工工件的一个加工序列{3，5，6，4，1，2}就是其相应的编码。

2.适应度值计算

在算法的迭代过程中，需要对所产生的每个染色体进行评价，即通过求解[P2]来确定相应的适应度值。因此，需要去求解大量的线性规划模型，假如采用单纯形法之类的常规方法进行求解，则算法的进化运算过程进展相对缓慢。对于给定的染色体，亦即确定了一个工件加工顺序方案，PFSP可以用一个有向栅格图G=(N,E)来表示，其关键路径的长度就是[P2]的最优目标函数值，进而通过递推公式得到的完工时间[14]是模型[P2]的一个最优解。本文采用此种方法来计算总完工时间进而确定染色体的适应度值。

3.初始种群

初始种群的好坏，会对算法的搜索路径和收敛速度产生影响。为了保证初始种群具有较高的质量和多样性，本文采用4种方法来进行初始化。首先，由CDS[2]生成m-1个染色体：将m台机器分组，产生m-1个两台机器的PFSP集合，进而利用Johnson算法获得相应的工件加工顺序方案。其余的染色体20%按照随机规则产生，20%根据GRASP(贪婪水平α=0.15)构造得到，60%通过基于NEH的GRASP[6-7](贪婪水平α=0.85)生成。

4.交叉变异算子

PFSP的遗传调度算法针对排列编码设计了许多成功的交叉算子，如顺序交叉(ordercrossover,OX)、部分匹配交叉(partialmappedcrossover,PMX)、相似块两点顺序交叉(similarblock2-pointordercrossover,SB2OX)，其中OX侧重保持工件间的相对顺序，PMX在保持绝对位置的同时也保证了一定的相对顺序，而SB2OX在OX的基础上还直接将相似块遗传给后代。

考虑到PMX[8]和SB2OX[9]在求解PFSP的成功经验，本文提出了一种混合交叉算子，它将PMX和SB2OX结合起来，对应的选择概率分别为0.40、0.60。此外，本文的变异算子也采用混合算子，它将平移(shift)算子、交换(swap)算子、逆转(inverse)算子结合起来，对应的选择概率分别为0.25、0.25、0.50。

5.邻域搜索

针对PFSP的特点，本文采用2种邻域搜索算法：相邻交换邻域搜索[4]、改进NEH邻域搜索。经典的NEH算法[3]依次插入了初始排序中的n个工件，而本文的改进NEH邻域搜索保留前一半作为当前排序，只是插入最后的[n/2]个工件。每一代种群中的个体均有机会进行邻域搜索：交叉个体以相同的概率来进行选择，而变异个体有0.20的概率进行改进NEH邻域搜索。

四、仿真实验

为了验证Memetic算法求解PFSP的性能，以OR-Libray中的26个benchmark算例作为测试数据：Carlier提出的8个算例(Car1～Car8)，后18个是由Reeves提出的Rec01～Rec35。为了评价算法的性能，本文采用文献[11]给出的下界C*，在此基础上可以求得以下指标：相对误差(relativeerror,RD)，其公式为RE=(Cmax-C*)/C*×100%；最佳相对误差(bestrelativeerror,BRE)；平均相对误差(averagerelativeerror,ARE)；最差相对误差(worstrelativeerror,WRE)。

1.实验环境

本文算法采用Matlab2014a编程实现，运行环境为Win8.1、i3-4130(3.40G)/4G的一体机。算法的参数设置如下：种群大小为80，保留2个适应度最好的子辈，交叉概率为0.70，选择操作采用随机遍历抽样算法，最大运行代数为2mn，最大运行时间为600s。如果在允许的时间范围内没有达到下界，则将算法终止时所找到的“最好解”作为最终调度解。

2.实验结果及分析

针对上述26个算例，采用本文提出的MA在相同的条件下独立运行20次，并与NEH[3]、混合遗传算法(hybridgeneticalgorithm,HGA)[10]、限优遗传算法(optimumlimitedgeneticalgorithm,OLGA)[11]进行比较，具体如表1所示。从表1中可以看出：

表1 4种算法的计算结果比较

(1)MA具有很好的求解质量，对于20×10及以下规模的算例均可以找到最优解，尤其对8个Car算例都可以100%求出最优解，而对于较大规模的算例也能够获得较好的近优解，对于这26个算例，MA、HGA、OLGA分别找到了17、16、16个最优解，对应的最优比率分别为65.38%、61.54%、61.54%;(2)MA具有较好的稳定性，对较大规模算例也能保持ARE很小，其平均ARE最小，另外，MA避免陷入局部最优点的能力较好，其平均WRE最小；(3)总体来说，MA远远优于NEH、HGA，MA与OLGA各具优势，MA的平均ARE、平均WRE略胜0.04%、0.03%，而平均BRE略低0.07%。

五、结语

本文针对置换流水车间调度问题中的最小化最大完工时间问题展开研究，主要取得了以下成果：(1)将相邻交换邻域搜索、改进NEH邻域搜索与遗传算法结合起来，提出了一种Memetic算法；(2)在算法设计中，充分利用已有的启发式信息，提出了一种基于组合规则的混合策略来提高初始种群的质量；此外，考虑到已有算子的优点，提出了一种混合交叉、变异算子；(3)基于benchmark算例的实验结果，通过与NEH、HGA、OLGA进行比较，验证了该算法在求解质量上的优越性。

但是，随着问题规模的增大，邻域搜索的计算量大大增加，进而影响到求解质量。下一步研究中，可通过问题规模来确定相应的参数，在全局搜索与局部搜索之间进行均衡。

[1]GAREYMR,JOHNSONDS,SENTHIR.Thecomplexityofflowshopandjobshopscheduling[J].MathematicsofOperationsResearch,1976,1(2):117-129.

[2]CAMPBELLHG,DUDEKRA,SMITHML.Aheuristicalgorithmforthenjob,mmachine sequencing problem[J].Management Science,1970,16(10):630-637.

[3]NAWAZM,ENSCOREE,HAMI.Aheuristicalgorithmforthem-machine,n-job flow shop sequencing problem[J].Omega,1983,11(1):91-95.

[4]DANNENBRINGDG.Anevaluationofflowshopsequencingheuristics[J].ManagementScience,1977,23(11):1 174-1 182.

[5]王正元,岑凯辉,谭跃进.求解同顺序加工调度问题的一种启发式方法[J].计算机集成制造系统,2004,10(9):1 124-1 128.

[6]刘延凤,刘三阳.改进微粒群优化求解置换流水车间调度问题[J].计算机集成制造系统,2009,15(10):1 968-1 972,1 985.

[7]顾文斌,唐敦兵,郑堃,等.基于激素调节机制改进型自适应粒子群算法在置换流水车间调度中的应用研究[J].机械工程学报,2012,48(14):177-182.

[8]CHENCL,VEMPATIVS,ALJABERN.Anapplicationofgeneticalgorithmsforflowshopproblems[J].EuropeanJournalofOperationalResearch,1995,80(2):389-396.

[9]RUIZR,MAROTOC,ALCARAZJ.Twonewrobustgeneticalgorithmsfortheflowshopschedulingproblem[J].Omega,2006,34(5):461- 476.

[10]WANGL,ZHENGDZ.Aneffectivehybridheuristicforflowshopscheduling[J].InternationalJournalofAdvancedManufacturingTechnology,2003,21(1):38- 44.

[11]李小缤,白焰,耿林霄.求解置换流水车间调度问题的改进遗传算法[J].计算机应用,2013,33(12):3 576-3 579.

[12]BENDERSJF．Partitioningproceduresforsolvingmixed-variablesprogrammingproblems[J].NumerischeMathematik,1962,4(3):238- 252.

[13]刘漫丹.文化基因算法(MemeticAlgorithm)研究进展[J].自动化技术与应用,2007,26(11):1- 4.

[14]PINEDOM.Schedulingtheory,algorithms,andsystem[M].2nded.NewJersey:PrenticeHall,2002:130-131.

(责任编辑 雨 松)

Memetic Algorithm for Permutation Flow Shop Scheduling Problems

SU Zhi-xiong,YI Jun-min

(School of Management,Xiamen University of Technology,Xiamen 361024,China)

A 0-1 mixed-integer linear programming model was established for the permutation flow shop scheduling with makespan criterion.Based on Benders’ decomposition,a problem solving strategy was proposed,and a Memetic algorithm designed.In designing the algorithm,a combinatorial population initialization method and a hybrid genetic operation were discussed.Further,a more efficient fitness value computation and two neighborhood search algorithms were adopted to improve searching efficiency.The final results of benchmark simulation verify the effectiveness of the proposed algorithm,which solves 17 of the 26 instances (65.38%) with the mean value of average relative error standing at only 0.88%.

production scheduling;permutation flow shop;Memetic algorithm;neighborhood search

2015-10-13

2015-11-13

国家自然科学基金项目(71371162)；福建省自然科学基金项目(2014J01271)；厦门理工学院高层次人才项目(YSK10009R)

苏志雄(1980-)，男，讲师，博士，研究方向为生产计划与调度、运输调度。E-mail:z.su@163.com

F273；TP278

A

1673-4432(2015)06-0025-05