考虑加工时间和交货期模糊的批调度问题研究

王雷雷，赵永中，司佳佳，李小林

（中国矿业大学矿业工程学院，江苏 徐州 221116）

1 引言

批处理机调度问题广泛存在于半导体加工、钢铁的热处理、港口货物装卸等生产场景中。不同于经典调度问题，批处理机可以将多个工件作为一批同时进行加工。其中，半导体加工的热处理操作是典型的批处理机调度过程，该加工过程中，多个工件作为一批同时进行预烧处理以识别出早期失效的产品，根据产品的类型、质量等级等要求不同，预烧的时间甚至会长达120h，从而很容易成为瓶颈工序。

当产品可靠度水平要求不同时，其预烧时间通常会是一个区间值，同时随着当前生产实际中顾客需求不确定性提高，产品的交期也经常出现大幅波动，因此对考虑模糊加工时间和交期的成批调度问题进行研究，并以满意度为目标设计算法对问题进行求解。

对于单机环境下批处理机调度问题，文献［1］首先对工件具有差异尺寸的预烧模型进行研究，证明该问题是强NP 难的。文献［2］提出了一种改进的粒子群算法，解决了求最小化最大延迟惩罚的单机批调度问题。文献［3］研究了相同交货期的差异尺寸工件批调度问题，用精确算法对最小化工件总提前和延迟的目标进行求解。文献［4］研究了目标为最小化工件最大延迟的单机批调度问题，提出了一种改进的粒子群优化算法。文献［5］提出了蚁群-鱼群混合算法来解决最小化工件制造跨度的目标。文献［6］研究了在单批处理机上最小化工件完工时间的问题，提出了最大最小蚁群算法对该问题进行求解。

上述研究均是建立在时间参数确定的基础上，但工件在实际加工过程中，由于工人和机器的不确定性，产品可靠性要求不同，加工信息不能准确预知，相关的时间参数是模糊的，进而具体交货期也无法确定。随着模糊调度理论在生产实际中的运用越来越广泛，更多的学者开始投入到模糊环境批调度的研究中。文献［7］考虑了模糊加工时间，建立了模糊完工时间模型，设计了蚁群算法，并采用特殊标准来选择蚂蚁的路径。文献［8］用梯形模糊数表示模糊交货期，研究目标转化为决策者对该工件完成时间具有的满意度，并使用改进的帝国主义竞争算法（MICA）对问题进行求解。文献［9］建立了模糊环境下的批容量问题、优先约束问题、交货期问题和加工时间问题的一些单机批加工调度模型，并且给出了相应的求解算法。文献［10］基于模糊加工时间和模糊交货期建立了三种调度问题的模型，并采用遗传算法搜索最优排序。文献［11］同时考虑模糊加工时间和模糊交货期，两者均用三角模糊数表示，对于最小化工件的提前和延迟目标提出了一种混合的差分粒子群算法。文献［12］研究了模糊环境下的并行批处理机问题，以最小化完工时间为优化目标，提出了模糊蚁群优化算法对问题进行求解。

现有研究大多考虑一种模糊量或者使用相同模糊数表示多个模糊量，而实际生产中，工件加工时间受加工特征及机器的影响与生产计划所确定的顾客订单交期通常具有不同的模糊数特征。因此，对工件加工时间与交货期采用不同模糊数的批处理机调度问题进行研究，结合现有文献中对加工时间和交期的模糊处理方式，分别采用三角模糊数和梯形模糊数表征工件的模糊加工时间和模糊交货期。由于不同类型模糊数运算的差异，进一步将工件延迟转化为完工时间相对于交期的满意度，建立了工件模糊交货期和模糊加工时间的隶属度函数与决策满意度的函数关系。在此基础上提出模糊批调度数学模型，设计了改进帝国主义竞争算法对该问题进行求解，并通过仿真实验对算法求解效果进行分析。

2 模糊环境下单机批调度问题

2.1 问题描述

模糊环境下单机批调度问题可描述如下：将n个工件的集合J={1 ，2，3，…，n} 安排在一台批处理机M上加工，任一工件j具有差异化的尺寸sj。在满足机器容量的条件下，可将多个工件分配至同一批进行加工。任一工件只分配至一个批中进行加工，批加工过程不允许中断。

考虑实际生产中加工时间的不确定性，采用三角模糊数表示工件模糊加工时间，即工件j在批处理机上的加工时间为(pj1，pj2，pj3)，采用梯形模糊数表示工件模糊交货期，任一工件j具有模糊交货期晚于交货期完工的工件j赋予一定的延迟惩罚βj。

工件j的加工时间隶属函数，如图1所示。

图1 工件加工时间隶属函数图Fig.1 Membership Function Graph for Processing Time of Job

在模糊加工环境下，工件j的完工时间等于所属批的模糊完工时间，任一批b的模糊完工时间由批工件的模糊加工时间取大得到，即批b的完工时间可由其所处位置k计算得到则工件完工时间隶属度函数，如式（1）所示。

2.2 优化目标

当采用梯形模糊数表示模糊交期时，工件的最优交期会处于一个模糊区间，为了避免拖期，需要将工件尽量安排在模糊交期范围内完成交货。因此，批完工时间相对于交货期梯形模糊数所处的位置即表达了顾客对于该完工时间的满意程度。即顾客满意度可根据交货期梯形模糊数的后半部分与工件模糊完工时间运算取得。可用二元组（dj1，dj2）来表示完工时间相对于交期的满意度，这里，dj1和dj2分别表示工件j交货期模糊数的后两个参数，即工件j按时交货时间与拖后交货时间。从而，工件j的交货期隶属函数可，如图2所示。相应的隶属度函数，如式（2）所示。

图2 工件交货期隶属函数图Fig.2 Membership Function Graph for Due Date of Job

显然，满意度指数随着交货期隶属度函数与完工时间隶属度函数叠加区域的变化而变化，可能具有重叠区域，也可能无交集。当二者无重叠区域时S1=0 ，则满意度指数AI=0 ；当二者重叠区域S1=S，则满意度指数AI=1 ；否则重叠区域会出现如下三类部分重叠的情况，如图3所示。

图3 隶属度函数重叠区域Fig.3 Membership Function Overlap Region

根据图3中完工时间及交货期隶属函数重叠区域，可得三种情况下满意度指数分别为：

2.3 优化模型

问题所涉及参量说明如下：

cap：机器容量；sj：工件j尺寸；

SIj：工件j不满意度指数，SIj=1-AIj；

βj：工件j延迟惩罚系数。

结合问题描述及满意度定义，建立考虑模糊加工时间和交货期的批调度问题数学优化模型如下：

式（6）表示目标函数为最小化不满意度UD，其中SI由上述不满意度公式计算；约束（7）表示决策变量；约束（8）表示一个工件仅出现在一个批中；约束（9）表示任一个批的工件加工尺寸之和不得超过机器容量；约束（10）表示任一个批的模糊加工时间取决于对该批中所有工件进行模糊取大操作；约束（11）表示模糊批完工时间；约束（12）表示工件模糊完工时间与所在批相同；约束（13）和（14）确保每批的开始时间大于或等于其前一批的完成时间。

3 求解算法设计

帝国主义竞争算法（ICA）由文献［13］首次提出，其基本思想来源于帝国主义殖民竞争机制。近年来帝国主义竞争算法的应用越来越广泛，文献［14］对帝国竞争算法进行了改进，解决了虚拟装配过程中装配序列规划的问题。

ICA把种群比喻为世界，种群中的个体为国家，解的优越性与国家能力的大小具有一致性。一个帝国由一个宗主国组成，宗主国拥有多个殖民地。殖民地受所属宗主国以及其他帝国中的宗主国和殖民地的影响，会发生移动。当殖民地的成本低于其宗主国成本时，两者位置互换，然后帝国之间竞争吞并。在下一次竞争中，强者获胜，循环往复直至最后，世界只剩下一个帝国，完成算法搜索。

3.1 帝国集团编码与初始化

在帝国主义算法中，每个解称为一个国家，对于n个工件的成批调度问题，每一个解可以表示成一个n维的向量，Ki=(k1，k2，k3，...，kn)，即表示第i个国家，向量中的每个分量为该位置的工件编号，采用随机键（Random Key）编码的方式随机生成工件序列集合作为初始国家集合。

3.2 国家成本函数计算

为了直观的评判一个国家势力的强弱，用成本函数作为标准：Ci=f(Ki)。成本函数与国家势力成反比。成本函数用于计算给定问题的目标函数，对应不满意度。

对于任一工件序列，设计BFEDD分批规则来求解每个国家的成本函数如下：

算法BFEDD（Best Fit Earliest Due Date）：

（1）选择工件序列首部第一个工件，将其放入到当前可以容纳它且该批次剩余容量为最小的批中。如果所有工件分配完毕，转（3）；

（2）若现有批次均无法容纳该工件，创建新批，转（1）。

（3）将批列表按交期非减排序，并顺序安排至机器，得出任一批的完工时间。

（4）结合2.2节中各AI计算公式，计算任一工件满意度指数，以及总体不满意度指数，即为成本函数。

假设所有国家数为N，其中有Nimp个国家由于势力强大成为宗主国，则剩下的Ncol个国家成为殖民地，且N=Nimp+Ncol。殖民地按一定的比例分配给宗主国，Nimp个宗主国获取相应的殖民地后，则建立了Nimp个帝国。

3.3 帝国同化殖民地策略改进

同化政策发生在每个帝国内部，是殖民地向宗主国不断靠近的过程，具体是指沿着宗主国和该殖民地间连线随机移动一个距离x，其中，x必须满足均匀分布：x∼U(0，α*d)，α为大于1的数，通常取α=2。为了增加算法的搜索广度，赋予一个随机角度偏移量θ，且θ满足均匀分布：θ∼(-γ，γ)，通常情况下γ=π/4。

为了避免在同化过程中搜索方向单一，即殖民地只受所属宗主国的影响的情况，这里考虑殖民地同时受所属宗主国和帝国中的其他殖民地以及其他帝国中的宗主国的影响。同时，国家之间的“距离”越小，产生的影响越大。为了提高算法的全局搜索能力，同时考虑不同国家之间距离的非线性影响，国家之间的吸引力计算设计如下。

用OFi表示目标函数，wi代表国家势力，di代表两个国家间的距离。其他宗主国对该殖民地的吸引力为γi，殖民地对殖民地的吸引力为η。

当国家1受到超过三个国家的影响时，此时国家1移动后的情况如式（16）。

式中：α1—国家1维持原状的可能性；αi(i=2，3，4)—国家1向各个国家移动的概率，0 ≤αi≤1，—当事国的现状；ximp1—所属宗主国的现状；ximp2+ximp3+...+ximpN—相邻宗主国的现状；xcol2+xcol3+...+xcolM—同一帝国中，其他殖民地的近况，随机数ri(i=1，2，3，4)∈[ 0，1 ]。

当殖民地在多方国家影响下到达一个新位置时，在新位置上的势力可能比其宗主国的势力更大，其成本也更低。此时，就将该殖民地和宗主国的位置互换。

3.4 改进的帝国主义竞争算法

改进的帝国主义竞争算法（IICA）步骤如下：

（1）根据帝国集团编码方法，生成N个国家，完成国家初始化。

（2）根据国家成本函数计算方法，对帝国集团任一国家Ki计算其当前的成本函数。确定了Nimp个帝国后，每个帝国中的宗主国对应的成本函数做为当前帝国的最优解。

（3）根据同化策略改进方法，计算每个帝国中殖民地同化后的成本函数，若小于其宗主国的成本，则将当前最优解更新。帝国之间进行竞争，计算每个帝国的总成本，势力大的帝国吞并势力小的帝国中的国家，消除最弱帝国。

（4）判断算法终止条件（达到最大迭代次数Nmax或最终剩下一个帝国），若满足终止条件，则输出最终的调度方案及不满意度，否则转（3）。

4 仿真实验

4.1 参数选取

这里采用随机方法产生算例，算例的规模包括工件个数（n），工件的加工时间工件尺寸和工件交货期。pj2大小服从均匀分布，分别在［1，10］和［1，20］随机产生。设机器的容量cap为10。工件尺寸sj分别从均匀分布［1，10］、［2，4］和［4，8］中产生。因此，算例类别共计10×2×3=60 类。具体的参数和水平，如表1所示。

表1 实验数据的工件参数Tab.1 Various Parameters of Experimental Data

其中，交货期的产生方式如下，确定单个工件平均模拟加工时间和平均模拟批数，由此获得总模拟加工时间BP。

交货期参数dj由以下均匀分布产生：

式中：l和h—下限和上限，分别设置为0.1和0.7。

4.2 实验结果及分析

在本节中，将IICA 算法的结果与原始ICA 和文献［8］提出的MICA 算法进行比较。IICA 算法中设置国家规模为1.5n，Nimp的比例为0.15，α1，α2，α3，α4分别为0.25，0.125，0.125，0.5。对每类算例生成10个实例，以平均值进行比较。按照加工时间不同，将工件尺寸分别为［1，10］，［2，4］［4，8］求得的结果取均值。由于目标函数是最小化UD，定义任一算法A相对于所提IICA算法差距公式Gap（A）%如下。

式中：UD（A）—算法A所求的目标函数UD值。

由表2可看出，IICA 算法总体上优于MICA 算法，平均幅度达到3.2%，IICA算法优于ICA 算法的幅度平均达到7.5%。将表2获得的ICA、MICA和IICA的结果按照加工时间不同做比较，P1和P2时间下的分类显示，如图4、图5所示。

图4 P1类中每个算法的结果Fig.4 The Result of Each Algorithm in Class P1

图5 P2类中每个算法的结果Fig.5 The Result of Each Algorithm in Class P2

工件的总不满意度随着工件规模越大呈现上升趋势，当工件规模较小时，无论是P1类还是P2类，ICA、MICA和IICA获得的最终结果差别不大，但随着工件规模的增加差别越来越明显，ICA的优化效果最差，IICA的优化效果要优于ICA和MICA。

为了进一步比较算法的性能，这里设计了统计分析实验对算法进行统计检验。首先将实验输出结果数据进行正态性检验得出数据符合正态分布，随后利用方差分析（ANOVA）模型进行检验。

模型显示为：

式中：μ—整体平均值；

τi(i=1，2，3)—3种不同算法的效果；

βj(j=1，2...60)—第j个样本的实例效果；

εij—随机误差。

采用95%的置信度进行检验，检验结果，如表3所示。基于P值对三种算法进行比较，可认为置信度检验是可靠的。为了比较各算法之间的性能排序，选用Least Significant Difference（LSD）进行检验结果，如表4所示。

表3 算法的ANOVA结果Tab.3 ANOVA Results of Algorithm

根据LSD测试的结果，可知三种算法的性能之间存在显著差异。通过分析可以得出，IICA具有最佳性能。这表明，改进后的殖民地移动策略提高了ICA的性能，同时，嵌入有效地启发式规则，能够有效地提升搜索解空间的效率。

5 结论

对加工时间和交货期模糊的成批调度问题进行了研究，将确定型环境下的工件总延迟目标转化为模糊制造系统中的不满意度，构建了问题的模糊数学模型。针对帝国主义算法容易陷入局部最优的问题，改进殖民地的移动策略，结合批调度的启发式规则设计IICA算法对问题进行求解。设计仿真实验对IICA的有效性进行分析，IICA算法在各类算例平均优于MICA和ICA算法的幅度分别为3.2%和7.5%。这里所研究问题可扩展到考虑工件到达时间的不确定性以及多机环境等情况，对于模糊环境下工件准时交货的目标也可进一步研究。