王宗光，谢小青，杨玉龙，廖世龙*

(1.兰州理工大学经济管理学院，甘肃 兰州 730050； 2.山东大学管理学院，山东 济南 250100)

1 引言

批调度问题主要指工件排序及工件合批，是半导体生产过程中提炼出的新型调度问题[1]。合批根据批处理设备的容量、工件形状材质、工件到达时间以及加工成本等多种因素综合处理。因此，批调度在求解难度上远高于古典调度[2]。实践生产中，批调度以适当的时间周期或事件驱动进行循环调度，仅需考虑怎样对某一时段内的工件分批、排程[3]，将动态、长期的全局调度问题分解为各时段内静态的局部子调度问题。传统批调度在各调度周期内只使用一种方法和一种确定的规则来解决问题，以便于调度的实现。而滚动时域调度方法则是时间驱动的循环调度策略。

当前批调度的研究可分为两种：一是理论。Liu的研究表明即便单台机器的工件集只有两个到达时间，批调度问题也是NP难题[4]。Zhao证明了目标为拖期惩罚的连续型批调度问题为强NP难[5]。二是算法，研究主要集中于初始时刻全局信息完全时，利用常规算法或群智能优化算法等离线算法进行一次的全局静态调度，获得调度最优值[6-8]。Melouks和Damodaran分别采用模拟退火算法、遗传算法对制造跨度进行优化研究[9，10]。Tang和Song设计了离散粒子群算法并将其应用在钢辊热处理混合流水车间[11]。闫萍和袁媛以化工领域设备批处理过程为研究对象，构建了分批与批调度决策的优化模型并提出改进的DE算法，仿真得出与PSO算法相比，改进的DE算法性能更好[12]。

实际生产加工中，工件动态到达处理设备，对工件信息了解有限。Ovacik和Marcos较早的将滚动调度方法应用到经典调度问题中并取得了较好的效果[13，14]。但是，滚动时域调度策略下，各调度周期内只进行局部调度且很难考虑全局信息，因此，无法对全局调度性能指标作估计和控制[15]。Nelson和Sourirajan将滚动调度策略和实时状态信息结合起来，首先把动态调度过程细分为多个连续静态调度，再在每个区间内逐个优化，最后达到局部最优[16，17]，进一步适应动态生产环境的不断变化，该研究表明滚动调度策略在解决调度问题上极具适用性[18]。

针对工件动态到达且调度开始时刻工件信息不完全的批调度问题，在时域内利用粒子群算法进行调度优化寻求局部调度最优，并加入惩罚函数，确保局部调度目标与全局目标一致。对滚动时域策略下各调度规则下的调度结果进行了仿真，并对此类动态调度问题中不同参数取值下的仿真结果进行了讨论。

2 滚动时域策略下批调度数学建模

2.1 滚动时域批调度问题描述

图1 时域l中工件调度流程图

2.2 符号说明

参数符号：

T：调度时域周期长度；

B：批处理设备的容量；

j：工件集合，其中j={1，2，…，n}；

rtj：工件j的到达时间；

ptj：工件j的加工时间；

sj：工件j的尺寸；

weightj：工件j的权重参数；

决策变量符号：

l：调度时域个数集，其中l∈{1，2，…，L}，L为调度时域个数的最大值；

ctj：工件j的完工时间；

bhl：时域l内待加工工件集；

bkl：调度时域l下的第k(k=1，2，…，Kl)批工件集；

RTkl：批bkl的到达时间；

STkl：批bkl的开始时间；

PTkl：批bkl的加工时间；

CTkl：批bkl的完工时间；

CTl：时域l中最后一批工件的完工时间；

Sl：时域l内得到加工的工件集；

S′l：时域l内未得到加工的工件集。

2.3 模型假设

1) 工件集合j={1，2，…，n}，每个工件包含如下信息：rtj、ptj、sj和weightj；

2) 批设备容量为B，是各时域中各批次的工件尺寸之和的最大值。批加工一旦开始，不能中断，也不能放入新工件；

3) 以批次进行加工，批bkl的到达时间RTkl为批中所有工件的最大到达时间、加工时间PTkl为批中工件最大加工时间、开始加工时间计算方法：

当k=1时

ST1l=max{RT1l，CTl-1，(l-1)T}

(1)

当k=2，3，…，Kl时

STkl=max{RTkl，CT(k-1)l}

(2)

从而，批bkl的完工时间CTkl为

CTkl=STkl+PTkl

(3)

4) 调度时域l的周期为T。上一时域的结束时间即为下一时域的开始时间，某一时域的结束时间为该时域内最后一个批次的完工时间。

2.4 滚动时域批调度数学模型

(4)

st.Yjkl={0，1}

(5)

(6)

(7)

Sl={j|j∈bhl，stj

(8)

S′l={j|j∈bhl，stj≥l*T}

(9)

(10)

(11)

其中j={1，2，…，n}，k={1，2，…，Kl}，l={1，2，…，L}。式(4)是目标函数，表示最小加权完工时间和；式(5)中，Yjkl为{0，1}决策变量，当工件j属于时域l中第k批时，Yjkl=1，否则，Yjkl=0；式(6)用以确保所有工件都能得到分批且工件不会重复加工；式(7)是工件分批的主要约束条件，表示同一批次内所有工件的尺寸和应当不超过批设备容量；式(8)表示时域l中已加工的工件集；式(9)表示时域l中还没有加工的工件集；式(10)表示时域l中加工工件数；式(11)表示时域l内工件分批数量。

3 滚动时域批调度PSO算法实现

3.1 模型的初始化

第一个时域中待加工工件集为到达时间在周期内的所有工件集合，后续时域中待加工工件集的确定方法参照图1。假设时域l中，待加工工件数为n(l)，PSO算法的粒子数为N，各粒子用n(l)维向量表示。粒子i的位置向量Xi=(xi1，xi2，…，xin(l))，各Xi都表示一个工件序列。xij(j∈{1，2，…，n(l)})是粒子i中工件j的优先值(xij越小，越靠前加工)，随速度向量Vi=(vi1，vi2，…，vin(l))中vij的变化而变化。

3.2 PSO算法中工件排序、分批

时域l中，以先到先加工的规则进行工件初始调度，bhl按rtj从小到大依次排序。若rtj相同，ptj越小，工件排序越靠前。得到时域l内工件调度的初始排序πl，πl(i)表示πl的第i个工件。令第1个工件优先值为πl(1)=rand(0，1)，其它工件优先值为[19]

πl(i+1)=πl(i)+rand(0，1)

(12)

将待加工工件先在批设备容量B的约束条件下分批，再计算当前时域中微粒的适应值。其中，活批是工件合批过程中，若至少存在一个批bk，在将工件j放入批bk后，仍然容量约束条件，则称批bk为j的活批。否则，批bk为确定批。

为保证调度目标，决策人员不会为了尽可能填满批设备而无限制的等待满足容量约束的工件到达。对于活批bk，在批等待时间内到达的所有工件都可以合入成为同一批。分批规则：对于工件j有两种安排方式，一是若当前不存在批，或不存在对于j的活批，则j生成新的批，此时新的批为活批；二是若存在对于j的活批bk，当j的到达时间与活批bk的到达时间间隔大于批等待时间，j进入新批，此时活批bk为确定批；否则，bk仍为活批。

4 局部惩罚函数与算法流程

4.1 局部调度惩罚函数

滚动时域调度下，①各调度时域结束时，部分工件已完成加工，后续时域中全局调度的自由度减小；②各调度时域下只加工部分工件，全局信息少。因此，时域l中目标惩罚函数Δfl表示为

(13)

(14)

4.2 批调度算法流程

Step1：给出初始时刻信息不完全的n个工件集合S；

Step2：根据工件到达时间确定第一个时域l内待加工工件集合bhl，该时域内工件信息已知；

Step5：返回局部最优调度适应值fl，可得工件排序和分批，进而求得时域l内的最优目标值Fl以及时域l内得到处理的工件集Sl和未得到处理的工件集S′l；

Step6：令Tabu={j|j∈S-Sl}，若Tabu不为空集，将时域l内未热处理的工件集合S′l滚动进入l+1时域，与step2中的bhl+1合并，即bhl+1=S′l∪bhl+1，进入step3；若为空集，结束。

5 仿真研究

5.1 仿真参数设计与算法有效性分析

5.1.1 仿真参数设计

本文采用Melouks等提出的随机产生数据的方法获得算例[20]，算例划分标准如下：

1)工件个数n分为J1、J2、J3、J4、J5类问题，工件数分别为20、40、60、80、100；

2)工件加工时间ptj服从[1，20]离散均匀分布；

3)工件尺寸sj服从[1，10]上的离散均匀分布；

4)工件到达时间rtj服从[0，rnE[ptj]]的离散均匀分布，其中r={0.1，0.2，0.3，0.4，0.5}，对应于r1、r2、r3、r4、r5类问题，其工件到达时间间隔分别为1、2、3、4、5；

在批处理设备的容量B=30，PSO算法中粒子个数m=80，迭代次数NC_max=80的参数下，所有算例运行100次，利用Matlab2011b实现。由于算例中数据均为随机产生，为防止个别极值的出现对运行结果产生影响，最终结果以除去10个最小值和10个最大之后的其余数值的平均值表示。文中不讨论工件尺寸sj、加工时间ptj，得到不同到达时间下调度时域周期长度T分别为50、100、150时不同工件数的加权完成时间和。

对五种常规调度介绍如下，后续对五种常规调度的调度结果与PSO算法下批调度模型优化后的调度结果进行比较。

1)先到先加工(FIFO)规则，调度时域内工件按到达时间rt非降生成排序，常用于调度车间的一般调度问题中；

2)基于优先权优先(PSF)规则，调度时域内工件按其权重weight非增生成排序，常用于工件含权重参数的批调度问题，但此调度规则容易造成热处理炉等批处理设备的空闲时间；

3)加权最小到达时间优先(WLAT)规则，调度时域内工件按其重要度与到达时间的比值weight/rt非增生成排序，是FIFO规则和PSF规则的折中，不会导致热处理炉产生大量的空闲等待时间；

4)加权最短加工时间优先(WSPT)规则，调度时域内工件按重要度与加工时间的比值weight/pt非增生成排序，在解决目标为加权完工时间和静态全局调度的问题中效果最佳；

5)最短加工时间优先(SPT)规则，能在解决大规模工件的静态调度问题中实现出很好的优化性能。

5.1.2 基于PSO算法的滚动时域批调度模型的有效性与适用性分析

图2中为r=0.1时的调度结果。首先，在不同工件数和调度周期下，基于PSO算法的滚动时域调度模型相对于其它五种常规调度规则的平均改进比最大值为24.99%，最小值为7.15%，体现了PSO算法对滚动时域策略下的批调度模型有较强的适用性；其次，调度周期T为50，SPT规则效果最佳；调度周期T为100、150时，WALT规则效果最佳。在相同工件数的情况下，随调度周期的增加，由于SPT规则未考虑工件权重信息，调度结果也随之增大。但调度周期的长短对FIFO、PSF、WLAT、WSPT四种规则的调度结果影响较小。工件密集到达，按照WLAT规则排序后不仅可保证较大权重的工件及早加工，而且批的开始加工时间较小。因此，WLAT规则在处理密集到达工件的调度时有较大优势。

图2 r=0.1时调度结果 图3 r=0.2时调度结果

图3为r=0.2时的调度结果。PSO算法下调度结果的平均改进比值在7.9%到31.78%间，FIFO规则明显优于WSPT规则，但WLAT规则效果仍是最好的。此外，随着调度周期变大，SPT、WSPT和PSF规则的调度结果也逐渐增大。

图4和图5分别为r=0.3、r=0.4时的调度结果。滚动时域批调度模型中PSO算法相对于常规调度规则的平均改进仍然可观。在所有算例中，五种简单调度规则中FIFO规则的调度优化效果相对最优，其次为WLAT规则，再次之为WSPT规则，PSF和SPT规则调度效果最差。相同工件数的算例中，除FIFO规则外，其它四种调度规则都是随时域周期的增大，调度结果增大。

图4 r=0.3时调度结果 图5 r=0.4时调度结果

图6 r=0.5时调度结果

图6为r=0.5时的调度结果。此时，与其它常规调度规则相比，FIFO规则仍表现出极好的性能，但PSO算法调度结果在各调度周期下相对于FIFO规则的优化效果则不明显。说明了PSO算法在处理工件分散到达的情况下优化效果不尽理想。导致这一现象的原因主要有两点：①工件到达时间间隔较长，各调度时域内到达的工件数量少，导致调度时域内待调度工件数量也较少，PSO算法的优化迭代性能得不到体现；②工件到达较为分散，导致整个调度过程产生较多的调度周期。尽管PSO算法调度过程中，各时域内都设定了惩罚函数以确保局部调度目标与全局目标相一致，但过多的局部调度仍然会对全局目标产生不小的影响。

综合图2到图6以及图7，可知：

1)除了在r=0.1，调度周期为T1、工件数分别为80和100的两个算例，PSO算法下批调度模型优化后的调度结果均优于常规调度规则，说明基于PSO算法的滚动时域批调度模型具有很好的调度优化效果。这两个算例中SPT规则较优的原因是由于工件到达时间间隔较短，且每个时域内需加工的批数又相对较少，造成工件在批处理车间的阻塞，导致在每个调度周期的决策时刻，可供调度的工件数目较多。此时，按照工件加工时间排序还会使得绝大部分时域内调度批数的增加，因而SPT规则的调度结果较理想。

2)FIFO、PSF、WLAT、WSPT、SPT五种常规调度规则中，随着工件到达时间的增加，FIFO规则的调度优化效果逐渐优于WLAT规则的调度效果，且调度周期的长短对FIFO规则影响较小，从而间接证明了FIFO规则在实际调度中作为最常用的调度规则有独有优势。

3)附录中的图5中，三条折线均为先升后降的走势，说明随到达时间参数r取值的增大，即工件到达由密集到分散时， PSO算法下滚动时域批调度模型的调度优化性能先上升后下降。其次，由折线的不同高度可知，随调度周期T的增大，模型及PSO算法的调度优化效果增强。这表明，PSO算法下滚动时域批调度模型在解决调度周期长的批调度问题中效果更佳，优势明显。

图7 到达参数、时域周期与平均改进比折线图

综上，当到达参数固定后，在调度周期较长(即T越大)的批调度问题中， PSO算法下滚动时域批调度模型的效果越好。考虑极限的情况，即当T→∞时，PSO算法可达到最优调度，此时的批调度策略为一次的全局静态调度，调度结果为滚动时域批调度问题的下界；当T→0时，PSO算法优化效果差，此时批调度方法为实时在线调度，调度结果为滚动时域批调度问题的上界。

6 结束语

设计了滚动时域调度策略，加入目标惩罚函数，得出PSO算法下各调度时域内的局部最优调度。仿真结果表明滚动时域调度策略下，PSO算法在解决工件密集到达以及调度周期较长的批调度问题时优化性能较好。同时，随着调度周期增多，惩罚函数越能影响调度效果。但调度时域内局部惩罚函数的设定并未有统一的标准，决策人员只能根据调度目标和实际调度情况进行调整。