面向柔性作业车间调度问题的改进博弈粒子群算法

顾幸生，丁豪杰

（华东理工大学信息科学与工程学院，上海200237）

调度是一个决策过程，是在规定的时间内进行有限资源的合理化配置，其目的是优化一个或多个目标［1］。而生产调度则是企业针对生产过程，进行有效、合理地规划，以便正常组织和开展产品的生产、加工或制造。生产调度问题是企业资源规划（enterprise resource planning，ERP）之后，制造执行系统（manufacturing executive system，MES）高效、顺利地完成产品制造的核心和关键［2］。根据系统的复杂性划分，柔性作业车间调度问题（flexible jobshop scheduling problem，FJSP）是最具代表性的一类调度问题。它将“在一组设备上加工完成一件产品”定义为一个作业（Job），其中参与加工的每台设备被定义为机器（Machine）；而一个作业根据加工工艺等限制，常被分成几个连续且相关的加工环节（单元）依次进行加工，这些加工环节被定义为工序（Operation）；工序是生产制造过程中最小的调度单元，每个工序每次只能被一台机器加工处理［3］。由于并行机等柔性设备的引入，柔性作业车间调度问题的求解需要同时对工序排序和机器选择两个子调度问题进行求解。

随着研究的深入，大量元启发式算法被用于对FJSP进行求解［4］。在对元启发式算法的改进和FJSP求解的研究过程中，Mesghouni等率先使用遗传算法对FJSP进行了求解［5］；Ong等进一步使用克隆和选择规则模拟人类免疫系统对FJSP进行求解［6］；Zribi等将遗传算法和局部搜索算法相混合对FJSP进行求解［7］；Tay和Ho混合遗传规划算法与调度分发规则求解FJSP［8］；Liouane等通过混合蚁群算法和禁忌搜索算法对FJSP进行求解［9］。21世纪以来，粒子群算法因其简捷、易于实现且便于与其他算法融合的特点而被国内外学者大量地尝试用于求解FJSP，并取得了丰富的成果。Girish等人较早发布了结合调度规则的粒子群算法对FJSP进行求解［10］；近年，Nouiri等使用分布式的粒子群算法针对嵌入式实时生产系统中的柔性作业车间问题进行了求解，均取得了较好的实用效果［11］。

对生产调度问题的研究涉及多个调度指标，其中因最大完工时间指标可以有效表达为其他常规调度指标的函数而最常被作为FJSP的目标进行研究。本文同样以该调度指标作为研究FJSP的唯一目标，采用一种字符数串编码方式对FJSP进行编码，同时采用一种基于有效空闲时段插入工序生成活动调度方案的解码方法［12］对FJSP问题进行解码；在对存在矛盾的多个调度指标间研究后［13］，根据自定义的博弈规则，利用了这些指标进行博弈，建立博弈解集对传统的粒子群算法进行改进，并结合对关键工序备机进行调整的调度策略提出了一种博弈粒子群算法。之后，在对一系列调度标准问题算例进行测试并与其他改进粒子群算法的对应结果进行了对比分析，表明了该博弈粒子群算法的良好求解性能。

1 问题建模

1.1 符号定义

为方便对FJSP的数学模型进行描述，本文定义了如表1所示的参数符号体系。

1.2 数学模型

优化目标：

约束条件：

FJSP的数学模型中，作业内部的工序加工次序为满足特定的约束条件而进行了预先的排定，因此加工时必须给予保障；但是由于每个作业间的相互对等和独立，不同作业的工序之间优先级相等，其加工次序不受约束，只要相应的加工机器空闲，即可进行加工，但是已经开始进行加工的工序中途不能被取消，也不能被其他作业的工序抢占。同时，FJSP还遵循以下的假定，所有参数均为非负整数；所有作业（第1道工序）在开始时刻（0时刻）均可被加工；每个作业由一个或多个排定的连续工序组成，每个工序至少有一台机器可以对其进行加工，且加工过程不能间断执行；一旦一个工序被加工完成，包含该工序的作业即被立刻转入到其下一个工序所分派的机器等待加工，直到该作业结束，而中间的存储环节被假定为无穷大，可以存储所有待加工的作业。

表1 FJSP相关参数符号定义Tab.1 Denotation of parameter character related with FJSP

从机器加工工序的角度（解码问题的角度）看FJSP的约束式，易知每台机器在对所分配到的工序进行加工时，只需保证同属一个作业的工序是按其内部预排的次序进行加工即可。此外，本文对机器故障等其他不确定因素未予考虑；但即使如此，由上述介绍可知，从组合优化角度看，FJSP模型的解（调度方案）随着作业在不同机器上的排布加工可以有多种不同的方案，是NP-hard问题较难求解的一类。如对于一个简单的10个作业分配给10台机器加工的问题，其可能的调度方案就有（10！）10个，而这种组合数可以随着作业数和机器数的增加呈指数爆炸形式的增加，基于文献［1］附录部分此类问题模型性能的分析，要在规定时限内从这些数目众多的方案中寻找出最优调度方案是一件无法完成的任务，只能求取其近似最优解。

2 问题的编码和解码

2.1 问题的编码

博弈粒子群算法在处理FJSP时，使用了一种新的字符数串编码方案，该编码方案采用整数字符数串进行编码，具体的实现过程通过表2所呈现的FJSP例子进行详细地说明。

表2 简单的FJSP例子Tab.2 Instance of FJSP

表2中第1列序号为所有工序的顺序编号，为方便与计算机内部计数转换，序号编号从“0”开始；第2列是给定的作业编号；第3列是按每个作业的内部约束对其所含工序的依次编号；最后3列分别列出了能够加工该工序的机器和对应的加工时间，其中，“-”表示该工序不能被对应的机器进行加工。

表3示例了如何将表2所呈现的FJSP例子编码为相应的字符数串，形成FJSP问题基础信息编码表。

表3 FJSP问题基础信息编码表Tab.3 Basic information encoding table for the intance of FJSP

表3中的每个字段的编码位宽，即采用多少字符对该字段信息进行描述应视具体问题的规模而定。针对本例，“索引”、“作业码”和“工序码”字段均选择了用2位字符表述该字段的信息；而“备选机器及加工时间编码”字段则选择了5位字符宽度，其中前2位表示机器号，后3位表示加工相应工序的处理时间，对于无法加工的情况则以全‘0’补位。

为配合算法程序使用此编码方案进行求解，编码方案设置了一个数组项数与工序数目相同的字符串数组，以对每种不断变化更新的调度情形进行存储。每次迭代时，一组更新了的工序排序次序码被按照当前工序的顺序，重新赋给每个待加工的工序；同时，根据每个工序所分派的备选机器号，对应的作业、工序和机器信息码被赋给相应的工序，最终形成一个新的调度解，即一个新的可行调度方案。表4所示的是第1步迭代时，针对已经分配好加工机器的原始工序排序，利用一组经算法更新后的次序码，生成一种新的可行调度方案的信息数据，表中第一列是问题当前工序的顺序（与当前数组索引号一致），第二列是一组更新后的工序排序次序码（与更新后数组索引号一致），最后一列则是为每个工序分配好机器后的作业、工序和机器信息码（机器号和相应加工时间编码的拼接）。算法迭代时，字符串数组根据次序码对当前工序排序进行调整，并存储其相应的作业、工序和机器信息码到更新后的各数组单元，即使用次序码作为更新后数组的索引，将对应的作业、工序和机器信息码存入相应的数组单元。上述具体的实现过程如图1所示，对于每个作业、工序和机器信息码而言，第1～2位表示作业号，第3～4位表示该作业下的工序号，第5～6位表示选中处理该工序的加工机器号，而最后3位表示使用该机器加工该工序的处理时间。

表4 一种待更新编码情况下的信息数据Tab.4 Information data waiting to be updated

图1 算法迭代中字符数串编码更新过程Fig.1 Updatingprocessofthecharacter-number string encoding in iteration

2.2 问题的解码

算法求解过程中，需要不断地对新生成的解进行适应度值的评估，因此需要将其解码成为一个可行的调度方案。根据文献［1］中的介绍，调度可以分为无延迟调度、活动调度和半活动调度，且最优的调度解一定位于活动调度当中。因此，本文使用文献［12］所介绍的一种常用的解码思路，针对所设计的编码，将生成的新码（新的调度解），根据依次得到的作业、工序和机器信息码所包含的每个工序的调度信息，将对应的工序插入到被指派机器上的空闲时段内，最终解码成为一个活动调度方案进行相关调度指标的考察。

具体解码时，考察每个工序所分派的机器上已安排的待加工工序情况：如果其上待加工工序间存在符合约束条件的、足够的空闲时段，则将工序尽可能早的安排到此空闲时段内等待加工；否则，就在满足约束条件的情况下，将工序尽量早地安排在该机器上待加工工序队列的队尾。

3 改进的博弈粒子群算法

3.1 传统粒子群算法

传统的粒子群算法（particle swarm optimization algorithm，PSO）由Kennedy在考察鸟群协同觅食等行为之后，于1995年提出，算法最终总结了如下的速度、位移迭代公式［14］。

式中：w、c1和c2分别表示惯性系数、个体认知系数和社会认知系数，w是维持迭代进行的基本参数；vcur和xcur表示当前的速度值和位移值；vnext和xnext表示下一步的速度值和位移值；p*表示个体经历过的最好位置；g*表示当前代中所有个体所经历过的最好位置中最优的一个位置，即，全局最优位置；r1和r2为一组(0，1)内的随机数，用以维系元启发式算法的随机性。其中，每个工序分量的xnext值被用作所有工序排定次序时的比较依据。

3.2 博弈粒子群算法

当要使最大完工时间（Cmax）指标最小时，需要令每台加工机器的负载（Lk）尽可能的饱满和平衡，因每台机器对各工序的加工性能（处理时间）不同，这种安排不可能将每个工序都安排在使其加工时间最小的机器之上，根据总机器负载（Ltotal）的定义，这将令该指标值增加；同理，要使总机器负载指标值最小，则需要将各个工序都尽量安排在使其加工时间最小的机器之上，这种安排常常会造成工序被集中分派给某些加工性能强的机器，即对大多数工序有较短的加工处理时间的机器（如表2中的机器2），造成这些机器的负载增加，从而令整个调度方案的最大完工时间增加；而要使最大负载机器负载（Lmax）指标减小，必然要以增加其他加工机器上的负载为代价，即将当前最大负载机器上的某些工序重新合理地分派给其它的加工机器处理，通常情况下，最大负载机器多是加工性能较强的机器，向其它机器分派这些工序同样会造成其被处理的时间增加，从而引起总机器负载指标值的增加。

因此，当同时考虑优化最大完工时间、总机器负载和个体最大机器负载三个指标时，必然会产生需要调和的矛盾，本文充分利用这些矛盾，为每个粒子构建了个体博弈解集，同时为整个群构建了一个群体博弈解集，然后分别随机使用个体博弈解集和群体博弈解集中的一个解代替传统粒子群公式（1）、（2）中的p*和g*参与迭代运算。在每个粒子完成各分量的迭代计算之后，针对产生的新解再与原有个体博弈解集中的解进行逐个地博弈，根据博弈的结果，更新和维护每个粒子的个体博弈解集；同时根据进一步博弈的结果维护群体博弈解集。此时，传统的粒子群公式变为

式中：prep表示随机地从粒子的个体博弈解集中选出的一个博弈解；而grep表示随机地从群体博弈解集中选出的一个博弈解。

博弈即一些个人、对、组或者其他组织，面对一堆的环境条件，在一定的规则下，同时或先后，一次或多次，从各自允许选择的行为或策略中进行选择并加以实施，从而获得各自结果的过程［13］。经过对上述算法改进策略的分析，易知本算法能够成功的关键是利用博弈规则生成有效的个体博弈解集和群体博弈解集，因此博弈规则的设计和订立直接影响着本算法的最终求解效能。

3.3 博弈规则

本文制定的博弈规则如下：

（1）博弈成功规则：依次取出个体博弈解集中的一个解与当前的新解进行博弈，当新解对应的调度方案中至少有1个指标优于正与之博弈的个体博弈解集中的某个解的对应指标，且另2个指标均不劣于正与之博弈的解的对应指标，则用当前的新解替换正与之博弈的个体博弈解集中的解；同时触发下一级的博弈，即使用当前的新解继续与群体博弈解集中的所有解进行逐个博弈，同样，当新解对应的调度方案中至少有1个指标优于当前正与之博弈的群体博弈解集中的某个解的对应指标，且另2个指标均不劣于当前与之博弈的解的对应指标，则用新解继续替换群体博弈解集中正与之博弈的解。

（2）博弈相持规则：不论在哪一级博弈中，当新解中至少1个指标优于当前正与之博弈的解的对应指标，而又未达替换正与之博弈的解的条件时，将当前的新解加入到正与之博弈的解所在的解集中。即，当前新解若处于与个体博弈解集中的所有解进行逐个博弈的阶段，则仅增添至个体博弈解集中；若处于与群体博弈解集中的所有解进行逐个博弈的阶段，则仅增添入群体博弈解集中，而此时，个体博弈解集中的某个解应已被当前新解所替代。

（3）博弈失败规则：不论在哪一级的博弈中，当新解中所有的指标均不优于正与之博弈的解的所有对应指标，则放弃该新解，停止博弈，各博弈解集维持不变。

特别需要说明的是，算法开始运行时，当每个粒子被用随机位置完成初始化后，此粒子所对应的解即为每个粒子个体博弈解集中的初始解，并直接与群体博弈解集中所有的解进行逐个博弈，以维护群体博弈解集；而群体博弈解集中的初始解，则默认为第一个被随机位置初始化的粒子所对应的解。

3.4 算法流程

新的改进算法在本文中被命名为博弈粒子群算法（Gaming PSO）。为方便算法流程的阐述，假设粒子编号为pno，种群规模数为N，迭代计数为r，算法的总迭代次数为R，算法流程如图2所示。

图2 博弈粒子群算法流程Fig.2 Flow of gaming PSO algorithm

4 关键工序确定及对其加工机器的再分派

图2所示的算法流程中表明，针对FJSP中的工序排序子问题，主要由改进的粒子群算法迭代公式（3）和式（4）来完成；而针对机器选择子问题，博弈粒子群算法则引入了重新安排关键工序机器的方法来实现，其中关键工序的确定可以根据其定义来实现。

4.1 关键工序的定义

关键工序是确定关键路径的核心要素，关键路径法由Kelly和Walker共同研究提出。该方法为有效解决资源分配与平衡等问题提供了指导思路，在众多学科领域发挥了重要作用。具体在求解FJSP过程中，考察每一个可行的调度方案（调度解），那些不能提前也不能推迟的工序被称为关键工序，而由关键工序组成的每一条完工路径都是关键路径。

4.2 关键工序的确定

依据关键路径法中关键工序的定义，关键工序的确定就是考察当前正向安排的调度解中的所有工序，以正向调度安排的最大完工时间作为基准进行逆向调度安排，即将正向调度安排中的每个工序尽可能的延后加工。对比两种调度安排，找出那些在两种调度安排下，即不能提前也不能推迟的工序，从而确定出当前的关键工序。由关键工序确定的过程，可以看出关键工序是随调度解的不同而动态变化的。图3展示了某种调度情况下如何确定关键工序的过程示意。

图3 确定关键工序Fig.3 Illustration of finding out critical operations

由图3可知，作业1的2个工序在进行逆向安排后，较之前的正向安排均出现了推迟，故是非关键工序；而作业2的3个工序无论如何安排其开始时间和结束时间都没有变化，因此是关键工序。

4.3 针对关键工序的机器再分派

关键工序一旦确定完成后，则按照数组的次序，找到第1个关键工序，然后在其备选加工机器集中随机的选出一台机器重新分派给该关键工序，对于新生成的解进行重新解码，并在评估得到的调度方案中的各个指标值后与博弈解集中的解进行逐个地博弈。当完成第1个关键工序的机器再分派尝试后，继续对第2个、第3个直至最后一个关键工序进行相同地备机再分派尝试，并且在此过程中将得到的新解不断地与博弈解集中的解进行博弈，以维护和更新各博弈解集。

5 标准算例测试与比对分析

Brandimarte等设计了一组FJSP算例［15］，包含10个代表性的FJSP问题，分别命名为Mk01～Mk10，成为目前研究FJSP问题的标准问题算例之一。本文用博弈粒子群算法，以最小化最大完工时间为优化目标，对Brandimarte算例进行了20次独立测试，将多次测试所求得最大完工时间的最小值、最大值和平均值列于表5中；同时，为了体现博弈规则的作用，表5中还列出了不使用博弈规则，即仅使用传统的粒子群算法（Tradition PSO）配合对关键工序的机器再分派规则对Brandimarte算例进行20次独立测试的结果情况。为便于与其他一些改进粒子群算法的相应结果进行了对比，表5列出了3种代表性的改进粒子群算法求解Brandimarte算例所得的最优结果。

粒子群算法参数的选择主要根据Clerc的研究结果选定［16］，w=0.689 343，c1=c2=1.42 694。同时，为体现算法的高效和快捷性，测试各算例时的粒子群规模（N）依据具体问题规模而单独设定，列于表格的最后一列；测试中，算法的总迭代次数均设为R=100。

表5中的第一跨列（1～3列）介绍了Brandimarte算例的基本特征信息，包括算例名称、规模和包含的工序总数；第二列给出了Girish等人于2009年发布于“文献［10］”的结合了调度规则的粒子群算法测试该组算例所得到的最小最大完工时间值；第三列列出了Nouiri等人于2018年发布于“文献［11］”的使用多智能体技术进行协同的改进粒子群算法对该组算例测试的相应结果值；第四列列出了本文作者于近期发布于“文献［17］”的基于解码再搜索的改进粒子群算法测试该组算例所得到的结果值；第五跨列（7-9列）给出了结合对关键工序备机再分派调度策略而改进的传统粒子群算法对各Brandimarte算例进行20次独立测试所得的最大完工时间值情况，包括多次测试得到的最小值、最大值和平均值；第六跨列（10-12列）给出了使用博弈粒子群算法对各Brandimarte算例进行20次独立测试的结果情况，包括多次测试得到的最小值、最大值和平均值；跨列的最后一列（第12列）给出了测试每个具体Brandimarte算例时，传统粒子群算法和博弈粒子群算法所采用的粒子群规模，同时用“*”上标表明所有对比算法中的最优解。

表5 各对比算法针对Brandimarte算例测试所得的最小最大完工时间值的情况Tab.5 Comparison of results on Brandimarte benchmarks with different algorithms

表5中所选的对比算法均是传统粒子算法与其他某种算法进行融合改进后的粒子群算法，而本文的博弈粒子群算法在设计上仅是对传统粒子群算法架构的微调，但考察其对Brandimarte算例的测试结果中的最优解（最小值），其中有9个最优解不弱于文献［10］中的最优解，而同样有9个结果不弱于文献［17］中的最优解，有6个结果值不弱于文献［11］中的最优解，表明算法具有较好的求解性能。同时为了进一步考察算法的执行效率，表6列出了在N=100时，文献［17］的算法和博弈粒子群算法执行单次迭代的耗时对比。文献［17］已经对其提出的算法收敛度、复杂度及求解性能等进行了详细说明，通过对比表6所列的两种算法单次迭代耗时数据，博弈粒子群算法的求解性能较文献［17］中的算法性能提升了近3～5倍，结合表5数据知博弈粒子群算法的耗时更少但最优解的精度更高，故其算法性能更优。

此外，通过对比表5中传统粒子群算法的结果和博弈粒子群算法的结果可知，传统粒子群算法的稳定性较差（最大值与最小值的差），且求得最小的最大完工时间值逊于其它算法的结果值。而当使用博弈规则对算法改进之后，博弈粒子群算法中的各粒子进行搜索时，在与由这些指标博弈所形成的解集中的解进行信息交流后，间接增加了粒子搜索路径的曲折性，同时这些指标间的矛盾又可以帮助粒子在搜索中获得跳出局优的“张力”，以维持粒子的继续探索。由于粒子不易陷入到局部极值中，其每一次搜索都是一次对解空间有效地探索，这使得算法的搜索更具效率。因此就结果数据看，博弈粒子群算法不仅在求解精度上得到了提高，在搜索的稳定性上也得到了极大的改进。

表6 两种改进粒子群算法的单次迭代耗时对比（N=100）Tab.6 Comparison of duration of iteration with the algorithm from culture[17]and Gaming PSO(N=100)

6 结论

本文提出的博弈粒子群算法充分利用了问题各性能指标之间的矛盾，通过形成博弈解集对传统的粒子群算法的信息交流机制进行改良，最终在对研究的单目标调度问题求解过程中取得了更显著的效果。由于问题各性能指标的满足都需要在规定时间内分配到所需的有限资源（矛盾点），因此对矛盾博弈的过程间接为所设定的目标寻优提供了有效的探索方向和驱离局部极值点的动力。博弈粒子群算法利用了这种隐性特性，结合对关键工序备机再分派规则对问题求解，不仅提升了算法的求解速度，也增加了算法的求解精度，而通过用其测试结果与其他算法相应结果进行对比，进一步表明博弈粒子群算法对单目标FJSP问题求解具有良好的求解性能。

作者贡献声明：

顾幸生：算法的前期规划和实现过程中的修正以及论文的统稿工作。

丁豪杰：算法的设计与编程实现，算例测试和结果比较及论文的撰写和修正工作。