干扰情形下重复性项目快速修复策略模型与算法

王浩, 张立辉, 周琳, 郭欣雨

(华北电力大学经济与管理学院, 北京 102206)

重复性项目是指所有活动在各个单位之间重复进行的项目,典型的重复性项目包括高层建筑、高速公路和跨海大桥的建设等。很多关于重复性项目调度的研究假设活动持续时间和材料供应是预先知道的并且不会改变[1-5]。然而,Viles 等[6]指出重复性项目是在动态环境中进行的复杂项目,通常会因为极端天气环境、不利地质条件、政策变化等干扰事件的影响导致项目成本增加,工期延长,甚至导致基准调度计划不可行。例如:中国的港珠澳大桥项目和美国的波士顿隧道项目均因为复杂的地质条件、恶劣的天气和资金缺口等干扰事件影响导致工期的延误和成本的超支。由于重复性项目是建筑行业项目中相当重要的一部分[7],因此有必要研究不确定环境中的重复性项目调度问题。

近年来,为了解决不确定环境下的项目调度问题,学者们提出了三种调度方法,分别为随机性调度方法、模糊性调度方法和鲁棒性调度方法。鲁棒性是指调度计划维持有效性,抵抗干扰事件的能力[8]。与随机性调度方法和模糊性调度方法相比,鲁棒性调度方法对于干扰事件采取了根本性的处理策略,因此该方法成为了解决不确定环境下项目调度问题最具潜力的方法[9]。鲁棒性调度方法按照应对干扰事件的处理方法不同又可细分为前摄性调度和反应性调度[9-10]。

前摄性调度是在项目计划阶段,通过插入时间缓冲的方式创建一个具有一定鲁棒性的基准调度计划。许多学者对前摄性调度进行了深入研究,但工程实际表明,即使基准调度计划具有非常高的鲁棒性,也不能完全规避项目执行过程中发生的干扰事件[10]。

反应性调度是在干扰事件发生后,对尚未开始的活动进行重新调整和优化,使反应性调度成本最小。目前反应性调度相关研究主要集中于一般性项目。Deblaere等[11]对多模式资源受限项目反应性调度问题进行研究,旨在资源或活动工期中断时获得最小化调度成本的反应性调度计划。Chakrabortty等[12]进一步考虑了优先关系变化、新活动增加等中断事件下的反应性调度问题。Elloumi等[13]针对多模式资源受限项目反应性调度问题提出了三种启发式算法进行求解。彭良武等[14]设计了两阶段多模式反应性调度模型,提高了反应性调度计划的鲁棒性。曹芳芳等[15]认为部分项目不需要满足铁路调度规则,活动执行时间可以提前,设计了一种多模式反应性调度模型,进一步降低了反应性调度成本。

与一般性项目相比,重复性项目由于多单元、工作连续性等特点,其反应性调度具备特殊性和复杂性:重复性项目活动受到干扰事件影响时,其紧前活动的部分单元可能尚未开始,因此也可以参与反应性调度;重复性项目可以通过打断工作连续性(间断)的方式有效缩短项目工期[16-18],因此除了现有研究常用的改变执行模式手段外,允许活动间断也可以作为一种重复性项目反应性调度手段。同时考虑改变执行模式和允许间断两种手段可以为项目管理者在制定反应性调度计划时提供更大的灵活性,进而可以得到反应性调度成本更低的调度计划。

重复性项目的反应性调度研究尚处于起步阶段,研究者较少。Sawomir等[19]通过加班和增加资源的方式加快施工,建立成本最小的反应性线性规划模型。Hegazy等[20]使用软逻辑和多模式手段修改调度计划,旨在以最小的成本满足项目截止日期约束,但该研究没有阐述重复性项目反应性调度模型。

上述反应性调度相关研究采用的均是完全重调度策略,即针对干扰事件,对尚未开始的所有活动进行全局优化调整。重调度策略能够实现反应性调度成本最低,但是对整个项目的调整范围较大,可能不被项目管理者接受。事实上,反应性调度还存在另外一种常被忽略的调整策略——快速修复策略。快速修复策略是指在干扰事件发生后,对尚未开始的活动进行局部优化,使扰动范围最小并适当兼顾减少反应性调度成本。快速修复策略在项目实践中非常实用。首先,由于需要调整的活动数量较少,因此对项目的扰动较小,这有利于降低管理和协调难度。尤其是在由多个分包商建造的项目中,快速修复策略可以帮助管理人员减少与其他分包商变更协议的次数;其次,调度计划的迅速恢复将有效减小项目里程碑延误的风险,这有利于承包商及时收到里程碑支付款项;最后,调整后的调度计划偏离基准调度计划的程度低,因此可以最大程度地保持基准调度计划考虑的项目目标(工期、鲁棒性和资源均衡等)。

综上所述,目前针对重复性项目反应性调度的研究极少,且尚未有人开展反应性调度快速修复策略的研究。由于关键路径法等传统调度方法在应对重复性项目调度问题存在诸多问题[4,21],现以在重复性项目中广泛使用的RSM(repetitive scheduling method)技术为工具,研究重复性项目快速修复调度问题。创新点主要体现在以下三个方面:①首次研究重复性项目快速修复策略,为项目管理者应对干扰事件提供多种修复范围下的反应性调度计划;②综合考虑多模式和间断两种反应性调度手段,构建了反应性调度成本-修复范围权衡优化模型;③针对问题模型,设计了一种基于强化学习的遗传算法进行求解。

1 模型构建

本文中研究的问题可界定如下:在重复性项目执行阶段,某一活动受到干扰事件影响而发生延误时,采用改变执行模式和允许间断的手段对基准调度计划进行调整和再次优化,以实现反应性调整范围和成本最小化的目标。

1.1 目标函数

在实际项目调度过程中,减少反应性调度成本是项目管理者最重视的目标之一,同时快速修复是管理者的现实需求。

本文提出的反应性调度优化模型的第一个目标函数是最小化反应性调度成本。表达式为

minCT=Cdc+Cmsdc+Cia+Cmsmc

(1)

式(1)中:CT为反应性调度成本,由偏差成本Cdc、模式更改带来的额外直接成本Cmsdc、项目工期变化而引起的额外间接成本Cia与更改活动执行模式和开始时间而引起的一次性额外调整成本Cmsmc组成。

(2)

(3)

式(3)中:Cmsdc为由于活动执行模式变更造成的额外直接成本;CD,ijk为活动i的第j个单元采用模式k的直接费用;xijk和xijk*为0-1变量,xijk=1为基准调度计划中活动i的第j个单元采用模式k,xijk*=1为反应性调度计划中活动i的第j个单元采用模式k*。

(4)

(5)

本文提出的优化模型的第二个目标函数是最小化反应性调度的快速修复范围,即最小化反应性调度更改开始时间和执行模式的活动数量。可表示为

(6)

1.2 约束条件

由于调整只能针对尚未开始的单元,因此在调整时刻t正在进行和已经完成的单元采用基准调度计划采用的执行模式。即

xijk*=xijk,ij∈Ft∪Pt

(7)

式(7)中:ij为活动i的第j个单元;Ft为调整时刻t已经完成单元的集合;Pt为调整时刻t正在进行的单元的集合。

同理,在调整时刻t正在进行和已经完成的单元的开始时间应该与基准调度计划保持一致。即

(8)

频繁改变执行模式和间断活动会产生以下负面影响:①增加管理复杂性;②对项目质量产生负面影响(每次更改执行模式和间断活动都会破坏已经建立的施工流程和质量控制措施,从而导致项目质量的降低);③会增加施工风险(每次更改都可能会导致不可预见的问题,例如材料供应或人员调整困难,这可能会给项目带来不必要的风险);④增加施工人员的不满,降低施工的效率。为了避免这些问题和简化计算,假定一个活动最多间断和改变执行模式一次,且间断和改变执行模式的单元位置应保持一致。

为确保每个活动最多更改其执行模式一次,设置执行模式更改次数约束为

(9)

式(9)中:Ut为调整时刻t尚未开始的单元的集合。

为限定一个活动最多间断一次,设置活动间断次数约束为

(10)

为确保间断和改变执行模式的单元位置保持一致,设置间断和执行模式更改位置约束为

(11)

式(11)中:M为足够大的正数。

为保证同一单元j,活动i的紧前活动h完成后,活动i才能开始,设置优先关系约束为

(12)

式(12)中:E为优先关系约束集合,(h,i)∈E表示活动h是活动i的紧前活动。

对于同一活动i,单元j+1只有在单元j完工后,单元j+1才能开始。设置逻辑关系约束为

(13)

2 基于强化学习的遗传算法

鉴于上述优化模型是一个混合整数非线性模型,本文设计基于强化学习的遗传算法对其进行求解。遗传算法(genetic algorithm,GA)是一种元启发式算法,模拟生物进化的自然选择过程来求解优化问题,已广泛应用于解决项目调度问题[5]。但是,GA的参数选取十分重要,将直接影响算法的求解效率。手动调整或随机猜测GA参数十分耗时,且当求解问题发生变化时,需要重新调整GA参数。在本问题模型中,干扰事件影响的单元位置以及单元工期延误的时间具有随机性,很难找出一个通用的GA参数来使得GA在所有干扰事件发生情况下均保持良好的求解效率。因此,本文中通过Q-learning强化学习算法对GA进行改进,以解决这一问题。Q-learning是一种强化学习算法,通过做出最大化长期奖励的决策来学习不同情景下的最优GA参数的选取,进而使GA在求解问题发生变化时也能继续表现良好,将Q-learning算法与GA算法结合的算法更适合求解本文所提模型。

针对问题的双目标属性,本文采用ε约束算法获得Pareto解[22]。ε约束算法的基本思想是将其中一个目标函数转化为约束,并通过逐步放松约束建立一系列单目标优化问题进行求解。由于修复范围的取值是离散的,因此本文将最小化修复范围转化为约束。

2.1 编码方案

遗传算法中最重要的一环是生成初始种群(随机解的集合),它以名为染色体的字符串形式编码,每个个体代表着一个解决方案。编码方案如图1所示,该图显示了一个只有4个活动的染色体。染色体的前四个基因表示采用的执行模式,后四个基因表示执行模式改变或活动间断的位置。

图1 染色体编码实例Fig.1 Chromosome coding example

2.2 算法流程

Step 1获取项目的基本数据,例如基准调度计划中活动各个单元的开始时间和执行模式,调整时刻,修复范围等

Step 2初始化种群和Q-table。

Step 3计算适应度函数。

Step 4计算种群多样性系数[23],确定种群状态(State)。公式为

(14)

式(14)中:dt为种群多样性系数,dt∈[0,1],dt越大,种群多样性越好;t为迭代次数;mean(ft)为第t次迭代中种群适应度函数的平均值;max(ft)为第t次迭代中种群适应度函数的最大值;p为种群大小;Di为种群中与第i个个体适应度相同个体的数目。

种群分为4种状态,dt∈[0,0.25]为状态1,dt∈(0.25,0.5]为状态2,dt∈(0.5,0.75]为状态3,dt∈(0.75,1]为状态4。

Step 5确定采取的动作。

根据种群状态和Q-table采用ε-greedy策略确定采取的动作。具体来说,如果一个随机数小于概率值ε∈[0,1],则随机选择一个动作,如果一个随机数大于ε∈[0,1],则选择Q-table中累计奖励最大的动作。

本文将交叉和变异概率视为Q-learning算法中的动作。交叉概率通常取值在[0.5,0.999]之间,变异概率通常取值在[0.001,0.2]之间,本文在[0.5,0.999]和[0.001,0.2]内分别均匀取6个交叉概率和5个变异概率进行组合作为算法可以选取的动作。

Step 6选择,交叉,变异操作。

选择操作是模拟自然选择中适者生存的过程。本文根据轮盘赌规则,基于个体适应度从当前种群中选择后代。

选择操作后,程序随机选择两个个体作为父代,使用双点交叉进行交叉操作。当随机数大于交叉概率时,子代与父代相同,反之子代是由父代在随机区间交换基因而产生的,如图2所示。

图2 交叉操作Fig.2 Crossover operation

变异操作则采用单点变异。只有在随机数小于突变概率时,染色体才会发生突变,突变位置是随机选择的。如图3所示。

图3 变异操作Fig.3 Mutation operation

Step 7计算动作奖励。

奖励设置是更新Q-table的依据,也是Q-leaning算法的关键一环。

种群多样性越高,找到最优解的可能性就越大。因此有必要对种群多样性进行奖励。计算公式为

(15)

算法迭代的目标是找到最优解。因此,如果在第t次迭代时种群的最优解[即max(ft)]得到了优化,应该奖励这个动作,反之,如果最优解没有得到优化,就应该惩罚这个动作。

(16)

如果第t次迭代时种群的平均适应度mean(ft)增加,说明整个种群已经得到了优化,应该给予奖励。需要注意的是,如果平均适应度没有变化,有非常大的概率是种群没有改变,因此应该给予较大的惩罚。计算公式为

(17)

(18)

Step 8更新Q-table。

Q-table的更新方式为

(19)

式(19)中:Qt,State,Action为第t次迭代时Q-table在状态和动作下的取值;α为衰减率;γ为学习率。

Step 9查看是否满足终止条件。如果已经满足终止条件,则算法终止,反之,则回到Step 3继续计算。

算法的流程图如图4所示。

图4 算法流程图Fig.4 Workflow of the algorithm

3 案例分析

3.1 结果对比

选取丹锡高速公路一段长约5 km的建设项目为例以验证本文反应性调度模型和算法的可行性。该重复性项目包括24 个活动,每个活动又分为5 个单元,每个单元长1 km。项目的截止日期是170 d,间接成本为每天31 600 元。表1列出了项目基础数据。在不更改执行模式和间断活动的情况下,以最小化建设总成本(包括直接成本和间接成本)为目标生成了基准调度计划,如图5所示。项目工期为170 d(满足工期要求),总建设成本为70 008 800 元人民币。在实际项目建设过程中,项目受到了干扰事件的影响。活动5的第2个单元的工期增加了2 d。

表1 项目基本数据Table 1 The basic data of the project

图5 初始调度计划RSM图Fig.5 RSM diagram for baseline schedule

右移策略作为最简单的项目反应性策略[8],是指不采取任何手段,将受到干扰事件影响的所有活动沿着时间轴向后推移的过程。本文分别使用右移策略和本文策略对该项目进行反应性调度,并进行结果对比分析。右移策略下的调度计划如图6所示,所有尚未开始施工的单元将延迟两天开始,项目的工期增加至172 d,总建设成本增加至75 015 940 元人民币,重新调度成本为5 007 140 元人民币。

图6 右移调度计划RSM图Fig.6 RSM diagram for right-shift schedule

本文模型得到的反应性调度成本-调整范围的Pareto曲线如图7所示,本文策略模型与右移策略模型的对比结果如表2所示。由结果可见,本文策略模型既能有效降低反应性调度成本,也能使项目迅速恢复至基准调度计划。

表2 不同策略对比结果Table 2 Comparison of different strategies

图7 帕累托曲线图Fig.7 Pareto curves

由图7可知,在一定修复范围内,本文策略得到的反应性调度成本随着修复范围的增加呈现下降趋势。可以解释如下:随着修复范围的增加,更多活动可以参与反应性调度,可以通过增加额外直接成本(或偏差成本)来使偏差成本(或额外直接成本)更大幅度降低,从而使反应性调度成本减少。

由表2可知,采用本文策略得到的反应性调度计划成本、工期和受影响的活动数目均不劣于右移策略得到的反应性调度计划。这很容易理解,本文策略可以更改活动的执行模式和允许间断,具备了更多应对干扰事件的手段,因此反应性调度成本和受影响的活动数目较小;其次,在一定修复范围内,项目恢复至基准调度计划的时间随着修复范围的增加呈现上升趋势。这是因为随着修复范围的增加,受影响的活动数目增加,导致恢复至基准调度计划的时间增加;最后,当修复范围增加至某一数值时,最小的反应性调度成本不再发生变化。这是因为调整活动的范围越广,偏离基准调度计划的活动就越多,将导致极高的偏差成本,此时其他成本的降低已无法弥补偏差成本的增加。

值得注意的是,表2中还存在以下两种现象。

(1)相比修复范围为1 个活动,修复范围为2 个活动时的反应性调度计划恢复至基准调度计划的时间更早。原因如下:修复范围约束为1 个活动时,反应性调度计划仅允许调整延误活动(活动5),由于其紧前活动(活动4)不受干扰,恢复至基准调度计划(活动5的完工时间)是第47 天;修复范围为2 个活动时,通过更改紧前活动(活动4)的执行模式,使活动4提前完工,进而导致受影响的最后一个活动可以更早的完成,因此可以较早的恢复至基准调度计划。

(2)当修复范围约束大于等于4 个活动时,额外直接成本为-507 224 元,这是因为活动5、活动7和活动8通过变更执行模式和允许间断等手段使得活动6部分单元可以采用直接成本更小但工期更长的执行模式,导致额外直接成本费用小于0。

为了验证所设计算法的有效性,将遗传算法(GA)应用于本算例进行测试对比。参数设置如下:种群大小设置为40,交叉和变异概率设置为0.8和0.1,学习率和衰减率设置为0.9和0.2,概率值ε设置为0.7,运行时间为10 s,取10次可行解。算法对比结果如表3所示。

表3 算法性能对比Table 3 Comparison of algorithm performance

根据对比结果可知,本文相同迭代时间下的平均调度成本,平均偏差,最大偏差均比遗传算法的求解结果好,这是因为Q-learning算法优化了遗传算法的参数选取,从而使算法收敛性能提高,说明了本文所设计的算法性能有效性。

3.2 蒙特卡洛模拟

为了进一步说明本文模型和算法的有效性和稳健性,采用蒙特卡洛模拟5 000 次干扰事件的发生。干扰事件的发生位置随机选择,单元工期的延误时间为1～3 d,修复范围约束为1～4 个活动。

对不同干扰事件下本文策略求得的最优反应性调度计划进行分析可知,本文策略得到的最优调度计划的工期仍不劣于右移策略;随着修复范围约束增加,本文策略仍存在反应性调度成本呈现下降趋势,恢复至基准调度计划的时间呈现上升趋势的特点。因此本文模型具有很好的有效性和稳健性。

算法运行时间设置为10 s,进行蒙特卡罗模拟5 000 次的算法对比结果如表4所示。

本文算法和遗传算法求解出可行解比例较低的原因主要是部分情况下修复范围过小,导致项目不存在满足修复范围约束的可行解。例如,活动16的第1个单元延误1 d,不存在修复范围为一个活动时的反应性调度计划。

由表4可知,本文算法在可行解中非支配解比例以及求得可行解比例均高于遗传算法,本文算法求得调度计划的调度成本比遗传算法求得调度计划的调度成本低,本文算法求解性能更好。

4 结论

本文研究了基于快速修复策略的重复性项目反应性调度问题。作者首先对研究的问题进行了界定,研究的目标分别为最小化反应性调度成本和最小化修复范围。在此基础上构建了反应性调度模型,针对该模型设计了一种Q-learning算法与遗传算法相结合的算法,并与单独的遗传算法进行对比。最后通过高速公路的案例验证本文所提模型和算法的有效性,并得出如下结论。

(1)通过反应性调度可以显著降低由干扰事件引起的调度成本,通常调度成本随着修复范围的增加而降低。

(2)当修复范围超过某个临界值时,增加修复范围并不会降低调度成本。

(3)Q-learning算法与遗传算法相结合的算法在求解该类问题上比遗传算法具有更好的求解效率。

本文可为项目管理者进行反应性调度时提供决策依据。