活动执行时间可提前的多模式反应性项目调度优化

曹芳芳, 何正文, 王能民

(西安交通大学 管理学院,陕西 西安 710049; 过程控制与效率工程教育部重点实验室(西安交通大学),陕西 西安 710049)

0 引言

受不确定因素的干扰，如天气变化、原材料到达延期、合同期限变更等，项目的实际进度往往不能按照基准计划准确执行[1,2]，此时，需要对受影响的活动进行局部修复或重调度，以确保项目的顺利实施，该过程称为反应性项目调度[1]。反应性项目调度发生在项目执行中，通过对执行中断修复从而弥补了前摄性项目调度对不确定性的预判不足。

实际中，由于必需的原材料延迟送达、与分包商签订的固定协议或活动提早启动会对后续活动造成无法估量的损失等，使得活动不得早于基准时间启动，该调整规则称为“铁路调度(Railway Scheduling)”[3]。然而，在实际的某些情况下，该执行规则对开始时间的约束使其并不能适用于所有项目。与之相反的另外一种规则为“接力赛调度(Roadrunner scheduling)”，要求执行中活动只要满足执行的资源需求，可在其紧前活动结束后尽早启动[4]。对于该类项目，活动提前启动不仅不会对其后续活动造成较大影响，甚至可为后续不确定性较高的活动留出更多的时间缓冲；尤其对于关键链上的活动，在资源可用时应尽早启动，提高资源利用率的同时也保证了项目的按期交付或不至于延期太久，并可避免为了加速某些活动而投入额外费用[5]；另外，在项目执行中可以根据资源实际情况适时安排活动，减小因严苛的基准时间约束而带来过多的资源调配成本；因此，反应性调整过程中允许活动提早启动，利用紧前活动提前完成的优势加快项目进度，某种程度上降低后续活动与基准计划的偏差。

综上，围绕随机工期引起的中断，研究活动开始时间可提前的多模式反应性项目调度优化问题。论文后续，首先综述相关文献；其次构建优化模型；随后设计启发式算法；并通过一个案例说明；最后得出结论。

1 文献综述

不确定型项目调度已成为项目调度领域的一个重要研究方向。Herroelen和Leus[1]针对该研究问题提出了五种方法，其中反应性调度由于其重要的现实意义引起众多研究者的关注。Zhu等[6]将引起中断的不确定因素分为网络结构、活动及资源三类，其中针对不确定活动工期与资源可用量的研究较为普遍。

早期，Van de Vonder等[7]比较了随机工期下的多种反应性启发式算法。Haruhiko和Daisuke[8]引入“计划进度水平”指标来评估反应性计划的进展程度。Long和Ohsato[9]提出模糊关键链反应性调度方法，允许活动尽早启动，但因关注缓冲渗透水平及进度的控制，而忽略了活动开始时间的稳定性。卢睿和林瑛[10]设计基于迭代局部搜索算法来求解随机工期下的加权提前-拖期惩罚反应性问题。任世科等[11]在应急救援反应性研究中允许实际时间提前，将其表示为减少的相应损失。Van de Vonder等[12]针对随机工期反应性中断对比了现有的前摄性与反应性调度算法。Lambrechts等[13]对资源中断的单模式反应性问题设计了多种前摄性及反应性策略。张沙清等[14]研究多项目反应性问题设计了基于优化资源流约束的算法；随后又提出多项目预测-反应性调度算法[15]。Dhib等[16]研究多技能反应性调度问题。Chakrabortty等[17]设计了两种离散时间模型来处理资源中断反应性问题。Chand等[18]针对资源动态变化提出了多目标超启发式方法来解决“抢占-重复”与“抢占-继续”两类反应性中断问题。

以上针对不同中断类型提出了多种反应性策略，但集中于单模式情形，当活动具有多种模式时，增加反应性问题的复杂性[19]。例如Deblaere等[20]研究工期及资源随机下的多模式反应性调度问题，基于“铁路调度”设计精确和启发式算法。王艳婷等[21]研究随机工期中断的多模式前摄性与反应性权衡问题。李佳媛等[22]研究资源可用量不确定的多模式反应性项目调度问题。Chakrabortty等[23]设计了两种多模式反应性恢复方案来解决单个或一系列资源中断问题。

上述反应性研究大多集中于单模式，且研究问题大多基于“铁路调度”规则。而本文基于不同的现实情形，允许活动提前启动。据此，研究不确定工期下活动开始时间可提前的多模式反应性项目调度优化问题。

2 问题界定及模型构建

(1)

(5)

上述，式(1)最小化反应性总成本；式(2)将T时刻已开始活动的执行模式与开始时间初始化为基准计划对应值；式(3)为优先关系约束；式(4)任何执行时刻t正在进行活动Pt对可更新资源的需求总量不超过资源可用量；式(5)为决策变量的取值约束。上述，将已完成与正在进行的活动的开始时间及模式设置为与基准值；对UT的活动，可通过提前基准时间启动，来减小后续活动的开始时间偏差；另外通过选择合理的模式组合，达到降低更多开始时间偏差成本的目的。

需注意，项目实际中会发生多次中断，每次均会调用上述模型，并将新生成的ST赋值于基准进度计划SB，以供下次中断时调用。

3 禁忌搜索启发式算法设计

本文研究问题为多模式资源约束反应性项目调度向活动工期不确定情况的扩展，属于NP-hard[24]，选用禁忌搜索算法(TS)进行求解，且该算法已被众多学者采用[11,13,20～22]。

3.1 解的表示与解码

解的表示使用活动次序列表AL，模式转换列表ML和时间裕量列表SL来表示。

AL:列表{l1,l2,…,ln}定义n个实活动的优先次序，li为活动i对应的位置，决定活动i在反应性进度计划中的优先次序。

ML：列表{m1,m2,…,mn}定义了n个活动的执行模式，mi为活动i执行模式。

SL：{b1,b2,…,bn}定义了n个活动的时间裕量。bi为活动i开始时间之前添加的时间裕量，确保算法搜索能够覆盖整个解空间。

编码及解码过程用图1示例项目说明。示例项目包含7个活动，其中0和6是虚活动。有一种可更新资源，其可用量R1=3。模式数据标注在图中。图2是三个编码列表，例如AL中l3=5，表示活动3在计划安排中的优先次序为第5；ML中m4=2，表示活动4按照模式2执行；SL中的b3=1，表示在活动3前有1个单位时间裕量；最终，通过SSGS解码得到进度计划为SB=(0,0,0,4,2,4,7)。

图1 示例项目AoN网络图

图2 示例项目编码列表

3.2 初始解构造

禁忌搜索初始解(AL0,ML0,SL0)构造如下：

AL0:在满足优先关系的前提下按照wi降序排列，已开始的活动的优先次序不变。

ML0:i(i∈UT)为随机选择一种执行模式。

SL0:将活动i(i∈UT)的时间裕量设置为0。

3.3 邻点生成机理

当前解(AL1,ML1,SL1)的邻点解(AL2,ML2,SL2)由以下三个算子随机生成：

活动位置交换算子(AO)：不违背优先关系条件下，在UT中随机选择两个活动并交换位置，得到AL2；令ML2:=ML1，SL2:=SL1。

执行模式改变算子(MO)：随机选择一个活动，改变其模式，得到ML2；令AL2:=AL1，SL2:=SL1。

开始时间裕量算子(SO)：随机选择一个活动i(i∈UT)，保证bi≥0，随机变化一个单位，得到SL2；令AL2:=AL1，ML2:=ML1。

三个算子的的移动定义如下：

AO移动：(i,li)及(j,lj)表示两个需交换位置的活动的移动，其中li、lj为两个活动(i,j)交换前对应的位置，将二者加入禁忌列表。

3.4 禁忌列表及终止规则

禁忌搜索算法定义三个禁忌列表TLA，TLM和TLS，分别对应编码列表。禁忌列表的禁忌对象分别为3.3节中三个算子逆向移动。

禁忌列表应用“First-in-First-out”规则；每次从该列表底部将邻点解的逆向移动加入；因此，当禁忌列表排满时，最早从底部进入的元素将从列表顶部被移出。该列表中的元素在生成邻点时不允许使用，但当某元素对应的目标值最优时，禁忌激活，移出列表。禁忌列表长度通过实验法获得。当搜索次数达到上限时算法结束，并输出当前最好解。

3.5 算法搜索步骤

步骤1输入(AL0,ML0,SL0)及对应的LOSS0；清空禁忌列表TLA,TLM,TLS；算法迭代上限Nmax；令迭代次数iter=0；解的初始化。

步骤2随机选择一个算子，生成邻点(AL2,ML2,SL2)，计算LOSS2，判断该邻点的逆向移动是否在对应的禁忌列表TLA、TLM或TLS中，若在，则转步骤4；否则转至步骤3。

步骤3令(AL1,ML1,SL1):=(AL2,ML2,SL2)，LOSS1:=LOSS2；令iter:=iter+1；更新禁忌列表。若LOSS2

步骤4若LOSS2

步骤5若iter≥Nmax，到步骤6；否则转步骤2。

步骤6输出(AL*,ML*,SL*)和LOSS*。

图3 TS算法伪代码

4 案例分析

4.1 项目背景及数据提炼

FZDJ项目是XH有限公司的一个加工项目，项目历时30天。图4为该项目的AoN网络图，包含34个活动，其中活动0和33是虚活动。该项目单位时间内可安排的热工6人、铣工6人及其他工种8人。项目相关数据见表1。

表1 FZDJ项目不同模式下工期均值、标准差、资源需求及模式转换成本

项目基准计划SB=(0,0,8,18,22,45,22,22,26,22,30,30,39,78,91,96,124,22,25,82,43,45,91,52,53,78,99,141,169,58,187,194,200,201)，初始模式为1。活动实际工期为(0,8,10,4,16,5,8,8,6,4,27,12,7,8,12,40,35,6,21,14,8,8,15,12,20,10,5,35,38,39,7,6,1,0)，实际进度计划为(0,0,8,18,22,45,22,22,26,22,30,30,49,78,91,103,143,22,28,97,43,45,111,52,53,78,126,178,201,58,225,232,238,239)。实际执行239小时，约30天，超计划5天，总损失22930元，其中模式调整成本1000元，开始时间偏离成本21930元。

图4 FZDJ项目AoN网络图

4.2 求解结果讨论

4.2.1 满意解与实际结果对比

求解得到FZDJ项目反应性调整具体过程见表2。第1次到第7次反应性调整中，与基准时间不同的活动数量为8、4、2、1、1、1、1，开始时间偏差成本也从最初的2270元降低至80元，开始时间变化的活动数目及反应性成本均减小，但由于开始时间偏差权重及工期变化程差异，反应性成本会局部增大，比如第6、7次调整较前几次增大；同时项目的完工时间却维持不变，这是由于前7次调整使得工期变化带来的影响控制在一定范围之内。但第8次调整的活动数目较多，是由于优先关系中靠后的活动28的工期变化较大，使得后续活动均偏离基准时间，引起调整成本较高。另外，提前启动的活动为5、13、14、19，23，24，25，其中活动5、13提前启动是由于其后续活动14、15、16实际工期增大；活动14提前是由于该活动本身及后续活动15、16实际工期增大；活动19、21提前是因其紧后活动22实际工期增大；活动23，24，25提前是因其后续活动27、28实际工期增大；正是对活动的适时提前启动，使得后续活动的时间偏差量减小，从而降低项目反应性总成本。

述调整中模式改变的活动有：T=58，活动14、25的模式转换为2；T=91，活动15的模式转换为2，T=103，活动16的模式转换为2；T=141，活动27的模式转换为2；T=169，活动28的模式转换为2，上述活动因实际工期增大幅度较大，导致实际开始时间延后且对后续活动造成影响，因此通过转换模式可降低与基准时间偏差，也减小了对后续活动影响。

不进行模式调整得到的进度为(0,0,8,18,22,38,22,22,26,22,30,30,39,71,84,101,148,22,25,48,43,42,89,50,51,71,104,113,183,62,201,208,214,215)，反应性成本为13190元，较模式转换后的损失增大2800元。虽模式调整引起2100元的成本，但却降低开始时间偏差成本4900元，因此模式调整是有效的。

表2 FZDJ项目的反应性调整结果

从满意解与实际情况对比发现，满意解总工期比实际提前28小时；反应性总损失比实际减少12540元；实际执行通过“右移”规则处理中断，而本文通过提前活动时间及模式调整，减小了总成本，并缩短了项目总工期。

4.2.2 满意解与开始时间不可提前结果对比

为了进一步验证优化模型的有效性，将满意解与活动时间不可提前结果比较(表3)。

表3 活动开始时间可提前与不可提前的对比结果

活动开始时间不可提前得到的计划为(0,0,8,18,22,45,22,22,26,22,30,30,39,79,92,100,140,22,25,97,43,46,108,52,54,79,116,159,182,58,206,213,219,220)；活动执行模式为(1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,2,1,1,2,1,1,1,1,1,1,1,2,2,1,1,1,1,1)，其中活动14、16、19、27、28从模式1转换至模式2。从表3可知，后者的调整次数及模式转换活动数量均小于前者；由于后者按照“铁路调度”进行调整，未充分利用紧前活动提前启动预留的时间裕量，使得其调整效果较差，分别体现在：开始时间变化活动数与开始时间偏差量均较大；资源平均利用率为55.9%，较前者低5.3%；项目完工时间为220小时，比前者大9小时；反应性总成本为13870元，高于前者3480元。因此，活动时间不可提前的策略在实际中效果较差。

4.3 敏感性分析

(a)资源可用量变化对反应性成本的影响

(a)模式转换成本对模式转换的影响

5 结论

本文研究不确定活动工期下活动执行时间可提前的多模式反应性项目调度优化问题。得出结论：与案例实际结果及活动时间不可提前的反应性结果相比，通过本文方法得到的反应性成本及项目完工时间均较低，且资源利用率高。反应性成本及活动影响数目随着反项目推进呈减小趋势，但由于开始时间偏差权重及工期变动程度不同会有局部增大现象，同时在某些时刻项目完工时间保持不变；通过将工期增大较大的活动或其紧前活动适当提前，或通过调整模式可降低成本；反应性成本随资源可用量增加先下降后不变，与开始时间偏差权重及模式转换成本呈单调正相关关系，并随活动工期标准差的增大而上升；另外模式转换成本与开始时间偏差成本的数量关系对是否进行模式调整有一定的影响，当模式转换成本增加或开始时间偏差成本减小到一定程度时，无需模式转换。

本文允许活动可提前于基准时间启动，并通过合理调整活动模式，有效降低与基准计划的执行偏差。研究问题为在不确定环境下制定合理的反应性进度计划提供新思路。