柔性作业车间的成套订单调度问题

徐震浩， 周 畅， 张凌波， 顾幸生

（华东理工大学化工过程先进控制和优化技术教育部重点实验室，上海 200237）

随着产品定制服务的出现，客户对产品的定制需求正朝着多品种、小批量、成套性方向发展。成套订单问题具有广泛的实际背景，有相当一部分企业采用定制生产方式，如大型工程、船舶制造等。对于某些大型机械，其工件定制通常具有配套性以满足产品模块化组装的要求，企业的竞争力不再局限于生产的高效率和快速性，并且延伸到了工件交付的准时性和成套性。虽然成套订单的生产调度问题是加工制造业面临和亟待解决的难点，但与一般的makespan最小化问题相比，具有加权订单成套率难以提高的特点。如何跳出局部最优，提高加权订单成套率是成套订单调度问题的难点和关键。目前，与成套订单调度问题相关的文献很少，且现有的相关研究仅围绕单机或两台机器的流水车间环境进行，鲜有对柔性作业车间环境下的成套订单调度问题的研究。与成套订单调度问题类似的问题是最小化提前/拖期惩罚、最小化总拖期等，与成套订单调度问题的相同点是都需要设置工件的交货时间。Pan 等[1]利用离散蜂群算法解决了批量流水车间的最小化提前拖期问题；Zhang 等[2]提出了一种基于块特性的邻域结构，融合模拟退火算法解决了最小化作业车间总拖期时间问题；鲁建厦等[3]提出了一种基于模拟退火的混合粒子群算法，解决了最小化作业车间下总加权拖期时间问题。成套订单调度问题是存在工件交货时间的前提下同时存在订单工件的配套问题，Zhou等[4]首先提出了成套订单问题并采用遗传算法解决了单机环境下加权成套订单的调度问题；Yu 等[5]提出了采用随机键编码方式的萤火虫算法用来解决单机环境下成套订单的调度问题；周水银等[6]采用启发式规则研究解决了两台机器构成的流水车间环境下的成套订单调度问题；吴春辉等[7]提出了一种基于工件交货时间瓶颈的启发式规则，利用遗传算法解决了单一工序并行机环境下的成套订单调度问题；傅青[8]以最大化成套订单数和最小化总配送时间为多目标，采用遗传算法和启发式算法相结合的方法求解该多目标问题。

蚁群算法具有相对较好的寻优特性，广泛应用于组合优化问题中[9]。本文在最大最小蚂蚁系统（Max-Min Ant System，MMAS）的基础上，根据成套订单问题工件之间配套性的特点设计了新的邻域结构，提出了一种具有邻域结构的最大最小蚂蚁系统（ MAX-MIN Ant System with a Neighbor Structure， MMAS-NS）。通过邻域搜索反复迭代缩减瓶颈订单和瓶颈工件的交货时间瓶颈，达到消除订单工件交货时间瓶颈的效果，进而使瓶颈工件按时完工，最终达到提高加权订单成套率的目的。实验结果表明，MMAS-NS 算法能够获得加权订单成套率较高的解，表现出比其他算法优越的性能。

1 问题模型和特点

1.1 问题模型

针对柔性作业车间环境下的成套订单调度问题模型，有以下描述：n 个工件在m 台机器上加工，这n 个工件分别属于H 个订单。

订单层面看，每个订单来自不客户，对于订单h，其权重为 wh，表示该订单的重要性，它包含 nh个工件，可表示为。

（1）每台机床每次只能加工一个工件；

（2）每个工序的加工过程不能中断；

（3）工件之间具有相同的优先级；

（4）不同工件的工序之间没有前后约束；

（5）所有工件到达时间均为零。

柔性作业车间环境下成套订单调度问题的数学模型表示如下：

其中， xh是决策变量：

约束条件如下：

其中， ahijkpl和 xhijopqk是决策变量：

式 ( 1) 为问题的目标函数，即最大化加权成套订单数，它与每个订单的权值 wh和该订单的成套系数xh有关；式 ( 2) 为加工工艺约束，即工件的某一工序只有在当前机器上加工完成后，才能进入下一台机器加工该工件的下一道工序；式 ( 3) 为工序非堵塞约束（资源约束），当前工序加工之前需要等待同机紧前工序加工完成才能开始加工，同机紧后工序需要在当前工序加工完成后才能开始加工。

1.2 问题特点

柔性作业车间的成套订单调度问题是以加权订单成套率作为目标函数，因此与其他目标函数的调度问题相比，具有以下特点：

（1）加权订单成套率和工件交货期有密切关系。当交货期比较宽松时，甚至每个工件都能按时完工，进而每个订单都满足成套性要求，此时加权订单成套率为1；而当交货期设置得比较紧张时，未成套订单所包含的工件都具有较大的交货时间瓶颈，而且很难将其交货时间瓶颈削减至0。

（2）难跳出局部最优状态。搜索过程停滞时，搜索结果的进一步改进需要加权订单成套率的进一步提高，即需要未成套的订单满足成套要求，而未成套订单可能包含多个工件，需要将每个工件的交货时间瓶颈削减到0 才能满足成套要求。与以makespan作为目标函数的调度问题相比，显然成套订单调度问题的搜索过程更难跳出局部最优的状态。

2 MMAS-NS 算法

2.1 算法框架

与其他种类蚁群算法(AS、ACO)相比，MMAS具有相对更好的搜索效果，但它仍然存在和其他元启发式算法相同的缺陷：虽然全局寻优能力较强，但局部搜索能力弱，当迭代达到一定代数后，信息素集中在某条路径，种群同化现象严重，容易陷入局部最优。为了避免蚂蚁种群的过早同化，弥补群智能算法局部搜索能力的不足，本文针对成套订单调度问题的特点提出了一种新的邻域结构，结合MMAS 得到带有邻域结构的最大最小蚂蚁系统(MMAS-NS)。MMAS-NS 的流程如图1 所示。

图 1 具有邻域结构的最大最小蚂蚁系统流程图Fig. 1 Flowchart of MMAS-NS

2.1.1 编码 解的编码方式采用扩展的基于工序的编码方式。解个体由两部分组成：基于工序编码的工序加工顺序序列(OS)、基于机器编码的工序加工机器序列(MS)。OS 段的数字代表工件，数字出现的次数代表该工件对应的工序；MS 段依次代表工件工序的加工机器。一种FJSP 的编码方式如图2 所示。

图 2 一种FJSP 的编码方式Fig. 2 An encoding method of FJSP

2.1.2 终止准则 算法在150 代内振幅不超过5%时终止迭代过程。

2.2 邻域结构

2.2.1 邻域搜索算法的思想和结构 订单未成套的原因在于订单中存在工件完工时间超过规定交货期，要想该订单成套，需要削减和消除订单中瓶颈工件的交货时间瓶颈。对于订单h 中的瓶颈工件i，其交货时间瓶颈定义如下：当时，工件完工时间晚于规定交货时间，称工件具有交货时间瓶颈，该工件称为瓶颈工件，包含瓶颈工件的订单称为瓶颈订单。

文献[10]针对作业车间下makespan 最小化问题提出了有效邻域结构N5，利用关键块首和块尾工序交换缩短关键路径的长度；类似地，针对成套订单问题，重新选择针对瓶颈工件的关键路径，并利用类似N5 的工序交换操作可以缩短瓶颈工件的关键路径长度，当瓶颈订单内所有瓶颈工件的交货时间瓶颈削减到0 时，加权订单成套率得到提高。

本文提出的新的邻域结构的主要思想：首先要选择迭代最优解Xiter-best或者全局最优解Xglobal-best作为邻域搜索的个体，然后选择该个体中未成套订单中权值较大的订单，接着选择该订单中交货时间瓶颈较大的瓶颈工件。由被选择工件的尾工序开始，从后向前选择一条关键路径，参考N5 邻域结构进行关键工序位置交换产生新的解，再根据订单加权成套率对新产生的邻域解进行贪婪选择，重复以上过程直到不能继续对任何工件的交货时间瓶颈进行削减。

邻域搜索算法结构如图3 所示。图4 为邻域搜索后的调度甘特图。在8 工件5 订单的情况下，假定绿色虚线是订单5 中工件7 的交货期，邻域搜索前工件7 完工时间在交货期之后，在进行了工序O72向前插空在O83之前的操作后，工件7 的尾工序O73的完工时间减小到13，因此订单5 成套，其他工件的完工时间不变，加权订单成套率上升。

图 3 邻域搜索算法流程图Fig. 3 Flowchart of neighborhood search algorithm

图 4 邻域搜索后调度甘特图Fig. 4 Gantt chart of scheduling after neighborhood search

2.2.2 待搜索解、瓶颈订单和瓶颈工件的选择 待搜索解的选择：在邻域搜索过程中贪婪选择订单加权成套率高的解，当两个或多个解的订单加权成套率相同时，选择加权瓶颈小的订单（因为该解权值较高的未成套订单的交货时间瓶颈相对较小），订单加权瓶颈表示如下：

瓶颈订单(Choosed_order)的选择：因为进行邻域搜索的解即为蚁群算法较优的解，可优化空间较小，所以直接选择未成套订单中权值最大的订单。若两个订单权值相同，选择订单总交货时间瓶颈较小的订单。

瓶颈工件(Choosed_job)的选择：选择交货时间瓶颈大的工件。工件交货时间瓶颈越大越难以消除，若该工件瓶颈无法完全消除，可直接放弃对该订单的优化进行下一个订单的优化。

2.2.3 邻域解的生成 本文的邻域结构不改变工序的加工机器，只改变工序间的相对位置。

关键路径的选取：首先建立空的关键路径工序集Set_CriticalPath，将Choosed_job 的最后一道工序放入关键路径。设关键工序集Set_CriticalPath 中首道工序为若存在同机紧前工序和同件紧前 工 序，则 分 别 为和。 若的结束时间与的开始时间相同，则选择加入关键工序集Set_CriticalPath，否则选择加入关键工序集Set_CriticalPath，直到的开始时间为0。如图5 所示甘特图中关键工序集为

可交换工序对和工序交换：工序交换使用N5 邻域结构，N5 邻域结构被证明是一种速度较快、效果较好的邻域结构。同机相连的关键工序形成关键块。对于首关键块，只交换块尾工序和块尾的同机紧前工序；对于中间关键块，可交换块首工序和块首的同机紧后工序，也可以交换块尾工序和块尾工序的同机紧前工序；对于尾关键块，只交换块首工序和块首工序的同机紧后工序。需要注意的是，若相邻工序属于同一个工件，则不能交换。

图 5 关键路径示意图Fig. 5 Schematic diagram of critical path

邻域解生成：对于任意被选择的解个体，构造其邻域解时需要对关键路径中的可交换工序对分别进行工序位置交换，其他工序位置不变。由此所得到若干邻域解的适应度值需要重新计算。当存在邻域解的适应度值大于当前解时，则利用该邻域解替换当前解。

3 仿真实验及性能分析

成套订单调度问题优化难度较大，因此本文的测试实例是在已有FJSP 实例基础上加入工件的交货时间、订单的工件分布情况、订单权值生成。其中工件交货时间在一定范围内随机生成，订单数量、订单情况（包含哪些工件）、订单权值随机生成。随机生成规则：每个订单包含的工件采用随机插入方法生成；订单数量、订单权值由式（8）生成。

3.1 算法参数分析和整定

影响蚁群算法的参数主要有：蚂蚁数量Npop、信息素残留系数ρ、信息启发式因子α、期望启发式因子β 等。本文通过正交试验方式对算法主要参数进行分析。正交试验使用的是20 工件5 机器11 订单测试实例，工序时间表见文献[11]。正交试验因素和水平设置如表1 所示。

根据正交表给出的每一组因素水平组合情况，进行10 次试验取平均值并做方差分析。

图6 示出了不同因素下目标函数95%置信度LSD 区间均值。从图6 可以看出，算法性能与Npop、ρ、α 相关，与β 无关。随着Npop的扩大，搜索次数增加，对解空间的搜索更加彻底，算法全局搜索能力增强，解的质量将有所提高，但搜索周期会相应变长；随着ρ 的增长，信息素蒸发速度降低，算法可以持续进行更大范围的搜索，解的质量将有所提高，但收敛速度将减慢；α 越低，搜索对信息素浓度的敏感性降低，当各条路径上信息素浓度差别较大时，较低的α 可以使信息素浓度不同带来的影响减小，收敛速度减慢，搜索时间更长，得到更好的解，反之若α 较大将会使这种浓度的差别指数级放大，加快收敛速度，往往会造成搜索收敛到局部最优解；β 只在搜索开始阶段信息素浓度信息匮乏时引导搜索进行，随着迭代的进行，各路径间信息素浓度τ 的差别逐渐增大，所以随着搜索的进行，β 的作用越来越小。本文算法参数设置如下：Npop=200，ρ=0.95，α=0.5。

表 1 正交设计因素和水平表Table 1 Factors and levels of orthogonal design

图 6 不同因素下目标函数95%置信度LSD 区间均值图Fig. 6 Prediction interval graphs of objective function at different factors

3.2 邻域结构有效性分析

为了验证本文提出的邻域搜索算法的有效性，对小、中、大3 种规模实例进行仿真实验。选取未加入邻域结构的MMAS 作为对比算法，对每个实例分别利用MMAS-NS 和MMAS 进行10 次仿真，MMAS算法参数设置和MMAS-NS 相同，记录迭代过程平均值并作收敛曲线图，通过对比两种算法的收敛结果说明MMAS-NS 算法的有效性。

3.2.1 小规模实例有效性分析 小规模实例包括文献[12]中的改编测试实例1（8 工件8 机器6 订单）和根据文献[13]提出的Mk01 改编的实例2（10 工件6 机器8 订单）。两个实例的订单数量、订单所含工件、订单权值均采用随机方式生成。小规模实例的收敛曲线如图7 所示。

由图7 可知，小规模实例下MMAS-NS 和MMAS算法都能达到较好的寻优效果。因为实例规模较小，虽然MMAS 也可以达到和MMAS-NS 相近的寻优效果，但MMAS-NS 每次搜索的结果更加稳定。以实例1 为例，MMAS 在10 次优化仿真中有4 次陷入了局部最优解，而MMAS-NS 的搜索结果每次都能达到MMAS 搜索结果的最优值，因此目标函数的平均收敛曲线收敛到了更好的值。由于搜索初始阶段信息素浓度信息缺乏，且没有采用精英保留策略，采用最早完工准则选择机器的方式本身可以构造较优的初始解，因此收敛曲线初始阶段可能出现下降情况。

3.2.2 中等规模和大规模实例有效性分析 中等规实例和大规模实例由文献[14]提出的测试实例（实例3）和文献[13]提出的Mk10（实例4）改编而成。收敛曲线如图8 所示。

图8 表明，在中等规模实例3 中，MMAS-NS 比MMAS 寻优性能有很大提升，加权订单成套率从0.60 提升到了0.78，并且在200 代以后寻优速度有了明显提升。与小规模实例不同，当问题规模提升后，没有采用邻域搜索的MMAS 的搜索能力有限，而邻域搜索算法可以有效提升加权订单成套率，尤其是只含有单一工件的订单成套率。以两种算法仿真结果中目标函数值的众数为例，10 次MMAS 仿真结果众数为0.591 7，对应满足成套性的订单为1、4、6、7、10；10 次MMAS-NS 仿真结果众数为0.784 7，对应满足成套性的订单为1、3、4、5、6、7、10，MMASNS 在MMAS 实现的成套订单基础上又实现了3、5 的成套，而3、5 都是单工件订单。由于是针对订单中的单一工件采用N5 邻域结构优化（将该工件的尾工序作为关键路径的尾工序），该工件的加工时间可以有效减小，因此该订单将成套，加权订单成套率提升。大规模测试实例的收敛曲线显示，MMAS-NS 针对大规模算例也有比MMAS 更好的寻优性能，分析过程和中等规模算例类似，不再赘述。

图 7 两个小规模测试实例下的算法收敛曲线图Fig. 7 Algorithmic convergence curves for two small-scale test instances

图 8 中等规模和大规模测试实例下的算法收敛曲线图Fig. 8 Algorithmic convergence curves for medium and large scale test instances

3.3 算法性能比较

为了说明加入邻域搜索过程后MMAS-NS 算法性能的优越性，本文针对不同规模下成套订单调度问题的测试实例进行仿真验证。选择最大最小蚂蚁系统(Max-Min Ant System，MMAS)、帝国竞争算法（Imperialist Competitive Algorithm，ICA）、带邻域结构的帝国竞争算法（Imperialist Competitive Algorithm with Neighborhood Structure，ICA-NS）作 为 对 比 算法。MMAS-NS 和ICA-NS 具有2.2 节所述邻域结构。MMAS-NS 和MMAS 的算法参数根据3.1 节分析结果进行设置，ICA 和ICA-NS 算法参数设置参考文献[15]进行，ICA-NS 和ICA 的区别是在ICA 每完成一次迭代后对最强帝国代表的解个体进行邻域搜索。表2 中所有仿真实例均采用文献[16]中的仿真实例对每一个测试实例进行10 次仿真，并对仿真结果进行分析，结果如表2 所示。表2 中n 为总工件数，m 为机器数，o 表示订单数，Max 表示最大加权订单成套率（Maximum Whole-Set Orders）、Min表示最小 加 权 订 单 成 套 率（Minimum Whole-Set Orders）、Avg 表示平均加权订单成套率（Average Whole-Set Orders）、Std 表示均方差（Standard Deviation）。

由表2 可知，当实例规模较小时，4 种算法都能找到较好的解，而且加入邻域搜索的MMAS-NS 和ICA-NS 多次仿真的均方差均为0，说明在小规模测试实例下，加入了邻域结构的两种算法每次都能找到最优解。随着测试实例规模的扩大，不加入邻域搜索的MMAS 和ICA 仿真结果均值(Avg)大致相同，与MMAS-NS 和ICA-NS 相比结果较差，说明MMAS-NS 和ICA-NS 在中等规模和大规模实例下表现出更加良好的寻优性能，进而说明了邻域搜索结构的有效性。在中等规模和大规模测试实例下，MMAS-NS 比ICA-NS 的均值更好，这是因为MMASNS 的机制是在每次迭代后，针对迭代最优解个体Xiter_best 进行邻域搜索，而在MMAS 的初始阶段几乎每次迭代的最优解都是不相同的，因而在MMAS的基础上加入邻域搜索可以对解空间进行更广阔的搜索；ICA 算法具有收敛速度快的特点，而帝国和殖民地之间是进行的有条件的更替，每次迭代最强帝国不一定改变，换句话说，ICA 是自带精英保留策略的搜索算法，最强帝国一直是全局最优解（精英解），因而ICA-NS 对解空间的搜索不如MMAS-NS 充分，因此MMAS-NS 比ICA-NS 有更好的全局寻优效果。

表 2 4 种算法在不同算例下的仿真结果对比Table 2 Comparison of simulation results of four algorithms under different instances

续表 2

为了更加清楚地表现MMAS-NS 和3 种算法的搜索过程，绘制4 种算法在中等规模实例的平均收敛曲线如图9 所示。可以看出加入了邻域搜索后的两种改进算法相比原有的算法性能都得到了提升，而且MMAS-NS 可以达到最好的寻优效果。ICA 和ICANS 收敛速度较快，但基于帝国竞争算法改进的ICANS 存在邻域搜索不够充分的缺点，不过性能比ICA仍然有一定的提升。

图 9 测试实例Case3 的收敛曲线图Fig. 9 Convergence curves of case3 problem

4 结束语

成套订单调度问题是一种在实际生产过程中广泛存在并亟待解决的调度问题，但由于该问题的复杂性，目前的相关研究主要集中于单机环境且研究成果较少。本文提出了一种新的基于柔性作业车间环境下的加权成套订单调度模型，分析了解决该问题的难点，并针对问题特点提出了一种新的邻域结构。针对瓶颈订单内包含的瓶颈工件，通过反复削减工件的交货时间瓶颈，最终达到提高加权订单成套率的目的。在不同规模实例下，通过MMAS-NS和MMAS 的仿真结果对比，验证了该邻域结构的有效性。为了进一步表明算法的有效性，与帝国竞争算法ICA 等其他元启发式算法的仿真结果进行了对比，说明了MMAS-NS 在搜索性能方面的优越性及其他算法存在的不足。以上结论仅限于柔性作业车间环境下的研究，实际生产中的模型将会更加复杂。另外解个体中工序加工机器分配使用的是工序最早完工准则，如果考虑工序加工机器的安排，邻域搜索该如何改进，算法性能是否会有进一步的提升，是下一步需要考虑的问题。