求解分布式两阶段装配流水车间调度的帝国竞争–协作算法

陈雅玲，雷德明

(武汉理工大学自动化学院，湖北武汉 430070)

1 引言

作为一类在消防车装配[1]，电路板生产[2]，塑料生产[3]和多页发票打印系统[4]等制造过程广泛存在的调度问题，两阶段装配流水车间调度问题(two-stage assembly flow shop scheduling problem，TAFSP)是实现批量生产和生产柔性间平衡的有效手段，它包含加工阶段和装配阶段，产品或工件的所有部件在加工阶段完成加工后，在第2阶段装配成最终产品或工件.分布式两阶段装配流水车间调度问题(distributed twostage assembly flow shop scheduling，DTAFSP)是TAFSP 在多工厂环境下的扩展，以快速响应市场和客户需求的变化.

近年来，TAFSP研究取得较大进展，研究者采用精确算法如分支定界[5-7]、启发式方法[8-10]和智能优化方法包括禁忌搜索[11]、粒子群优化算法(particle swarm optimization，PSO)[12]、蛙跳算法[13]、帝国竞争算法(imperial competitive algorithm，ICA)[14]、人工免疫系统算法[15]、迭代贪婪(iterative greed，IG)[16]、变邻域搜索(variable neighborhood search，VNS)[17]、模拟退火[18]和遗传算法(genetic algorithm，GA)[19-20]等对具有DPm→1布局的问题进行求解，其中DPm→1布局由加工阶段所需的m台专用并行机和装配所需的单装配机组成.

DTAFSP问题通常包含两种工厂结构，一种由F个具有DPm →1等布局的工厂组成，另一种由F个加工工厂与一个装配工厂组成.对于每个工厂具有DPm →1布局的问题，Xiong等[21]应用VNS、简化VNS和GA的混合算法(GA-RVNS)优化makespan和平均完成时间的加权和.Deng等[22]给出了问题的混合整数规划模型和一种竞争模因算法(competitive memetic algorithm，CMA).针对第2类DTAFSP，Hatami等[23]运用VNS和IG最小化最大完成时间.Wang等[24]提出一种结合memetic算法的分布估计算法.Lin等[25]设计了一种混合生物地理学优化方法.Lin等[26]提供了一种回溯搜索超启发式算法.Zhang等[27]应用启发式算法，混合VNS和混合PSO求解柔性装配的问题.Shao等[28]提出了3种启发式方法，VNS和迭代局部搜索算法.Sang等[29]设计了3种离散的杂草入侵算法.Pan等[30]构建了混合整数线性模型，并给出了3种构造性启发式算法，两种VNS和一种IG.Ferone等[31]提出了一种偏随机迭代局部搜索算法.

如上所述，第2类DTAFSP受到更多关注，尽管具有DPm →1布局的TAFSP得到广泛而充分的研究，但每个工厂具有DPm →1布局的DTAFSP研究进展却相对较小.由于DPm →1布局的TAFSP在实际制造过程中应用广泛，随着经济全球化的深入发展，有必要研究这类TAFSP在多工厂环境下的扩展问题即前述第1 类DTAFSP.另外，智能算法如GA，CMA，VNS和分布估计算法等已成功应用于DTAFSP的优化求解.由于DTAFSP的高度复杂性和智能算法在复杂优化问题求解方面的优势[32]，有必要深入探讨智能算法如ICA等在DTAFSP的应用可能和优势.

ICA是一种受社会政治行为启发的新型智能算法.它既是有效的全局搜索算法，又具有很强的局部搜索能力.ICA能有效地实现全局搜索与局部搜索的协调，适用于不同种类的优化问题，同时还具有灵活性、鲁棒性和可扩展性等显著特征.目前，ICA已广泛应用于函数优化[33]、生产调度[34-36]、最优潮流问题[37]、结构优化问题[38]、PID参数优化[39]和电能分配问题[40]等.

针对每个工厂DPm →1布局的DTAFSP，提出了一种新型帝国竞争-协作算法(imperialist competition and cooperation algorithm，ICCA)以最小化总延迟时间.该算法通过应用最强帝国与最弱帝国间协作和新型帝国竞争策略以逼近问题的最优解.通过大量实验测试ICCA的新策略对其性能的影响，并将ICCA与其他算法进行对比.实验结果表明ICCA在求解DTAFSP方面具有较强的优势.

2 问题描述

DTAFSP由n个工件J1，J2，···，Jn和F个分布在不同位置的同构工厂组成.每个工厂f内有m台专用并行机Mf1，Mf2，···，Mfm和一个用于装配的机器AMf.每个工件由m个部件组成，这些部件先在第一阶段由m个不同的机器进行加工，当一个工件的所有部件加工完成后，由装配机进行装配成最终的工件.同一工件在不同工厂中的加工时间、装配时间和准备时间相同.pik和sik表示加工阶段机器Mfk上Ji的加工时间和加工前的准备时间.ai和sai表示Ji在装配阶段的装配时间和装配前的准备时间.di表示工件Ji的交货期.

表1 参数和描述Table 1 Parameters and description

还需满足以下约束:

1) 所有机器在0时刻均可加工工件.

2) 忽略运输时间.

3) 一台机器同一时刻只能加工或装配一个工件.

4) 每个工件在同一时刻只能由一台机器加工或装配且加工过程不能中断.

DTAFSP包括工厂分配子问题和调度子问题，工厂分配用于确定每个工件所在的工厂，调度用于确定工件加工的顺序，两个子问题之间具有强耦合关系，即工厂分配结果对调度子问题具有显著影响，需将两个子问题有效地结合在一起，才能得到最优解.

问题的目标函数为最小化总延迟时间

其中:Ci为工件Ji的完成时间，Ttot为总延迟时间.

3 基于ICCA的DTAFSP

3.1 帝国初始化

DTAFSP包含工厂分配子问题和调度子问题.Deng[22]提出了一种编码方式，其编码串为{π1，···，πh1，*，···，*，，···，πn}，它由F -1个*和n个工件表示，*为分隔符，将n个工件分割成F个部分，每个部分代表对应工厂的调度串.其中hf表示工厂f所分配的工件数，

本文也使用上述编码方式，只是将*替换成n+1，n+2，···，n+F-1，其中n+1，n+2，···，n+F-1的作用和*一样，也是分割符，这样处理的目的是为了执行基于顺序的交叉(order based crossover，OBX)[41].

解码时，由编码串得到每个工件的调度串，对每个工厂f的调度串，从调度串的第一个工件开始，对每个工件，安排其部件加工，所有部件加工完成后进入装配阶段.

表2描述了DTAFSP的一个实例，包括10个工件和2个工厂，每个工厂2个机器.它可能的编码串为[2 1 8 3 11 4 6 7 9 5 10]，工厂1的调度串为J2，J1，J8，J3，工厂2的调度串为J4，J6，J7，J9，J5，J10，在各个工厂根据其调度串依次安排工件的部件加工和装配.图1为最终所得的甘特图.

表2 参数和描述Table 2 Parameters and description

图1 可行解的甘特图Fig.1 Gantt chart of a solution

随机生成S个初始解，构成初始种群P.

采取如下步骤构造初始帝国:

步骤1计算每个解xi ∈P的成本，并对种群内的所有解按成本值进行升序排序，假设c1≤c2≤···≤cS.

步骤2确定Nim个成本最小的解作为殖民国家，所有殖民国家构成集合H，计算殖民国家的归一化成本

步骤3确定殖民国家k的势力

和殖民地数量NCk=round(Ncol×powk).

步骤4将殖民地随机分配给相应的殖民国家，构成Nim个帝国，每个帝国由一个殖民国家和它的殖民地组成.其中round()为四舍五入取整函数，Ncol=S-Nim表示殖民地总数.

帝国k的归一化总成本定义如下:

其中:Qk表示殖民国家k所拥有殖民地的集合，通常，ξ=0.1.对所有帝国按降序排序，假设.显然，帝国1为最强帝国，帝国Nim为最弱帝国.

3.2 同化和革命

同化和革命是产生新解的主要途径.同化过程中，帝国中的殖民地沿着殖民国家的方向移动ν，移动距离ν是区间[0，τ ×e]中的一个随机数，其中τϵ(1，2).e是殖民地与殖民国家间的距离.为了扩大搜索范围，加入一个随机偏移量θ，它服从[-φ，φ]内的均匀分布，其中φ是一个参数.革命与GA的变异操作类似，能够增强ICA的搜索能力，防止算法早期收敛到局部最优.

由于DTAFSP的离散特性，同化与革命需要离散化，而不是直接利用ICA上述方式.

提出了一种基于帝国协作的同化和革命，其详细步骤如下:

邻域结构N1描述如下:随机选择两个工厂，在总延迟时间较大的工厂中随机选择一个工件插入到另一个工厂.N2则是将总延迟最大工厂中随机选择的工件Ji和从其他工厂随机选择的工件Jj互换.N3在总延迟最大工厂中随机选两个工件并进行互换.N4的步骤为:随机选择两个工厂，在其中一个工厂中随机选择一个工件，插入到另一个工厂中.

保留集Mk用于存储帝国k的历史优化数据.外部档案Ω保存ICCA进化过程中产生的最好解.通过实验确定Mk的最大规模为10，Ω最大规模为15.这两个集合采用同样的更新方式，当用x更新它们时，以Mk为例，若最大规模未达到，则直接将x添加到集合中;否则，如果x优于集合内的最差解，则直接替代最差解.

上述同化和革命过程中，帝国1，2，···，Nim-1独立进行同化和革命，帝国Nim只有部分殖民地按照其它帝国相同的方式进行同化和革命，其他殖民地不单独进行同化和革命，而是将这些殖民地所属的计算资源提供给最强帝国即帝国1，利用其较强的搜索能力，为帝国Nim提供新解，实现两者协作.当＜W时，将帝国Nim的一半计算资源与帝国1的搜索能力进行交换，否则将帝国Nim的所有计算资源与帝国1的搜索能力互换.帝国1中的解质量较高，利用这些解很容易生成高质量的解提供给最弱帝国，从而避免最弱帝国计算资源的浪费，提高搜索效率.

3.3 帝国竞争

通常，帝国竞争的具体过程如下:计算每个帝国的总成本TCk，归一化总成本以及势力EPk，构造向量[EP1-r1EP2-r2···]，EPg-rg最大的帝国为取胜帝国g，将最弱帝国的最弱殖民地分配给帝国g，其中ri是随机生成的，且ri∈[0，1]，i=1，2，···，Nim.由于最弱帝国的最弱殖民地质量较差，直接将其加入获胜帝国会影响获胜帝国的质量，为此，提出新型帝国竞争过程.

新型帝国竞争的具体过程描述如下:

2) 随机选择一个解x ∈Ω，执行λ与取胜帝国g的殖民国家之间的OBX，生成新解.

3) 若新解优于最弱帝国的最弱殖民地，则将新解加入到取胜帝国g，并且更新Ω.否则，将最弱帝国的最弱殖民地转移到取胜帝国g中.

3.4 算法描述

ICCA的具体步骤描述如下:

步骤1初始化.随机产生初始种群P，确定Nim个殖民国家，构造Nim个初始帝国.

步骤2计算所有帝国的归一化总成本并降序排列.

步骤3每个帝国执行同化与革命.

步骤4确定每个帝国内的殖民国家和殖民地之间是否需要互换，若是，则用殖民地更新殖民国家.

步骤5计算所有帝国的归一化总成本并降序排列.

步骤6执行新型帝国竞争.如果一个帝国的殖民地数量为0，则直接删除该帝国.

步骤7若满足终止条件则停止搜索，否则返回步骤2.

图2描述了ICCA的流程图.ICCA的时间复杂度为O(S×UR×R×Loop)，其中Loop为步骤2-6的循环次数.

图2 ICCA流程图Fig.2 Flow chart of ICCA

和现有ICA不同，ICCA具有以下特点:

1) 对殖民国家的归一化成本和帝国的势力进行重新定义，以保证殖民国家和帝国势力都不为零，从而使所有殖民国家都能分配一定数量的殖民地，让所有帝国能参与竞争.

2) 为了充分利用计算资源，通过最强帝国搜索能力与最弱帝国计算资源的自适应交换，实现了最强帝国与最弱帝国间的协作.

3) 采用新型帝国竞争过程，利用外部档案内的解与取胜帝国的殖民国家间的交叉产生新解.这样整个算法中，既有帝国之间的竞争过程，又有帝国间的协作.

4 实验结果与分析

为了测试ICCA在求解DTAFSP方面的性能，进行了大量实验，所有测试实验均用Microsoft visual C++2019 编程实现，在8.0 G RAM 1.60 GHz CPU环境下运行.

4.1 测试实例和比较算法

文献[21]生成了27个小规模实例和100大规模个实例，本文直接按照该文献的方式产生127个实例，其中交货期定义如下:

其中α ∈[0.2，1.2].

选用CMA[22]，VNS[21]和GA-RVNS[21]为对比算法，它们本身就是用来求解DTAFSP，当目标函数改为总延迟时间后，它们能直接求解本文问题，故选用它们和ICCA进行比较.为了测试ICCA的协作与竞争的有效性，将ICCA与基本的ICA进行比较.当从ICCA中删除最强帝国与最弱帝国的协作过程，帝国竞争过程直接将最弱帝国的最弱殖民地加入到取胜帝国，ICCA就变成了ICA.

4.2 参数设置

CMA的终止条件为(0.1×n)s.通过实验发现，当CPU运行时间达到(0.1×n)s时，ICCA及其它对比算法也能收敛，故ICCA和对比算法都采用了上述终止条件.

ICCA的主要参数包括S，Nim，R和UR.每个参数有两种设置，即S为60和80，Nim为6和8，R为15和20，UR为0.2和0.3，共16组参数组合.每个实例的每种组合随机运行20次.最后确定使ICCA性能最好的一组参数为S=60，Nim=6，R=20，UR=0.3.

GA-RVNS和VNS的参数取自文献[21]，CMA的参数来自文献[22]，实验表明，利用这些参数设置3种算法都获得了最好的计算结果.

4.3 实验结果与比较

针对每个实例，每个算法独立运行20次，计算每次运行所对应的相对百分比偏差(RPD)，

其中表示所有算法关于该实例所获得的最小总延迟时间.采用3个性能指标MIN，MAX和AVG，它们分别表示20次运行所获得的最小RPD，最大RPD和平均RPD.

图3描述两个实例的收敛曲线.

图3 收敛曲线Fig.3 Convergence curves

图4给出了所有算法的箱线图.表3-8描述了ICCA和对比算法的计算结果.其中实例3×50×2和实例3×200×2，由于为0，表中直接给出了所有算法的总延迟时间.

图4 所有算法的箱线图Fig.4 Box plot of all algorithms

由表3-7可知，在100个大规模实例中，其中关于69 个实例，ICCA取得了优于ICA的MIN，对于其中58个实例，ICCA获得了比ICA更好的MAX，对于63个实例得到的AVG小于ICA的相应结果，如表6所示，关于小规模实例，ICCA和ICA的结果相同或者非常接近.以上分析表明ICCA的性能优于ICA，从而验证了ICCA的协作与竞争新策略的合理性和有效性.

表3 5种算法关于两工厂实例的计算结果Table 3 Computational results of five algorithms on instances with 2 factories

表4 5种算法关于三工厂实例的计算结果Table 4 Computational results of five algorithms on instances with 3 factories

表5 5种算法关于四工厂实例的计算结果Table 5 Computational results of five algorithms on instances with 4 factories

表6 5种算法关于五工厂实例的计算结果Table 6 Computational results of five algorithms on instances with 5 factories

表7 5种算法关于六工厂实例的计算结果Table 7 Computational results of five algorithms on instances with 6 factories

如表3-7所示，ICCA关于70个实例取得了优于CMA的MIN，关于88个实例所获得的MIN小于VNS的相应结果，关于几乎所有大规模实例得到了小于GA-RVNS相应值的MIN，表明在运行时间相同情况下，ICCA的收敛性能优于对比算法.比较ICCA及其对比算法关于MAX和AVG的结果，可以发现，ICCA关于大多数实例产生了优于其3个对比算法的相应结果.从图3-4也可以看出ICCA相对于其对比算法的性能优势.总之，由于帝国竞争新策略和帝国协作的引入，使得计算效率得到改善和提高，从而导致ICCA在求解DTAFSP方面具有较强搜索优势.

5 结论

针对以总延迟时间为目标的DTAFSP，提出了ICCA.该算法在ICA的基础上增加了最强帝国和最弱帝国的协作机制，通过自适应交换最强帝国搜索能力和最弱帝国计算资源，实现帝国之间的协作.使用历史演变数据，采用新的帝国竞争方法以获得高质量的解.进行了计算实验，并与现有方法进行比较，验证了ICCA策略的有效性以及在求解DTAFSP方面较强的搜索优势.

表8 5种算法的小规模实例的计算结果Table 8 Computational results of five algorithms on small scale examples

分布式两阶段装配流水车间调度问题是一个很重要的问题，普遍存在于实际制造系统，但现有的研究还较少.未来将继续关注这类问题，并应用一些新的智能算法，比如蛙跳算法求解该问题.