面向印制电路板钻孔任务动态调度的短视策略

鄢敏杰，王小明，朱松平，陈庆新，毛 宁

(广东工业大学 广东省计算机集成制造重点实验室，广东 广州 510006)

印制电路板(printed circuit board，PCB)是电子工业的重要部件之一，其加工工艺复杂，钻孔是其核心工序之一。在工程实际中，PCB钻孔任务通常是集中在每个班次开始的时段随机到达，不同任务之间在板数、孔数、孔径、板材等方面具有较大差异。每台钻孔机器是多轴同步运动，每次只能加工同一订单。由于单次叠板数量有限，一个订单往往无法在同台机器一次完成加工。为了缩短交货期，可能需要将一个订单拆分成多个子任务，由多台机器同时加工。此外，为了降低加工错误风险，在每台机器首次加工一个订单时需要进行首板加工与检测。上述任务特征和工艺要求导致PCB钻孔任务调度问题与传统机器调度问题不同，优化求解难度相对更大。当前企业主要是依据人工经验进行PCB钻孔任务调度，很难有效控制订单交货期和设备利用率。

PCB钻孔任务调度问题本质上属于具有任务可拆分特性的并行机调度问题(parallel machines scheduling problem, PMSP)，其在最小总拖期目标下为NP-难问题[1]。当前国内外学者都是在静态环境下研究这类问题，即假定所有任务在初始时刻均已到达，且资源和任务信息是确定的。任务可拆分PMSP相关研究可以按照决策目标进行分类。在最小化总拖期目标方面，Kim等[2]提出首先在不考虑拆分的情形下获得每台机器加工序列，接着对每台机器上的任务进行拆分和重排序。Shim等[3]提出了3种优势定理和多种下界计算方法，并据此构建了分支定界算法。Sariçiçek等[4]构建了一个基于序列位置变量的整数规划模型，并发现模拟退火(simulated annealing,SA)算法表现优于禁忌搜索。类似的，Kim等[5]也建立了相应的整数规划模型，并发现SA算法表现优于遗传算法。在最小化最大完工时间目标方面，Yalaoui等[6]、Nait等[7]、Wang等[8]分别提出了相应的启发式算法。Wang等[9]和Liu等[10]提出了考虑学习效应的优势定理，据此建立了基于序列位置变量的数学模型和分支定界算法。此外，Liang等[11]以总拖期和最大完工时间作为联合目标，发现变邻域搜索(variable neighborhood search, VNS)算法表现优于多重蚁群优化算法。

尽管目前尚未见到关于PCB钻孔任务动态调度的相关研究，但是国内外学者对其他类型的动态调度问题进行了一定研究，详见综述文献[12]。总体来说，现有动态调度方法可分为反应式、前摄式以及前摄−反应式3类[13]。反应式调度不预先生成固定的调度方案，而是实时地在局部作出决策。这类方法适用于应对不可预期事件，常采用启发式规则等实时性高的方法[14-15]。前摄式调度是指在制定计划时提前预测潜在随机干扰，从而令所得调度方案在执行过程中具有较高的鲁棒性，适用于应对可预知随机事件[16]。前摄−反应调度则是综合了前摄与反应两种方法的优点，一方面采用前摄方法制定出能够应对可预知随机事件的鲁棒调度方案，另一方面采用反应调度方法根据实时事件对调度方案进行修改[17]。此外，动态调度有事件驱动、定周期，以及两者混合3种再调度机制[18]。所谓事件驱动是指当出现使得系统状态发生改变的事件时就触发再调度，而定周期是指每隔一个周期调度一次。事件驱动机制能及时应对突发事件，定周期机制能提高生产稳定性。两者混合机制能够综合两者的优点，因而应用更为广泛[19]。

由于PCB钻孔任务动态到达过程为不可预期事件，任务必须及时处理以满足交货期要求，因此本文将采用基于事件驱动的反应式调度方法加以解决。

1 问题描述

本文研究的PCB钻孔任务动态调度问题由n个动态到达的任务和m台具有同等能力的机器构成，并考虑任务可拆分特性和因首板检测而导致的切换时间。假定任务j在时刻rj到达，其交货期dj、权重wj、 切换时间sj、 单位任务数uj，以及单位任务的工期pj均已知。所谓单位任务是指机器单次加工的任务，将一批在同一台机器上连续加工且属于相同任务的单位任务称为子任务。切换时间是指机器在切换加工不同子任务时，所需额外准备时间。任务j的完工时间cj是由其最晚完工子任务确定的，对应拖期为Tj=max(0,cj−dj)。

由于不同PCB企业在进行钻孔任务调度时可能采用不同的决策目标，因此本文将分别考虑如下5种典型的决策目标：最小化总拖期时间(total tardiness,TT)(如式(1)所示)，最小化总加权拖期时间total weighted tardiness,TWT)(如式(2)所示)，最小化最大完工时间(maximum completion time,Cmax)(如式(3)所示)，最小化总流水作业时间(total flowtime,TF)(如式(4)所示)，最小化总加权完工时间(total weighted completion time,TWC)(如式(5)所示)。

2 事件驱动的再调度方法

本文所研究的PCB钻孔任务动态调度问题，面临新任务到达和在制任务完工两类事件。当有新任务到达且存在空闲资源时，才会触发相应的调度方法来获取当前时刻的决策。为了既快速响应动态事件又保证调度优化效果，本节将描述优先规则和智能算法两类再调度方法。

2.1 优先规则

优先规则的优点是简单高效，在工程实际中应用非常广泛。目前，有大量面向各类生产调度和项目调度问题的优先规则，规则的表现与调度环境密切相关，没有哪一种规则在所有环境下都表现最优[20]。由于本文考虑了如式(1)～(5)所示5种决策目标，因此将从现有文献中选取适用于这些决策目标的规则。从文献[14]中选取8种规则，从文献[21]中选取了MDD和WMDD两种规则，另外还考虑了FCFS、WEDD和SPT3种规则。本文所选取的13种优先规则如表1所示。

表1 所选13种优先规则的形式化描述Table1 Formalization of selected 13 priority rules

优先规则只能实现对当前等待任务排序，在按照优先级顺序安排任务开工时还需要进一步考虑如何对其进行拆分的问题。为此，本文考虑一种能够最快完成开工任务的拆分策略，也就是将当前开工任务的所有单位任务尽可能均匀地安排至当前所有担 ⎿uj/mt」+1个 单位任务，其余空闲机器承担⎿uj/mt」个单位任务，其中⎿·」表示向下取整函数。空闲机器中。例如，假定t时刻有mt台空闲机器，当前具有最高优先级的任务j含有uj个单位任务，那么将有ujmodmt(表示uj除以mt的余数)台空闲机器承

2.2 智能算法

与优先规则通过简单排序和任务拆分进行决策不同，智能算法可完整表达任务开工方案，在算法停止时只需令每台空闲机器加工序列中的首个子任务开工。然而，在动态调度过程中的某些决策时刻可能等待任务数较少，此时若直接将式(1)～(5)所示决策目标作为智能算法的目标函数，会导致大量局部最优解。为此，本文提出将式(1)～(5)所示决策目标作为智能算法的第一目标，将当前参与调度的任务的最大完工时间或总切换时间最小作为智能算法的第二目标。经过这样处理之后，智能算法将以更贪婪的方式获得全局更优的调度方案。

2.2.1算法编码

优势定理1在最优调度方案中，同一台机器上最多存在一个属于同一任务的子任务。

证明见Shim等[3]提出的Proposition1、Kim等[5]提出的Property1以及Wang等[9]提出的Theorem2。

本文将基于该定理来构建相应的智能算法，提高其求解效率。需要强调的是，该定理在动态环境下并不能保证最优性，而是一种局部最优定理。在此基础上，本文参考Sariçiçek等[4]的SA算法编码方法，定义每台机器的子任务序列以及各子任务的单位任务数量。如图1所示，Jkl表 示在机器k的 第l个位置上加工的子任务，SJkl表 示子任务Jkl的单位任务数量，nk表 示在机器k上的子任务总数。该方法的优点是解码过程简单，很容易嵌入优势定理1以及计算目标函数值。

图1 算法编码规则Figure1 Algorithm coding rule

2.2.2邻域算子

本文采用智能算法常用的3种邻域算子来构造邻域解，即同台机器子任务交换、两台机器单位子任务插入和交换算子。与常规邻域算子不同之处在于，本文在邻域构造过程中始终遵循优势定理1。例如，若将机器k中的任务j的一个单位任务插入或者交换到机器k′上，那么将先判断机器k′上是否存在属于任务j的子任务，若存在就直接将该单位任务并入该子任务中，否则随机插入或者交换到机器k′。

2.2.3模拟退火与变邻域搜索

现有关于静态PCB钻孔任务调度的研究表明，SA算法表现优于禁忌搜索和遗传算法[4-5]，VNS算法表现优于多重蚁群算法[11]。因此，本文将直接采用SA算法和VNS算法进行再调度，并对比这两种算法在动态环境下的表现。SA算法的伪代码如图2所示，其中，X0为 初始解；X为当前解；E0为初始温度；E为当前温度；Ef为 截止温度；Y为邻域解；α为温度衰减系数；C(X)表 示X对应的目标函数值；Neighborhood(X)表示等概率选用3种邻域操作构造X的邻域解。

图2 SA算法伪代码Figure2 Pseudocode of SA algorithm

由于传统VNS需要耗费大量计算时间进行局部搜索，无法满足PCB钻孔任务快速调度需求，因此本文采用摒弃局部搜索的ReducedVNS(RVNS)。现有研究表明，RVNS在求解大规模问题时的优化效果与传统VNS相当，但是计算速度可提升十几倍[23]。RVNS伪代码如图3所示，其中，I为当前迭代次数；Imax为 最大迭代次数；q为 邻域算子索引；qmax为最大邻域算子索引(本文采用了3种邻域算子，故qmax=3)；Neighborhood(X,k)表示采用第q个邻域算子来构造X的邻域解。

图3 RVNS算法伪代码Figure3 Pseudocode of RVNS algorithm

3 计算实例

为了验证本文所提出的PCB钻孔任务动态调度短视策略的有效性，本节将参照企业实际数据生成测试算例，对比分析优先规则及不同版本的SA、VNS算法在不同环境下的优化效果和计算效率。所有算法采用C#语言编程实现，实验结果由计算程序在配置为2.20 GHz处理器和32.0 GB内存的服务器上运行所得。

3.1 算例数据

通过对广东某PCB企业调研，发现该企业共有24台钻孔机器，平均每天加工100个任务，每个任务的子任务数大致服从均匀分布U[1,9]。为了更全面地测试本文调度策略的有效性，进一步考虑两种工期和3种交货期环境。在短工期环境下，加工工时和切换时间分别服从分布U[5,60]和U[3,10]；在长工期环境下，加工工时和切换时间分别服从分布U[60,120]和U[3,20]。参照文献[2-4]中的实验设计，设定任务的交货期服从分布

其中，参数β为交货期紧急系数，在紧急、一般、宽松3种交货期环境下的分别取值为0.4、0.8和1.2。此外，设置任务的到达时间服从分布

其中参数a、b用于控制任务在早、中、晚3个班次集中到达的特性。对于任意任务，其到达时间分别有30%的概率落于(a,b)=(0,1/12)、(a,b) = (11/24,13/24)、 (a,b)=(11/12,1)对 应 的3个 区 间，另 有10%的概率落于 (a,b)=(0,1)对应的区间。在每种参数组合下随机生成25个算例，共有150个算例。

如2.2节所述，本文提出将当前参与调度的任务的最大完工时间或总切换时间最小作为SA和RVNS算法的第二目标。为了对比两种第二目标的优劣，本文将以最大完工时间最小为第二目标的SA和RVNS，标记为SA1和RVNS1，将以总切换时间最小作为第二目标的SA和RVNS，标记为SA2和RVNS2。此外，参照现有文献的调参结果来合理设置SA和RVNS算法的参数。具体来说，参照文献[5]设置SA算法参数E0= 300，Ef= 0.001，α=0.999，参照文献[11]设置VNS参数Imax=10 000。

3.2 评价指标

本文采用如式(6)所示的相对偏差百分比作为评价各调度方法优化效果的指标。

其中， O bjz表示方法z求解某个算例所得目标函数值； O bj∗表示所有方法求解该算例得到的最好目标函数值。

3.3 结果分析

在上述实验数据和评价指标设置下，采用13种优先规则和两种版本的SA及RVNS算法求解150个算例。总体来说，优先规则求解单个算例的速度非常快，其耗时可以忽略不计。SA和RVNS算法求解单个算例所需平均时间分别为25 s和49 s，但是单次决策所需耗时均在1 s以内。所有调度方法在决策效率方面，都能够满足企业实际再调度要求。各调度方法的优化效果对比结果如表2 ～ 4所示，具体分析如下。

表2 各方法在5种决策目标下的平均Dev%Table2 The average Dev% of each method under 5 decision objectives

表2展示了各调度方法在不同决策目标下的综合表现。可以看出，各优先规则的表现差异性较大，5种决策目标下表现最好的优先规则都不同。具体来说，在TT决策目标下综合表现最好的是MDD，而WMDD则在TWT决策目标下综合表现最优(COVERT和ATC表现与之非常接近)。值得一提的是，在Cmax决策目标下LPT表现远优于其他规则，优化效果普遍高出20%以上。这是由于LPT优先安排工作量大的任务，这些任务平摊到各台空闲机器上的单位任务数多，从而缩短了切换时间。但与此同时，LPT在其他决策目标下的表现都是最差的。SPT与LPT相反，优先安排工作量小的任务，这些任务的加工速度很快，因而在TF决策目标下表现最优。此外，在TWC决策目标下表现最好的是WSPT。上述结论与文献[14]中的结论基本一致。

相比之下，4种智能算法的优化效果在除Cmax之外的决策目标下平均提升了20%。对于SA和RVNS，可以看出RVNS在所有目标下都稍微优于SA，但是这种差别并不明显。对于SA和RVNS所用两种第二目标，可以看出在TT和TWT目标下采用最小化最大完工时间为第二目标更优(SA1和RVNS1分别优于SA2和RVNS2)，在Cmax目标下采用最小化总切换时间为第二目标更优，而两者在TF和TWC目标下则无显著区别。

表3和表4分别进一步展示了不同工期和不同交货期环境对各调度方法表现的影响。由表3可以看出，各调度方法的表现规律与表2所示总体规律相一致。工期规模增大对优先规则在TT和TWT目标下的表现未产生显著影响，但是显著提升了优先规则在其余目标(尤其是Cmax)下的表现。这是因为在本实验参数设置中，任务切换时间相对加工时间的占比会随着工期规模增大而下降，由此导致任务拆分策略对任务完工时间的影响下降。由表4可以看出，尽管各调度方法在不同交货期环境下的表现规律与表2所示总体规律也相一致，但是方法之间的差异有着显著的变化。具体来说，随着交货期由紧急到宽松，几种智能算法的表现较为稳定，优先规则之间的差距在缩小，但是优先规则与智能算法之间的差距则显著增加。相比较而言，交货期环境变化对TT和TWT目标下优先规则的表现影响大于在其他目标(尤其是Cmax)下的表现，这是因为这两个目标与交货期直接相关。在紧急交货期环境下大量任务将拖期，此时调度优化空间不大，因此部分优先规则与智能算法的差距并不大。同样道理，在非常宽松交货期环境下大多数任务将不会拖期，对应的调度优化空间也不大。然而，企业大多数时候是处于一般偏紧急的交货期环境，此时采用智能算法进行动态调度决策能有效减少拖期。

表3 各方法在2种工期规模和5种决策目标下的平均Dev%Table3 The average Dev% of each method under 2 duration size and 5 decision objectives

表4 各方法在3种交货期环境和5种决策目标下的平均Dev%Table4 The average Dev% of each method under 3 due date environments and 5 decision objectives

4 结束语

本文针对PCB钻孔任务动态调度问题，提出基于事件驱动的再调度短视策略，对比分析了优先规则与嵌入局部优势定理的SA和RVNS再调度算法在不同调度环境下的表现。计算实验结果表明，各优先规则在不同决策目标下的表现差异性较大。SA和RVNS算法总体表现显著更优和更稳定。RVNS优化效果略好于SA，但是SA计算效率相对高一倍；工期规模和交货期紧急程度变化对各调度方法的表现优劣未产生显著影响，仅在部分决策目标下呈现出方法间差距的缩小和增大。总体来说，本文所提出的智能算法较经典优先规则在优化效果方面平均提升20%以上，同时计算效率能够满足企业实际动态调度要求。

尽管本文发现基于SA和RVNS算法的再调度短视策略能够有效解决PCB钻孔任务动态调度问题，但是未来还有大量相关问题值得进一步研究。例如，调度方法应当适应更为复杂的实际问题，包括具有多种不同能力的钻孔机器，任务的工时难以估计以及存在一个工人看管多台机器等情形。此外，还可以在考虑可预测部分新任务到达时间的情形下，构建周期驱动和事件驱动相结合的再调度机制。