第48卷第12期2020年12月
同济大学学报（自然科学版）
JOURNAL OF TONGJI UNIVERSITY（NATURAL SCIENCE）
Vol.48No.12
Dec.2020
论
文
拓
展
介
绍
面向柔性作业车间调度问题的改进博弈粒子群算法
顾幸生，丁豪杰
（华东理工大学信息科学与工程学院，上海200237）
摘要：对柔性作业车间调度问题的研究可以令实际生产加工过程更加贴合当今人们对商品个性化和定制化方面的需求。在对柔性作业车间调度问题中的多个性能评价指标进行研究后，巧妙利用它们间的矛盾点，在自创的问题编、解码方案的基础之上，建立了博弈解集，并对传统粒子群算法的寻优机制进行改进，提出了改进博弈粒子群算法。运用该算法对一组标准问题调度算例进行求解，验证了该算法良好的求解性能。同时，通过与其他粒子群算法结果和耗时等的比对显示该算法可以更有效地求解以最小化最大完工时间作为唯一优化目标的柔性作业车间调度问题。
关键词：柔性作业车间调度问题；粒子群算法；关键工序；
最优化；智能决策
中图分类号：TP273+.1文献标志码：A An Improved Gaming Particle Swarm Optimization Algorithm for Flexible Job-shop Scheduling Problems
GU Xingsheng，DING Haojie
（East China University of Science and Technology，School of Information Science and Engineering，Shanghai200237，China）
Abstract：The rearch on flexible job-shop scheduling problems（FJSP）can help the production in practical to meet the ascending demands of personalization and customization from special customers.On the basis of a full study of scheduling criteria on FJSP，the paper propos a gaming particle swarm optimization algorithm gaming PSO）with novel encoding and decoding schemes. In comparison with the traditional PSO，the communication mechanism of the propod PSO is improved by a gaming solution t，which takes advantages of the contradictions among the scheduling criteria.Finally，bad on a test of the standard
benchmarks and a comparative study of the test results with tho by other improved PSOs，the propod gaming PSO proves to be effective in minimizing the maximum completion time of FJSP.
Key words：flexible job-shop scheduling problem （FJSP）；particle swarm optimization algorithm；critical operations；optimization；intelligence decision
调度是一个决策过程，是在规定的时间内进行有限资源的合理化配置，其目的是优化一个或多个目标［1］。而生产调度则是企业针对生产过程，进行有效、合理地规划，以便正常组织和开展产品的生
产、加工或制造。生产调度问题是企业资源规划（enterpri resource planning，ERP）之后，制造执行系统（manufacturing executive system，MES）高效、顺利地完成产品制造的核心和关键［2］。根据系统的复杂性划分，柔性作业车间调度问题（flexible job-shop scheduling problem，FJSP）是最具代表性的一类调度问题。它将“在一组设备上加工完成一件产品”定义为一个作业（Job），其中参与加工的每台设备被定义为机器（Machine）；而一个作业根据加工工艺等限制，常被分成几个连续且相关的加工环节（单元）依次进行加工，这些加工环节被定义为工序（Operation）；工序是生产制造过程中最小的调度单元，每个工序每次只能被一台机器加工处理［3］。由于并行机等柔性设备的引入，柔性作业车间调度问题的求解需要同时对工序排序和机器选择两个子调度问题进行求解。
随着研究的深入，大量元启发式算法被用于对FJSP进行求解［4］。在对元启发式算法的改进和FJSP求解的研究过程中，Mesghouni等率先使用遗
文章编号：0253‐374X（2020）12-1782-08DOI
DOI：10.11908/j.issn.0253-374x.20101收稿日期：2020-04-02
美国大选的公布时间基金项目：国家自然科学基金（61973120，61573144，61773165，61673175）
第一作者：顾幸生（1960—），男，教授，博士生导师，工学博士，主要研究方向为控制理论与应用，生产计划与生产调度，复杂工业过程的建模控制与优化。E-mail：xsgu@ecust.edu
通信作者：丁豪杰（1978—），男，工程师，博士生，主要研究方向为生产计划与调度过程的控制与优化。
E-mail：hero_ding1978@163.
com
第12期顾幸生，等：面向柔性作业车间调度问题的改进博弈粒子群算法
传算法对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
数学模型优化目标：min C max =max 1≤j ≤n
{C j }约束条件：
S i ，j +p i ，j ，k ≤E i ，j
E i ，j ≤S i ，(j +1)
j +1≤n j
E i ，n i
≤C max
怨恨的意思(S i ，j +p i ，j ，k )y i ，j ，e ，f ≤S e ，f
i ≠e or j ≠f ∑k ∈M i ，j
x
i ，j ，k
=1
FJSP 的数学模型中，作业内部的工序加工次序
为满足特定的约束条件而进行了预先的排定，因此加工时必须给予保障；但是由于每个作业间的相互对等和独立，不同作业的工序之间优先级相等，其加工次序不受约束，只要相应的加工机器空闲，即可进行加工，但是已经开始进行加工的工序中途不能被取消，也不能被其他作业的工序抢占。同时，FJSP 还遵循以下的假定，所有参数均为非负整数；所有作业（第1道工序）在开始时刻（0时刻）均可被加工；每个作业由一个或多个排定的连续工序组成，每个工序至少有一台机器可以对其进行加工，且加工过程
表1
FJSP 相关参数符号定义
Tab.1
Denotation of parameter character related
with FJSP
参数符号
n m J i J i O i n i
O i ，j j M k M k M i ，j S i ，j E i ，j C j p i ，j ，k e f
x i ，j ，k
y i ，j ，e ，f
C max L k L max L total O sum
符号定义
作业总数机器总数作业全集
针对作业的索引，
i =1，2，…，n 作业全集J 中的第i 个作业第i 个作业的工序集
第i 个作业的工序集的元素个数第i 个作业的工序集的第j 个工序作业J i 包含的工序索引，
j =1，2，…，n i 机器全集针对机器的索引，
k =1，2，…，m 机器全集M 中的第k 个机器工序O i ，j 的备选机器集工序O i ，j 的加工开始时间工序O i ，j 的加工结束时间作业j 的完工时间，C j =E j ，n j
工序O i ，j 在机器M k 上的加工时间
foreign是什么意思针对作业的索引号，
e =1，2，…，n 且e ≠i 作业J e 包含的工序索引号，
f =1，2，…，n e x i ，j ，k =
{
1，工序O i ，j 在机器M k 上加工
0，其他
y i ，j ，e ，f =
{
1，同一机器上O i ，j 在O e ，f 之前被加工
0，
其他
最大完工时间，
C max =max 1≤j ≤n
{C j }第k 台机器的负载，L k =
∑i =1
n
∑j =1n i
p i ，j ，k x i ，j ，k
最大个体机器负载，
L max =max {L 1，L 2，…，L m }总机器负载，L total =∑k =1m ∑i =1nevaluate是什么意思
∑j =1n i
p i ，
j ，k x i ，j ，k 工序总数，O sum =
∑i =1
n
n i
1783
同济大学学报（自然科学版）第48卷
不能间断执行；一旦一个工序被加工完成，包含该工序的作业即被立刻转入到其下一个工序所分派的机器等待加工，直到该作业结束，而中间的存储环节被假定为无穷大，可以存储所有待加工的作业。
从机器加工工序的角度（解码问题的角度）看FJSP的约束式，易知每台机器在对所分配到的工序进行加工时，只需保证同属一个作业的工序是按其内部预排的次序进行加工即可。此外，本文对机器故障等其他不确定因素未予考虑；但即使如此，由上述介绍可知，从组合优化角度看，FJSP模型的解（调
度方案）随着作业在不同机器上的排布加工可以有多种不同的方案，是NP-hard问题较难求解的一类。如对于一个简单的10个作业分配给10台机器加工的问题，其可能的调度方案就有（10！）10个，而这种组合数可以随着作业数和机器数的增加呈指数爆炸形式的增加，基于文献［1］附录部分此类问题模型性能的分析，要在规定时限内从这些数目众多的方案中寻找出最优调度方案是一件无法完成的任务，只能求取其近似最优解。
2问题的编码和解码
2.1问题的编码
博弈粒子群算法在处理FJSP时，使用了一种新的字符数串编码方案，该编码方案采用整数字符数串进行编码，具体的实现过程通过表2所呈现的FJSP例子进行详细地说明。
表2中第1列序号为所有工序的顺序编号，为方便与计算机内部计数转换，序号编号从“0”开始；第2列是给定的作业编号；第3列是按每个作业的内部约束对其所含工序的依次编号；最后3列分别列出了能够加工该工序的机器和对应的加工时间，其中，“-”表示该工序不能被对应的机器进行加工。
表3示例了如何将表2所呈现的FJSP例子编码为相应的字符数串，形成FJSP问题基础信息编码表。
表3中的每个字段的编码位宽，即采用多少字符对该字段信息进行描述应视具体问题的规模而定。针
对本例，“索引”、“作业码”和“工序码”字段均选择了用2位字符表述该字段的信息；而“备选机器及加工时间编码”字段则选择了5位字符宽度，其中前2位表示机器号，后3位表示加工相应工序的处理时间，对于无法加工的情况则以全‘0’补位。
为配合算法程序使用此编码方案进行求解，编码方案设置了一个数组项数与工序数目相同的字符串数组，以对每种不断变化更新的调度情形进行存储。每次迭代时，一组更新了的工序排序次序码被按照当前工序的顺序，重新赋给每个待加工的工序；同时，根据每个工序所分派的备选机器号，对应的作业、工序和机器信息码被赋给相应的工序，最终形成一个新的调度解，即一个新的可行调度方案。表4所示的是第1步迭代时，针对已经分配好加工机器的原始工序排序，利用一组经算法更新后的次序码，生成一种新的可行调度方案的信息数据，表中第一列是问题当前工序的顺序（与当前数组索引号一致），第二列是一组更新后的工序排序次序码（与更新后数组索引号一致），最后一列则是为每个工序分配好机器后的作业、工序和机器信息码（机器号和相应加工时间编码的拼接）。算法迭代时，字符串数组
表2简单的FJSP例子Tab.2Instance of FJSP
序号0 1 2 3 4 5
作业
作业1
作业2
工序
工序1
工序2
工序1
工序2
工序3
avb工序4
备选机器及加工时间
机器1
3
-
3
1
3
-
机器2
-
1
4
3
2
1
机器3
2
3
2
5
-
3
表3FJSP问题基础信息编码表
Tab.3Basic information encoding table for the
landing guy的寓意
intance of FJSP
索引
00
01
02
03
04
05
作业码
01
01
02
02
02
02
工序码
01
02
01
02
03
04
备选机器及加工时间编码
机器1
01003
01000
01003
01001
01003
01000
机器2
02000
02001
02004
02003
02002
02001
机器3
03002
03003
03002
03005
03000
03003
表4一种待更新编码情况下的信息数据
Tab.4Information data waiting to be updated
当前序号
（数组索引）
00
01
02
03
04
05
次序码（新索引）
（工序的新位次）
01
04
00
03
02
05
作业、工序和
机器信息码
010101003
010203003
020102004
020203005
020301003
020403003
1784
第12期顾幸生，等：面向柔性作业车间调度问题的改进博弈粒子群算法
根据次序码对当前工序排序进行调整，并存储其相应的作业、工序和机器信息码到更新后的各数组单元，即使用次序码作为更新后数组的索引，将对应的作业、工序和机器信息码存入相应的数组单元。上述具体的实现过程如图1所示，对于每个作业、工序和机器信息码而言，第1~2位表示作业号，第3~4位表示该作业下的工序号，第5~6位表示选中处理该工序的加工机器号，而最后3位表示使用该机器加工该工序的处理时间。
2.2问题的解码
算法求解过程中，需要不断地对新生成的解进
行适应度值的评估，因此需要将其解码成为一个可行的调度方案。根据文献［1］中的介绍，调度可以分为无延迟调度、活动调度和半活动调度，且最优的调度解一定位于活动调度当中。因此，本文使用文献［12］所介绍的一种常用的解码思路，针对所设计的编码，将生成的新码（新的调度解），根据依次得到的作业、工序和机器信息码所包含的每个工序的调度信息，将对应的工序插入到被指派机器上的空闲时段内，最终解码成为一个活动调度方案进行相关调度指标的考察。
具体解码时，考察每个工序所分派的机器上已安排的待加工工序情况：如果其上待加工工序间存在符合约束条件的、足够的空闲时段，则将工序尽可能早的安排到此空闲时段内等待加工；否则，就在满足约束条件的情况下，将工序尽量早地安排在该机器上待加工工序队列的队尾。
3
改进的博弈粒子群算法
3.1
传统粒子群算法
传统的粒子群算法（particle swarm optimization
algorithm ，PSO ）由Kennedy 在考察鸟群协同觅食等行为之后，于1995年提出，算法最终总结了如下的速度、位移迭代公式［14］。
v next =wv cur +c 1r 1(p *-x cur )+c 2r 2(g *-x cur )（1）
x next =x cur +v next
（2）
式中：w 、c 1和c 2分别表示惯性系数、个体认知系数和社会认知系数，
w 是维持迭代进行的基本参数；v cur 和x cur 表示当前的速度值和位移值；
v next 和x next 表示下一步的速度值和位移值；
p *表示个体经历过的最好位置；
g *表示当前代中所有个体所经历过的最好位置中最优的一个位置，即，全局最优位置；r 1和r 2为一组(0，1)内的随机数，用以维系元启发式算法的
activity是什么意思随机性。其中，每个工序分量的x next 值被用作所有工序排定次序时的比较依据。3.2
博弈粒子群算法
当要使最大完工时间（C max ）指标最小时，需要令每台加工机器的负载（L k ）尽可能的饱满和平衡，因
每台机器对各工序的加工性能（处理时间）不同，这种安排不可能将每个工序都安排在使其加工时间最小的机器之上，根据总机器负载（L total ）的定义，这将令该指标值增加；同理，要使总机器负载指标值最小，则需要将各个工序都尽量安排在使其加工时间最小的机器之上，这种安排常常会造成工序被集中分派给某些加工性能强的机器，即对大多数工序有较短的加工处理时间的机器（如表2中的机器2），造成这些机器的负载增加，从而令整个调度方案的最大完工时间增加；而要使最大负载机器负载（L max ）指标减小，必然要以增加其他加工机器上的负载为代价，即将当前最大负载机器上的某些工序重新合理地分派给其它的加工机器处理，通常情况下，最大负载机器多是加工性能较强的机器，向其它机器分派这些工序同样会造成其被处理的时间增加，从而引起总机器负载指标值的增加。
因此，当同时考虑优化最大完工时间、总机器负载和个体最大机器负载三个指标时，必然会产生需要调和的矛盾，本文充分利用这些矛盾，为每个粒子构建了个体博弈解集，同时为整个群构建了一个群
queena什么意思体博弈解集，
然后分别随机使用个体博弈解集和群
图1
算法迭代中字符数串编码更新过程
Fig.1
Updating process of the character -number string encoding in iteration
1785
同济大学学报（自然科学版）第48卷
体博弈解集中的一个解代替传统粒子群公式（1）、（2）中的p*和g*参与迭代运算。在每个粒子完成各分量的迭代计算之后，针对产生的新解再与原有个体博弈解集中的解进行逐个地博弈，根据博弈的结果，更新和维护每个粒子的个体博弈解集；同时根据进一步博弈的结果维护群体博弈解集。此时，传统的粒子群公式变为
v next=wv cur+c1r1(p rep-x cur)+c2r2(g rep-x cur)（3）
x next=x cur+v next（4）式中：p rep表示随机地从粒子的个体博弈解集中选出的一个博弈解；而g rep表示随机地从群体博弈解集中选出的一个博弈解。
吸血鬼日记 第四季博弈即一些个人、对、组或者其他组织，面对一堆的环境条件，在一定的规则下，同时或先后，一次或多次，从各自允许选择的行为或策略中进行选择并加以实施，从而获得各自结果的过程［13］。经过对上述算法改进策略的分析，易知本算法能够成功的关键是利用博弈规则生成有效的个体博弈解集和群体博弈解集，因此博弈规则的设计和订立直接影响着本算法的最终求解效能。
3.3博弈规则
本文制定的博弈规则如下：
（1）博弈成功规则：依次取出个体博弈解集中的一个解与当前的新解进行博弈，当新解对应的调度方案中至少有1个指标优于正与之博弈的个体博弈解集中的某个解的对应指标，且另2个指标均不劣于正与之博弈的解的对应指标，则用当前的新解替换正与之博弈的个体博弈解集中的解；同时触发下一级的博弈，即使用当前的新解继续与群体博弈解集中的所有解进行逐个博弈，同样，当新解对应的调度方案中至少有1个指标优于当前正与之博弈的群体博弈解集中的某个解的对应指标，且另2个指标均不劣于当前与之博弈的解的对应指标，则用新解继续替换群体博弈解集中正与之博弈的解。
（2）博弈相持规则：不论在哪一级博弈中，当新解中至少1个指标优于当前正与之博弈的解的对应指标，而又未达替换正与之博弈的解的条件时，将当前的新解加入到正与之博弈的解所在的解集中。即，当前新解若处于与个体博弈解集中的所有解进行逐个博弈的阶段，则仅增添至个体博弈解集中；若处于与群体博弈解集中的所有解进行逐个博弈的阶段，则仅增添入群体博弈解集中，而此时，个体博弈解集中的某个解应已被当前新解所替代。
（3）博弈失败规则：不论在哪一级的博弈中，当新解中所有的指标均不优于正与之博弈的解的所有对应指标，则放弃该新解，停止博弈，各博弈解集维持不变。
特别需要说明的是，算法开始运行时，当每个粒子被用随机位置完成初始化后，此粒子所对应的解即为每个粒子个体博弈解集中的初始解，并直接与群体博弈解集中所有的解进行逐个博弈，以维护群体博弈解集；而群体博弈解集中的初始解，则默认为第一个被随机位置初始化的粒子所对应的解。3.4算法流程
新的改进算法在本文中被命名为博弈粒子群算法（Gaming PSO）。为方便算法流程的阐述，假设粒子编号为p no，种群规模数为N，迭代计数为r，算法的总迭代次数为R，算法流程如图2所示。
开始
初始化：
工业机器人教育
问题基础信息表的建立；
对表示各粒子的字符串数组初始化；
在个体初始位置建立个体博弈解集并更新群体博弈解集；
r:= 0; ...
(r ++) < R ?
(p no ++) N ?
使用公式(3)和(4)更新当前粒子的各分量位移
(工序排序数)，并用对所有排序数排序，根
据各排序数的位次生成一组次序码。
根据次序码，对所有工序进行重新排列，生成
新的解，并对新解的目标指标进行评估。评估
时借助解码所得的调度方案，生成反向调度方
案，并确定和标识关键工序。
对关键工序的备选机器进行重新安排，
并对新得到的解的目标指标进行评估。
p no:= 1；
结束
Yes
Yes
No
No
图2博弈粒子群算法流程
Fig.2Flow of gaming PSO algorithm
1786
