项目是一个由一系列带开始和结束时间、彼此协调且可控的任务组成的独特过程，以期在满足时间、成本和资源的约束下达成特定目标^[[1]]，唯一性和临时性是其主要特征。模具项目是典型的工程订货型(engineering to order, ETO)生产模式，每套模具产品的差异性较大且均为一次性生产，因此模具制造具备项目的两大特征，越来越多的模具企业采用项目方式进行模具生产管理。

然而，模具生产的一些特征使得模具项目管理难度非常大，企业普遍存在大量项目拖期的情况^[2-5]。模具生产主要特征包括：项目共享的关键资源数量有限；不同项目对应的交货期、订单价值、客户重要度等信息不同；新项目到达时间不可预测；项目之间进度相互关联；先验知识的缺乏使得难以准确预估项目任务实际所需工期；模具生产过程中频繁发生返修、设备故障、工程变更等突发事件。在上述因素影响下，企业往往难以制定项目计划，即使制定出项目计划也极容易在项目执行过程中受不确定性冲击而失效^[4-5]。在工程实际中，应对上述大量随机干扰的有效做法是进行项目动态调度，也即根据项目实际执行情况对项目计划进行修订或重新制定。那么，采用何种方法进行模具项目动态调度就变得尤为关键。

项目调度就是安排项目任务的开工顺序以及为每个任务分配对应的资源，其决定了能否有效达成项目目标，因而是项目管理的重要组成部分^[1]。根据前面对模具项目调度环境的简单描述可知，其本质上属于随机资源受限多项目调度问题(stochastic resource-constrained multi-project scheduling problem，SRCMPSP)。在过去十几年时间里，国内外相关领域学者对资源受限项目调度问题进行了广泛研究，提出了大量调度方法，相关研究可见Herroelen等^[6-8]、Van de Vonder等^[9]以及Hartmann等^[10]发表的综述文献。另外，国内学者王凌等^[11]以及方晨和王凌^[12]也对这类问题进行了比较全面的综述。总的来说，现有项目调度方法主要是面向确定性单项目问题，基本不适用于模具动态项目调度这种规模大且高度随机的问题。事实上，工程实际中越简单实用越可靠的方法才是更好的方法。优先规则虽然无法像精确方法或智能方法那样得到最优调度方案，但是足够简单高效，因此在工程实际中应用较多。国内外学者针对各类排序调度问题提出了大量优先规则，不同优先规则所对应的决策目标也往往不同，部分学者对现有规则进行了综述性总结^[13-14]和详细对比分析^[15]。大量实验结果表明，不同调度环境下各规则的表现不一样，尚没有哪一种规则能够在所有环境下都表现最优。此外，优先规则也被广泛应用于项目调度问题，Kolisch和Hartmann^[16]描述了基于优先规则的启发式算法；Browning和Yassine^[17]采用20种优先规则对确定性RCMPSP进行调度，实验结果表明一些之前被广泛倡导的规则在一些项目环境下表现较差，并指出决策者需要根据决策目标来选择对应的调度规则；Wang等^[18]针对不同规则在不同环境下表现优劣不同提出了基于马尔可夫决策过程理论和多规则组合的随机项目前摄调度算法，所得最优组合调度策略比单一规则策略结果更优。

综上所述，模具项目动态调度问题非常复杂，缺乏有效的求解方法来获得最优调度方案，但优先规则因其简单高效而被工程应用所接受。然而，目前尚没有见到关于优先规则在模具项目动态调度问题中的对比研究。为此，本文将选取15种适用于模具项目动态调度问题的经典优先规则，以随机生成的测试算例为实验数据设计对应的仿真实验，对比其在不同项目环境下的表现，从而为模具项目调度决策提供指导。

1 问题描述

尽管复杂的模具由成百上千零部件构成，但是企业自身仅设计加工少量诸如型腔，内模等关键部件，其余零部件则通过采购或外协获得。另外，模具关键部件对应的重要加工任务(受资源约束较大、工期较长)数比较少，主要为数控加工和电火花加工等。工程实际项目管理通常是重点关注这些关键定制零部件的重要任务，其对应的简化项目网络任务规模通常不大，且同一种模具产品类型的简化项目网络拓扑结构近似相同(具有相同的主要工艺路径)。

模具项目动态调度问题包含一个随时间动态变化的项目集合 φ t = { 1 , 2 , ... , l t } 和一个可更新资源集合 K = { 1 , 2 , ... , k } ，其中， l t 表示 t 时刻在制项目总数； k 表示可更新资源类型的数量。每一类资源的总量均有限，定义第 m ∈ K 种资源的总量为 M m 。假定所有项目具有相同的网络拓扑结构并考虑新项目随机到达，每个新项目 i ∈ φ t 的主要信息有到达时间 T i 、交货期 D i 、项目金额 v i 以及拖期惩罚系数 w i 。项目 i ∈ φ t 可用双代号网络(activity-on-node network，AON)图 G i = ( N i , A i ) 表示，其中， N i = { 0 , 1 , ... , n i } 表示任务集合(任务0和 n i 是2个虚拟任务节点，对应任务工期和资源需求都为0，分别代表项目 i 的开始和结束)， A i 表示任务之间的紧前约束关系集合。项目 i 的任务 j ∈ N i 对应工期为 d i j ，其在执行过程中需要占用 r i j m 个第 m ∈ K 类资源。本文不考虑任务抢占资源，也即只能将资源分配给当前等待列表中的任务。假设项目 i ∈ φ t 的完工时间为 F i ，则其对应的拖期天数为 [ F i − D i ] + ，拖期成本为 v i w i [ F i − D i ] + 。

除了新项目随机到达外，还通过随机任务工期来表达其他随机事件对项目的干扰。考虑到模具项目周期比较长(通常在30 d~80 d)，项目决策周期一般是以d为单位，因此假定所有任务工期是一个概率分布已知的离散随机变量。简而言之，模具项目动态调度问题是在考虑新项目随机到达和任务工期不确定的情况下，在满足任务紧前约束和资源约束的前提下，通过对项目资源进行协调决策来尽可能确保所有项目按期完工。

2 调度优先规则

在过去几十年里，国内外学者针对各类生产调度和项目调度问题提出了大量经典优先规则。总体来说，现有优先规则可以简单地划分为以下5类。

1) 包含加工时间的规则：最短加工时间(shor- test process time，SPT)，最长加工时间(longest pro- cess time，LPT)，加权最短加工时间(weighted shor- test process time，WSPT)等。

2) 包含交货期的规则：交货期优先(earliest due date，EDD)，改进交货期优先(modified due date，MDD)等。

3) 既不包含加工时间也不包含交货期的简单规则：先到先服务(first came first served，FCFS)，后到先服务(last came first served，LCFS)等。

4) 包含车间信息的规则：下一队列工作(work in next queue，WINQ) 等。

5) 包含2种及以上上述4类规则的规则：最大松弛(maximal slack，MaxSlk)，最小松弛(minimal slack，MinSlk)，显著拖期成本(apparent tardiness cost，ATC), 延期成本(cost over time，COVERT)等。

由于各模具项目的权重(项目金额和拖期惩罚系数的乘积)不同，因此若以项目群总拖期成本为模具项目动态调度决策目标，则本文所研究的问题可抽象为加权拖期优化问题。在早期研究中，COVERT规则是面向加权拖期问题应用最广泛和有效的规则^[19]。Russell等^[20]采用多种拖期指标对COVERT规则进行了测试，结果表明其在各种交货期紧急程度下都表现更优。在COVERT规则的基础上，Vepsa- laine和Morton^[21]首次提出了优先规则ATC。实验结果表明，ATC在求解基于任务工期的加权拖期问题时是一种与COVERT优化效果相当甚至最优的优先规则^[22]。Jensen等^[23]利用job-shop环境下具有不同客户优先级的调度问题对比分析了多种优先规则，结果表明除了传统的SPT规则表现较优之外，还发现以平均流水时间为评价指标时ATC规则在宽松交货期环境下表现更优，而COVERT规则在紧急交货期环境下的表现则更优。

综上分析，本文最终选取了如表1所示的15种优先规则，其中部分优先规则因所有项目网络拓扑结构相同而无法直接应用于模具项目动态调度问题，因而对其进行了一定修改，具体描述如下。

传统优先规则是采用 LF i j − t − d i j 来计算项目 i 任务 j 的松弛时间。由于本文所有模具项目网络拓扑结构相同，不同项目在同一任务节点的工期均值相同，这就使得传统MINSLK规则等价于EDD规则。为此，本文提出以项目松弛时间(project slack, PS)作为松弛类规则(MINSLK，MAXSLK，SRO)在各个任务节点的排序依据，并定义项目 i ∈ φ t 的松弛时间 PS i = D i − t − RT i ，其中， RT i 表示项目剩余工期(等于项目当前进度状态下剩余最长路径的长度)。此外，本文还将以项目剩余工期取代传统加工时间类规则(SPT，LPT，WSPT)中的任务工期。最后，当不同规则对应任务优先级相同时，将统一采用WPV作为第二排序规则。

其中，

LS i j 和 LF i j 分别表示项目 i 任务 j 的最晚开工和完工时间，均在不考虑资源约束的情况下根据项目交货期和任务紧前约束关系倒推计算得到；

T i j 是项目 i 任务 j 的到达时间，项目第一个任务节点的到达时间为项目到达时间，其余任务到达时间为最后一个紧前节点的完工时间；

cp i 表示任务工期取均值时项目 i 的关键路径长度；

RN i 表示项目 i 当前未开工任务总数；

p i 表示项目 i 下所有未开工任务的工期均值；

λ 为超前参数，文献^[21]指出在动态job-shop环境下取 λ = 3 比较合理；

W i q 为剩余项目 i 任务 q 的等待时间均值，文献^{[19, 21]}指出该值可近似看作任务工期均值乘以一个因子(通常取值为0.05)。

3 仿真实验

本节将首先随机生成多组对应不同项目环境的模具项目群算例，在此基础上进一步考虑任务工期服从不同分布来设计对应的仿真实验，通过收集和计算各个优先规则对应的评价指标值来判断其在不同项目环境下的表现优劣。仿真实验所用调度计算程序采用Visual C#编程实现，实验结果由该程序运行在一台操作系统为Windows 10，硬件配置为CPU 1.86 GHz，8.00 GB RAM的台式机上所得。

3.1 实验设计与实验数据

根据模具企业调研信息，本仿真实验假定所有项目具有如图1所示包含10个任务节点的项目网络结构。

图1项目网络中各任务节点的工期均值如表2所示，该项目网络的关键路径长度均值 L c p = 33 d。

基于上述项目网络，本文以一个中等规模的模具企业(平均在制项目数量为130个)为研究对象，假定该企业的制造系统是经过排队网理论优化设计的，各类资源的负荷均衡且在制项目数相对稳定。模具企业中的一类资源通常是指一个工作中心，而任务节点与工作中心之间往往是一一对应关系，且每个任务执行过程中仅需要1个资源(如1台设备等)。由于各资源负荷均衡，因此大致满足 M k 1 / d k 1 = M k 2 / d k 2 。本实验令第1个任务节点对应的资源数量 M 1 = 8 ，据此可以计算出其余资源的数量。此外，假定新的模具项目按照泊松过程随机到达，根据排队网理论中Little’s定律可以计算出新项目到达率近似为1.75。

为了使制造系统尽早处于稳态，本文将在初始时刻随机生成数量等于平均在制项目数130的初始项目，并大致令这些项目按照稳态模式处于不同进度状态，接着再从零时刻开始按照泊松过程随机生成每日新到达项目。初始项目的到达时间等于一个服从离散均匀分布 U { − 7 , − 1 } 的随机数减去进度倒推时间BT (该值等于当前进度对应已完工最长路径长度)，后续到达项目的到达时间则等于对应的系统时间。除项目到达时间 T 外，项目金额 v 和拖期惩罚系数 w 将按照连续均匀分布随机生成，而项目交货期 D 则由项目到达时间加上一个服从离散均匀分布的随机数，具体参数设置如表3所示。

在表3中，本文通过交货期紧急系数 α 来控制项目群的整体交货期紧急程度，并设置了 α = { 0.6 , 1.2 , 1.8 } 3种取值。对于每一种交货期紧急系数，首先随机生成5组初始项目群，接着每组初始项目群再分别随机生成5组不同的项目到达过程。换句话说，每种交货期紧急系数对应有25组不同的模具项目群算例，3种交货期紧急系数共有75组算例。

在上述随机生成的75组算例基础上，本仿真实验进一步考虑任务工期服从以下4种不同的概率分布：完全确定、泊松分布 Poi ( d ) 、离散正态分布 N ( d , d 2 / 16 ) 以及离散均匀分布 U { d − 2 , d + 2 } 。对于泊松分布和离散正态分布，本文限定任务工期随机变量必须大于等于1。3种交货期紧急系数与4种任务工期概率分布进行组合可得到12种不同的项目环境，本仿真实验将详细考察各优先规则在每种环境中的表现。

3.2 评价指标

模具项目动态调度的主要目标是减少拖期。单个项目的拖期指标包括项目拖期天数和项目拖期成本，对于整个项目群而言则还有拖期项目数(或者项目拖期率)这一指标。

由于项目群的拖期指标会随时间动态变化，因此本文将一方面考察各优先规则在项目群动态执行过程中的表现，另一方面还将对比项目群执行完成之后各规则对应的最终指标。在项目群动态执行过程中，将收集每一天项目群的累积拖期天数(cumulative tardiness days)，累积拖期成本(cumu- lative tardiness cost)以及累积拖期项目数(cumulative tardiness number) 3种样本，最后计算同一种环境下这3种指标每天的样本均值，以考察各优先规则对应指标在项目群动态执行过程中的变化趋势。另外，还将计算整个项目群完成之后的最终总拖期天数、最终总拖期成本以及最终总拖期项目数样本均值，将其与规则对应指标动态变化趋势作为综合评价各规则总体表现的标准。

3.3 实验结果与分析

在任务工期完全确定的情况下，利用前述15种优先规则对75个模具算例进行调度，统计得到如图2所示的不同交货期紧急系数下各规则对应3种指标的动态曲线，以及如表4所示的最终指标对比结果。

从图2和表4可以看出，3种指标动态变化趋势可分为线性增长和非线性增长两大类，同一交货期紧急系数下不同优先规则对应同一指标的曲线斜率有所不同，且规则之间的最终指标差距随着交货期紧急系数的增大而愈加明显。造成这一现象的因素有2个，第1个因素是项目环境，例如在交货期紧急环境(α=0.6)下，由于大量项目都将拖期，此时几乎所有规则对应的累积拖期项目数都呈线性增长，且最终拖期项目数相差不大；第2个因素则是各规则计算任务优先级的方法不同，关于这一因素对应的结论及其具体分析如下。

1) EDD、MDD以及MINSLK在所有交货期紧急程度下的拖期天数指标表现都是最优，原因在于这些规则都是以最短交货期作为项目开工的主要依据。规则LPT、MAXTWK对应3种指标均为非线性增长，其在前半阶段( t ≤ 150 )增长相对缓慢，但随后却急剧增长，最终拖期天数明显大于其他规则，而其他规则对应的最终拖期天数则相差不大。造成这种现象的原因在于LPT和MAXTWK都是优先执行新来的项目(因为这些项目对应的剩余项目工期或剩余工作量更大)而完全未考虑项目交货期，从而导致系统堆积的项目越来越多，拖期天数急剧增加。然而，LPT在最终拖期成本指标方面却比部分规则更优，这主要是因为LPT极容易导致大量项目齐头并进，在项目剩余工期相同的情况下会优先开工权重更大的项目，从而在一定程度上降低了拖期成本。

2) ATC在所有交货期紧急程度下的拖期成本指标表现相对更优且更稳定，COVERT规则显然只适用于交货期更紧急的环境，其在交货期宽松环境下甚至不如EDD等规则，这一结论与其他学者所得结论相一致。另外，SPT、WSPT、COVERT及WPV在交货期紧急环境下表现与ATC相似，原因在于这些规则都以项目权重作为主要决策依据，这说明在大量项目可能拖期的情况下优先选择权重大的项目是一种比较好的调度策略。另外，MDD在交货期宽松环境(α=1.2)下拖期成本指标稍微优于ATC，且EDD、MINSLK、CR、SRO等以最短交货期为主要决策依据的规则拖期成本指标也都表现不错，这说明在只有少数项目拖期的情况下优先选择交货期更短的项目是一种比较好的调度策略。

3) MAXSLK在交货期较为紧急(α=0.6和α=1.2)时的拖期项目数最小，而ATC则在交货期宽松(α=1.8)时的拖期项目数最小，其原因是MAXSLK令交货期更大的项目优先开工，在交货期紧急环境下大多数项目处于拖期边缘，此时让交货期更大的项目按期完工就能够有效降低项目拖期数。当交货期宽松时，可以看到ATC拖期天数比较大但是拖期项目数最小，意味着该规则通过权衡放弃了少数权重小的项目(因为这些项目即使拖期很多对应的拖期成本也很小)，从而保证了其余权重更大的项目不拖期。另外一个有意思的现象是，在交货期较为紧急环境下，MINSLK和MAXSLK这2个截然相反的规则分别在拖期天数和拖期项目数指标下表现最优。

简而言之，通过本组任务工期确定下的模具项目动态仿真调度实验发现，不同评价指标对应的最优规则不同，甚至相同评价指标下不同交货期紧急系数所对应的最优规则也不同。这充分表明模具企业需要根据其管理目标及项目所处环境来选择对应的优先规则进行调度决策。此外，在交货期紧急环境下，大多数规则对应的拖期天数和拖期项目数差别不大，但是拖期成本却有着天壤之别。这表明项目调度决策时综合考虑多种评价指标要比选择单一决策目标更加合理。

接着，假定所有任务工期均服从泊松分布，同样采用15种优先规则对75个模具算例进行仿真调度(每个规则对每个算例进行5 000次仿真)，得到如图3所示3种指标动态曲线以及如表5所示最终指标结果。

从图3可以看出，当任务工期服从泊松分布时各规则在不同交货期紧急程度下对应指标的动态变化规律与任务工期确定下所得结果非常相似。但是从表5能够找到一些不同之处，主要体现在以下2个方面。

首先，MDD在拖期天数指标方面的表现有所下降。造成这种现象的原因在于MDD采用任务工期均值来计算任务的优先级，当任务工期确定时任务实际工期就等于均值，此时能够更加准确地预估任务完工时间，而当任务工期随机时则会出现偏差。相比之下，MINSLK和CR预估项目剩余工期时多个随机任务工期叠加之后削弱了随机偏差，而EDD始终以项目交货期为决策依据则不受此偏差影响。这也是为什么任务工期确定时这几种规则拖期天数指标相同，而在任务工期随机时变为EDD最优，MINSLK和CR其次，MDD略差。

其次，COVERT与ATC在拖期成本指标方面的差距有所缩小。造成这个现象的原因是任务工期随机后部分工期实际取值大于均值，当大量任务工期取值超过均值时就演变成交货期紧急的环境，而COVERT规则在这种环境下的表现是比较好的。

此外，还分别考虑任务工期服从离散正态分布和离散均匀分布，同样采用15种优先规则对每个模具算例进行5 000次仿真调度。所得结果与图2和图3非常相似，受篇幅限制，本文仅通过表6和表7所示的最终指标对比结果来展示这两种分布所得结果与前述结果之间的细微差别。从表7可以看出，各规则在离散均匀分布与泊松分布下的表现几乎相同，且COVERT和ATC在拖期成本指标方面的差距更小。相比之下，表6所示结果差别比较明显，在离散正态分布下COVERT在拖期成本方面要好于ATC，且在交货期宽松环境下MDD等规则拖期项目数远小于ATC。由此可见，不同的任务工期分布对优先规则的优劣表现具有较大影响。

基于上述实验结果及相关分析，本文最终总结出不同模具项目环境下对应不同决策目标的最优规则，如表8所示。基于该结论，模具企业管理人员在工程实际中就可根据其所面对的项目环境以及管理决策目标，选择最合适的优先规则进行模具项目动态调度决策。

4 结束语

本文以模具项目群动态调度问题为研究对象，选取并通过大量仿真实验对比分析了15种适用于该问题的经典优先规则在不同项目环境下的优劣表现。实验结果表明，交货期紧急系数以及任务工期分布对于各规则在拖期成本和拖期项目数指标方面的影响较大，企业需要根据其所面对的项目环境以及管理决策目标合理地选择优先规则进行模具项目调度决策。一方面，本文总结出的不同环境不同决策目标对应最优规则表，对于模具项目管理人员在实际生产管理中合理选择优先规则进行动态调度决策具有重要指导意义。另一方面，在下一步研究工作中将基于本文所得研究结论，构建基于多规则组合的模具项目群动态高效控制策略。