求解柔性作业调度问题的协同进化粒子群算法

宋存利

大连交通大学，辽宁大连 116028

求解柔性作业调度问题的协同进化粒子群算法

宋存利

大连交通大学，辽宁大连 116028

1 引言

柔性作业车间调度问题（Flexible Job-shop Scheduling Problem，FJSP）是JSP调度问题的扩展。在JSP中一个作业包含多个工序，每道工序仅在一台加工设备上加工，而FJSP中，每个工序可有多台性能不一的加工设备，放松了对加工设备的约束，扩大了解的搜索范围，相比JSP更接近加工实际也更加复杂。对FJSP问题进行研究的文献很多，其中Bruker和Schlie[1]是最早对FJSP问题进行研究的人，他们提出了求解2工件的FJSP的多项式算法。之后很多学者都陆续对之进行了研究，如Chen等[2]、杨晓梅等[3]、张超勇等[4]、刘冬梅等[5]、李铁克等[6]这些作者提出了求解该问题的遗传算法，在这些算法中，他们有的将工件排序和设备分配作为两个变量求解，有些用一个统一的方法求解，然后对相应的遗传算子进行改进，以便优化算法性能；Brandimarte 等[7]则是用禁忌搜索算法求解该问题；Fattahi等[8]提出了四种将禁忌搜索算法与模拟退火算法相混合的策略来解决该问题；Mastrololli等[9]则将禁忌搜索算法和邻域函数混合来求解该问题；刘晓冰等[10]提出了免疫克隆选择算法求解柔性生产调度问题；Liu等[11]针对柔性调度问题提出了一种多粒子群求解多目标的算法求解该问题，该算法中，不同种群以不同的目标求解，同时各种群间通过信息的传递来求得一个满足多目标的综合优化解。Zribi等[12]提出了求解柔性调度问题的Z.K.K方法，该方法的特点是将柔性Job-shop调度问题分解为设备分配和工序排序两个子问题，首先用分枝定界和禁忌搜索算法结合一种下界评估方法来求出设备分配方案的较优解，然后根据此设备分配方案利用一种遗传算法来对工序排序寻找最优解。Ho等[13]提出了求解柔性Job-shop调度问题的文化进化遗传算法GENACE，该算法的CDR算法利用不同的优先级规则来初始化遗传算法的种群，然后利用文化遗传算法来求解。彭传勇等[14]提出了广义的粒子群算法求解作业车间调度问题，在此算法的启发下，本文提出求解柔性作业车间调度问题的粒子群算法。

总之对柔性调度问题的研究文献较多，但利用粒子群算法对此问题的求解却相对较少，在此基础上，本文在研究柔性作业车间调度问题特点的基础上，提出了解决该问题的协同进化的粒子群优化算法CPSO，该算法对设备分配码和工件编码分别采用不相同的编码方法。对设备分配码采用整数编码方法，提出了修订的粒子更新公式来对设备编码进行更新操作，以保证设备编码在运动过程的合法性。对工件序列采用基于操作的随机键编码方式编码。同时考虑到设备分配与工件排序之间的强耦合性，传统的粒子群求解模式有可能在粒子运动过程中破坏gbest的优化模式，因此将设备选择和工件调度分别作为两个寻优变量，分别利用PSO算法进行寻优，并根据两个变量的内容进行互相评价，最终获得一个将设备选择和工件调度相结合的最优的调度结果。最后实验表明该算法对FJSP问题的有效性。

2 柔性作业车间调度问题描述

柔性Job-shop调度问题可描述为：n个工件在m台设备上加工。n个工件的编号用Ji来表示（其中i=1，2，…，n），每个工件Ji包含Oi道工序，用Oij表示工件Ji的第j道工序(1≤j≤Oi)。m台设备的编号用Mk来表示（其中k=1，2，…，m），对每道工序Oij都至少有1台设备可完成它的加工。定义P为设备分配矩阵，当Pijk=1时，表示工件Ji的第j道工序在设备Mk上加工，否则Pijk=0。定义Tijk为加工时间矩阵，当设备Mk不能加工此工序时，则定义Tijk=∞，矩阵S代表工件的开工时间矩阵，其中Sij为工件Ji的第j道工序的开工时间，矩阵C代表工件的完工时间矩阵，其中Cij为工件Ji的第j道工序的完工时间。当每台设备都可加工所有工序时，则问题为全柔性车间作业调度问题（Τotal-Flexible Job-shop Scheduling Problem，Τ-FJSP），当每道工序的加工设备是m台设备的部分设备时，则此问题为部分柔性车间作业调度问题（Partial-Flexible Job-shop Scheduling Problem，P-FJSP），本文设定调度的目标是求最小化最大完工时间makespan，其表达如公式（1）所示。

公式（2）～（6）表示问题的约束条件，其中公式（2）表示一个工序的完工时间等于其开工时间加上其在某一具体加工设备上的加工时间之和，这表明工序在加工过程中设备不会故障、不被其他工序抢占，直到在该设备加工完成才可离开。公式（3）说明每道工序都必须等其前驱工序加工完成才能开始加工；公式（4）和公式（5）说明对应每个工序，只能将它分配到一台可加工设备上去。公式（6）说明必须为所有的工序分配加工设备。

3 算法描述

3.1 编码及解码算法

（2）工序排序编码

粒子群算法求解FJSP的第一个问题是用一种合适的粒子码来表示合法的调度结果。在FJSP问题中，由于每道工序的加工设备不唯一，因此相比JSP它的编码工作涉及到两方面，一个是加工设备分配问题，另一个是安排工序的加工顺序问题。由于两个工作的性质不同，因此一个FJSP的调度编码应由两部分编码组成，第一部分对应设备分配的编码，第二部分对应工序排序的编码。

（1）设备分配编码方案

首先对m台加工设备依次从1开始编号，每台设备对应唯一的编号。对工序进行编号，根据问题描述，总共有待加工工序总数为道工序的加工任务，用一个长度为S的向量来表示粒子位置，工件i将在向量中出现Oi次，第一次出现代表第i个工件的第一道工序，第二次出现代表第i个工件的第二道工序，以此类推。这样做保证了粒子更新操作将产生满足工艺约束的编码方案，不需额外的调整。

3.2 粒子更新公式定义

在PSO算法中，每个粒子被映射成问题空间的一个可行解。在D维的搜索空间中，每个粒子都具有自己D维的位置和速度。在飞行过程中，每个粒子通过自身和同伴的飞行经验不断调整自己的飞行速度，从而达到飞向好的搜索空间的目的。这里用Xi=(xi，1，xi，2，…，xi，d)表示粒子的位置，用Vi=(νi，1，νi，2，…，νi，d)表示粒子速度，用Pi= (pi，1，pi，2，…，pi，d)表示粒子自身的最佳位置，用Pg=(pg1，pg2,…，pgd)表示群体的最佳位置，用MPg=(mpg1，mpg2，…，mpgd)表示所有群体的目前最佳位置。则工序编码部分的粒子编码，采用的粒子更新公式如式（7）所示。

设备分配码这部分的粒子码用整数来编码，每个数据代表设备的编号，针对设备分配码部分设计了粒子更新公式如式（8）所示。

具体对公式（8）的解释是w代表粒子Xi的变异概率，即对于粒子Xi每维上的元素值，随机生成一个随机数ρ，若ρ〈w，则修改对应维上的设备号，让其为另一个能加工该工序的合法设备号。否则不变。参数c1和c2为交叉率，其中c1+c2≤0.7。具体的交叉操作步骤为：

步骤1首先设置集合set={1，2，…，D}，set1=set2=Φ （Φ代表空集）。

步骤2从集合set中随机选择c1×D个元素，每选择一个元素，则将它放入集合set1，并从集合set中去掉。

步骤3再次从集合set中选择c2×D个元素，每选择一个元素，则将它放入集合set2，并从集合set中去掉。

步骤4以set中的元素为下标，将粒子xi，d(t)中对应位置的元素值赋值给xi，d(t+1)的对应位置；以set1中的元素为下标，将粒子pi，d(t)中对应位置的元素值赋值给xi，d(t+1)的对应位置；以set1中的元素为下标，将粒子pgd(t)中对应位置的元素值赋值给xi，d(t+1)的对应位置，则操作结束。

3.3 协同进化模型

协同进化的一般思想是多个种群共同进化，或者是一个种群分为多个部分，各种群在各自独立进化的同时相互间共享和不断进行信息交换。各种群不仅利用从外界获得的各种信息来指导自身的搜索，同时还把搜索得到的经验与其他种群分享，从而使整个系统协同进化，直至获得最优解。本文的协同进化粒子群算法框架如图1所示，其中M代表设备分配编码，P代表工件排序码。

图1 协同进化粒子群优化算法模型

在该协同进化模型中，粒子种群有两种类型，一种是由s个M={Mj|j=1，2，…，s}粒子构成的设备分配群，用Mswarm表示，该种群中每个粒子对应一个设备分配方案，且该种群只有一个群体，用于对设备分配方案进行求解。另一种是含有s个子种群的工件排序群Pswarmj，其中j= 1，2，…，s，每个Pswarmj又包含k个粒子，每个粒子Pj，i(i=1，2，…，k)表示一个工件排序码，该类种群用于对工件排序方案进行进化。设备分配粒子Mj与工件排序种群Pswarmj一一对应，相互结合进行评价。具体的CPSO算法进化过程描述为Pswarmj中的每个粒子与Mj表示的设备分配方案相结合进行最小化最大完工时间的计算，并利用PSO算法连续进化POP1代获得一个新的种群Pswarmj。对于设备分配种群Mswarm中的每个粒子Mj的评价，则利用与其对应的工件排序种群Pswarmj中的目前存在的最优工件排序粒子对其进行评价，然后对Mswarm进化一代，从而获得新的Mswarm种群，即一组新的设备分配方案。在一次协同进化结束后，对Pswarmj种群的每个粒子再利用新的设备分配方案进行评价，以此类推，直到满足协同进化算法终止条件。本文中用最大协同进化代数POP2来确定。最后输出所有Pswarm种群中最好的工序分配方案和Mswarm中的最好设备分配方案。总之本文中的协同进化算法是同时利用设备种群和工件分配种群的同时进化来获取最优解。协同进化PSO算法的流程图如图2所示。

图2 协同进化PSO算法流程图

4 仿真实验与分析

首先对完全柔性调度问题Kacem进行测试，其中的CPSO算法参数设置如下：由于全柔性调度问题可选方案较多，所以对Mswarm种群规模设计较大s=15。对部分柔性调度问题Brandimarte问题，Mswarm种群规模设计较小一些s=10。其他方面两问题可采用一致。每个Pswarm子种群的规模采用k=20，Mswarm种群进化最大代数pop1= 30，每个Pswarm子种群进化最大代数pop2=40。对Pswarm种群，其惯性因子w=1，加速因子c1=c2=1.5，c3=1.5，每个粒子的矢量值区间为-4～4，速度的矢量值区间为-2～2。对Mswarm种群，其惯性因子w=0.05，c1=c2=0.25。所有的工件序列码采用随机生产方式，设备分配码随机生成40%，最短设备优先选择生成一个，剩余粒子采用70%的设备选择最短设备加工算法生成。

每个算例均运行10次，下面给出算法的统计结果。其中表中指标表示如公式（9）和公式（10）：

其中Cmax为各个算法取得的最优值，Cavg为各个算法运行10次取得结果的平均值。

表1中给出的是关于Kacem问题的调度统计结果，从结果看CPSO和GENACE算法取得的最优结果均相同，求出了问题的目前最优解。从ARE的统计结果可看出CPSO算法误差较小。表2给出了关于Brandimarte问题的运行结果，其中LB指问题的下界值，UB指问题的上界值。将算法CPSO的统计结果与目前比较好的算法Z.K.K[12]的运行结果和Chen[2]等的运行结果进行比较。统计结果表明CPSO算法相对于Z.K.K算法，有8个结果都要好于Z.K.K，对问题MK03和MK08的优化结果和Z.K.K相同。将CPSO算法和Chen的算法相比，5个问题的结果优于Chen的结果，3个问题的结果和Chen的结果相同，2个问题的结果稍差于Chen的结果。通过以上实验说明了协同进化算法在求解FJSP问题上具有明显的优越性。

表1 各种算法对Kacem问题的调度结果

表2 各种算法对Brandimarte问题的求解结果

5 结论

本文在研究柔性作业车间调度问题特点的基础上，提出了解决该问题的协同进化粒子群优化算法CPSO，该算法对设备分配码和工件序列码分别采用不相同的编码方法。对设备分配码采用整数编码方法，提出了修订的粒子更新公式来对设备编码进行更新操作，以保证设备编码在运动过程的合法性。对工件序列采用基于操作的随机键编码方式编码，该部分粒子的更新采用标准粒子更新公式。同时考虑到设备分配与工件排序之间的强耦合性，传统的粒子群求解模式有可能在粒子运动过程中破坏gbest的优化模式，同时将设备选择和工件调度分别作为两个寻优变量，分别利用PSO算法进行自适应寻优，并根据两个变量的内容进行互相评价，最终获得一个将设备选择和工件调度相结合的最优的调度结果。通过实验验证了算法的有效性，但不足之处是算法运行时间较长，今后需在提高算法运行效率方面继续研究。

[1]Bruker P，Schlie R.Job shop scheduling with multipurpose machines[J].Computing，1990，45：369-375.

[2]Chen H，Ihlow J，Lehmann C.A genetic algorithm for flexiblejob-shopscheduling[C]//ΤheProceedingsofthe1999 IEEE International Conference on Robotics&Automation，Detroit，1999：1120-1125.

[3]杨晓梅，曾建潮.遗传算法求解柔性job shop调度问题[J].控制与决策，2004，19（10）：1197-1200.

[4]张超勇，饶运清，李培根，等.柔性作业车间调度问题的两级遗传算法[J].机械工程学报，2007，43（4）：119-124.

[5]刘冬梅，傅卫平，来春为，等.改进遗传算法求解柔性车间调度问题[J].西北大学学报，2011，41（4）：611-616.

[6]李铁克，王伟玲，张文学.基于文化遗传算法求解柔性作业车间调度问题[J].计算机集成制造，2010，16（4）：861-866.

[7]Brandimarte P.Routing and scheduling in a flexible job shop by tabu search[J].Ann Oper Res，1993，41：157-183.

[8]Fattahi P，Mehrabad M S，Jolai F.Mathematical modeling and heuristic approaches to flexible job shop scheduling problems[J].J Intell Manuf，2007，18：331-342.

[9]Mastrololli M，Gambardella L M.Effective neighborhood functions for the flexible job shop problem[J].Journal of Scheduling，2002，3（1）：3-20.

[10]刘晓冰，吕强.免疫克隆选择算法求解柔性生产调度问题[J].控制与决策，2008，23（7）：781-785.

[11]Liu H，Abraham A，Wang Z.A multi-swarm approach to multiobjective flexible job-shop scheduling problems[J].Fundam Informaticae，2009，95：465-489.

[12]Zribi N，Kacem I，Kamel A E.Assignment and scheduling in flexible job-shops by hierarchical optimization[J].IEEE Τransactions on Systems，Man and Cybernetics Part C：Applications and Reviews，2007，37（4）：652-661.

[13]Ho N B，Τay J C，Lai E M K.An effective architecture for learning and evolving flexible job shop schedules[J].European Journal of Operational Research，2007，179（2）：316-333.

[14]彭传勇，高亮，邵新宇，等.求解作业车间调度问题的广义粒子群优化算法[J].计算机集成制造系统，2006，12（6）：911-917.

[15]Kacem I，Hammadi S，Borne P.Pareto-optimality approach for flexible Job-Shop scheduling problems hybridization of evolutionary algorithms and fuzzy logic[J].Mathematics and Computers in Simulation，2002，60（3/4/5）：245-276.

SONG Cunli

Dalian Jiaotong University,Dalian,Liaoning 116028,China

Τhe flexible job shop scheduling problem is a typical NP-hard problem.Τhis problem involves two problems,such as equipment allocation and job assignment,and these two problems have strong couplings.Τo solve this problem a co-evolution Particle Swarm Optimization algorithm is proposed.Τhe algorithm solves the equipment allocation and job assignment as two optimization variables,optimized respectively and evaluated mutually according to the contents of them.Τhe experiments show the algorithm has obvious advantage on FJSP problem.

Particle Swarm Optimization（PSO）algorithm;flexible job shop scheduling problem;makespan;neighborhood search

柔性作业车间调度问题是典型的NP难题。柔性作业车间调度问题涉及到设备分配和作业分配两个问题，并且两问题之间具有较强的耦合性，提出了基于协同进化的粒子群算法。该算法将设备选择和工件调度分别作为两个寻优变量，利用PSO算法分别进行寻优，根据两个变量的内容进行互相评价。实验表明该算法对FJSP问题的有效性。

粒子群算法；柔性车间作业调度问题；最小化完工时间；邻域搜索

A

ΤP301

10.3778/j.issn.1002-8331.1305-0128

SONG Cunli.Co-evolution Particle Swarm Optimization algorithm for flexible job-shop scheduling problem.Computer Engineering and Applications,2013,49（21）：15-18.

辽宁省教育厅计划项目（No.L2010086）。

宋存利（1975—），女，博士，副教授，主要从事生产调度、智能算法等研究。E-mail：scunli@163.com

2013-05-13

2013-06-21

1002-8331（2013）21-0015-04

CNKI出版日期：2013-07-03http://www.cnki.net/kcms/detail/11.2127.ΤP.20130703.1142.003.html