基于里程碑支付的多模式多项目现金流平衡调度优化

何羽康, 贾 涛, 王能民

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

0 引言

对于现实中的绝大多数项目来说,承包商通常会发生两种形式的现金流:现金流出和现金流入。在项目的实施过程中,如果承包商的现金流出与流入能够保持平衡,那么就不会出现现金流缺口,项目便可以顺利地向前推进和实施;否则,在现金流出与流入之间即会产生缺口,这会给项目的平稳实施造成困难并引发额外的融资成本。因此,在项目的执行过程中,如何保持现金流出与流入的动态平衡,是承包商必须面对和解决的一个关键问题。

从本质上讲,项目的现金流出及流入均与项目调度紧密相关:一方面,现金流出的大小及时间取决于活动执行模式和开始时间的安排;另一方面,现金流入依据合同支付条件由项目的进展程度所决定。所以,通过对项目的合理调度可以有效地协调现金流出和流入,从而实现现金流的平衡。由此可见,以现金流平衡为目标的项目调度无疑是一个具有较高实用价值的研究问题。

考虑到里程碑支付是现实中的最为常见支付条件之一,本文研究基于里程碑支付的多模式多项目现金流平衡调度问题。在论文的后续部分,首先在第1节对相关文献进行综述;然后在第2节构建问题的优化模型并提炼模型性质;第3节设计问题求解的改进禁忌搜索启发式算法;第4节用一个实际案例对研究进行验证;最后,第5节给出研究结论并指出未来的研究方向。

1 文献综述

考虑现金流的项目调度问题属于项目调度研究领域的一个重要分支,该分支目前存在大量的研究成果。例如,LEYMAN和VANHOUCKE[1]在考虑资金约束下,构建了三种不同的净现值模型并设计了两种新的调度方法。崔南方等[2]提出了基于现金流关键度的分散缓冲算法,从而在现金流绩效指标上取得了更优的结果。在平衡各个时期活动的融资需求与资金供给的前提下,FATHI和AFSHAR[3]研究了考虑融资的多目标项目调度问题。郑维博等[4]针对多模式净现值最大化项目调度问题,设计了双层嵌套禁忌搜索启发式算法。AL-SHIHABI和ALDURGAM[5]借助不同的启发式信息开发了一种蚁群算法,用于求解基于融资的项目调度问题。

也有不少学者对多项目调度问题进行了研究,ELAZOUNI[6]针对基于融资的多项目调度问题提出了一种启发式算法,通过计算实验验证了算法的有效性。LIU和WANG[7]利用约束规划构建了净现值最大化多项目调度模型。EL-ABBASY等[8]同时考虑了工期、成本、融资等多个目标,提出了一种基于快速精英非支配排序的遗传算法。在考虑共享多技能人力资源前提下,于懿宁等[9]建立了局部调度及全局协调决策模型并设计了相应的求解算法。张静文等[10]针对分布式多项目调度问题,开发了一种自适应遗传算法。

关于现金流平衡项目调度问题,HE等[11]研究了承包商最大现金流缺口最小化单项目调度问题,开发了问题求解的变邻域搜索、禁忌搜索和两者混合的启发式求解算法。宁敏静等[12]将上述问题扩展到随机活动工期环境中,使得现金流均衡项目基准计划具有应对工期随机变化的能力。HE等[13]研究了可重复使用资源约束下的多项目现金流平衡调度问题,设计了问题求解的模拟退火和禁忌搜索算法。然而,需要特别强调的是,关于多模式多项目现金流平衡调度问题,据作者所知,迄今尚未有系统深入的研究。

2 优化模型构建及问题性质分析

2.1 优化模型构建

将H个项目执行过程中t时刻的现金流缺口定义为Gt,则由ACOt和ACIt便可计算出Gt:Gt=ACOt-ACIt。令Gmax为所有Gt中的最大值,则本文所研究问题即是如何合理地安排Π以最小化Gmax,其优化模型表述如下:

(1)

s.t.si+dimi≤sj,(i,j)∈Ah;h=1,2,…,H

(2)

snh≤Dh,h=1,2,…,H

(3)

k=1,2,…,Kh;h=1,2,…,H

(4)

(5)

mi和si为非负整数,i=0,1,…,nh;

h=1,2,…,H

(6)

其中,Ah表示项目h中各活动之间的逻辑关系集合。在上述优化模型中,目标函数式(1)最小化承包商最大现金流缺口;约束条件式(2)确保某一活动j的开始时间不早于其紧前活动i的完成时间;式(3)为项目的截止时间约束;式(4)计算项目实施过程中间支付的支付量;式(5)确定预付款及项目完成时刻的支付量;式(6)为决策变量的定义域约束。

2.2 问题性质分析

给定一个多项目进度计划Π,业主的支付pk的发生时间也随之确定。现假定在相邻两次支付所形成的时间区间(tk-1,tk)内,最晚开始活动的开始时间为silatest。那么,关于在区间(tk-1,tk)内的最大现金流缺口,存在如下性质1。

性质1给定某一多项目进度计划Π,在业主的相邻两次支付所形成的时间区间(tk-1,tk)内,承包商的最大现金流缺口一定发生在[silatest,tk)时段上。

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

多模式项目调度问题已被证明为NP-hard问题,考虑到本文所研究问题的复杂性,从实用角度出发,采用禁忌搜索算法求解上述优化模型。

3.1 解的表示及解码算法

用如下两个集合表示问题的解:

(1)活动执行模式集合EMS:该集合由H个项目的活动执行模式向量Mh构成:EMS=(M1,M2,…,MH),它决定了项目活动执行模式的安排。

(2)开始时间偏移集合TDS:该集合由H个项目的开始时间偏移向量TDh构成:DS=(TD1,TD2,…,TDH),其中,TDh=(Δ0,Δ1,…,Δnh),Δi∈[0,lsi-esi],esi和lsi分别是活动i由关键路径法所决定的最早和最晚开始时间。

令EAS为所有紧前活动都已安排了开始时间的活动所构成的集合,那么,给定一组(EMS,TDS),其对应的多项目进度计划安排Π可用下述解码算法生成:

步骤1令h:=1。

步骤2输入项目h的开始时间;令EAS:={0};根据EMS和TDS分别确定项目h中各活动的dim和Δi。

步骤3基于dimi及活动之间的优先关系,依次安排EAS中的活动尽可能早地开始,从而获得一个初始的si;进一步令si:=si+Δi。

步骤4将已安排了开始时间的活动移出EAS,同时将所有紧前活动都已安排了开始时间的活动移入EAS。检查EAS是否为空集,若是转步骤5;否则,转步骤3。

步骤5令h:=h+1。判断h>H是否成立,若成立转步骤6;否则,转步骤2。

步骤6由上述步骤所确定的活动开始时间si组成Sh,Sh与由EMS所决定的Mh构成项目h的进度计划安排(Mh,Sh),所有H个项目的进度计划安排共同组成Π={(M1,S1),(M2,S2),…,(MH,SH)}。输出多项目进度计划安排Π。

3.2 初始解构造方式及改进措施

问题的初始解(EMSstar,TDSstar)按下述步骤构造:

步骤1给定一个单项目h,将其所有活动均安排以成本最低的模式执行,由此得到一个Mh。检查在Mh下项目关键路径长度是否大于项目截止时间Dh。如果不大于Dh,则已获得一个工期可行且成本最低的Mh;否则,在关键路径上选择一个赶工成本增加最小的活动,将其执行模式变为工期较短的模式,重复该操作直至关键路径长度不超过Dh为止,由此得到一个可行的Mh。对于其他项目也按照上述方式构造相应的Mh,进而得到全部H个项目的活动执行模式向量,它们共同组成了EMSstar。

步骤2给定一个单项目h,根据EMSstar中的Mh确定活动的执行模式,由此得到各活动的工期。在不违反活动之间的逻辑关系和项目截止时间约束的前提下,安排里程碑活动尽早开始,非里程碑活动尽晚开始,从而生成一个Sh。根据Sh中各活动的开始时间确定其时间偏移Δi,由此获得TDh。对于其他项目也按照上述方式构造相应的TDh,进而得到全部H个项目的开始时间偏移向量,它们共同组成了TDSstar。

步骤3输出所得到的初始解(EMSstar,TDSstar)。

基于2.2中的性质2和3提出如下措施,对得到的初始解进行改进。在对(EMSstar,TDSstar)进行改进时,首先对其进行解码,获得对应的多项目进度计划Π;然后对Π执行如下操作后再进行编码,从而得到改进后的(EMSstar,TDSstar)。

步骤5输出改进后的多项目进度计划Π。

3.3 邻点生成机理及算法实施策略

给定问题的当前解(EMScurr,TDScurr),其邻点解(EMSneig,TDSneig)用如下两个算子随机生成:

(1)模式改变算子:从EMScurr中随机选择一个Mh,在选定的Mh中任选一个mi;在项目截止时间Dh的约束下,将所选mi随机地变为另一可行的值,由此得到一个新的EMScurr;该EMScurr与仍保持不变的TDScurr一起构成一个新解,记为(EMSneig,TDSneig)。

(2)偏移改变算子:从TDScurr中随机选择一个TDh,在选定的TDh中任选一个Δi;在项目截止时间约束下,将所选Δi随机地变为[0,lsi-esi]中的另一个值,由此得到一个新的TDScurr;该TDScurr与仍保持不变的EMScurr一起构成一个新解,记为(EMSneig,TDSneig)。在得到(EMSneig,TDSneig)后,采用3.2中所给出的措施对其进行改进。

考虑到在进行项目调度时,活动的开始时间必须在确定了执行模式之后才能安排,因此,将禁忌搜索算法设计为如下两个内外层相互嵌套的迭代搜索:内层在给定EMS下搜索满意的TDS并将结果反馈给外层,而外层在内层搜索返馈结果的基础上搜索满意的EMS,内外层的搜索结果共同构成问题的满意解。对于内外层搜索分别定义禁忌列表,用于存储搜索过程中的从当前解到邻点解的逆向移动。所有位于禁忌列表中的逆向移动都是被禁止的,但如果某个被禁忌的逆向移动能够生成比当前最好解还要好的邻点解时,其禁忌状态可以被激活,以便算法能够移动到该解上。在算法的搜索过程中,两个禁忌列表均采取“先进先出”的规则进行管理,同时,算法探测过的最好解被保存下来并不断更新。算法的停机准则定义为其运行时间,即事先设定好一个Timestop,当算法的运行时间达到Timestop时便停止搜索,并将保存的当前最好解输出为问题的满意解。

4 案例研究

4.1 案例数据

XAHT公司是一家中型民营建筑企业,2015年1月1日至2016年12月16日,该企业同时实施了两个项目(分别称为项目Ⅰ和项目Ⅱ)。项目活动具有两种执行模式(分别用执行模式1和2表示),活动挣值及在不同执行模式下的工期和成本均已知,其他数据如下:γ1=10%,γ2=5%;θ1=90%,θ2=90%;MAS1={1,2,4,7,8,11,17,19,21,24,26,28},MAS2={1,2,3,4,7,15,16,24}。为表述方便,将2015年1月1日上午8时记为0时刻,项目Ⅰ和项目Ⅱ分别于0和195时刻开始,它们的截止时间D1和D2分别为657和715时刻。

4.2 改进算法与原启发式算法的对比

为了评价算法的绩效并验证基于性质所提出的改进措施的效果,作者编写了两个版本的算法程序:原启发式算法TS和改进算法TSIM,前者没有添加改进措施,而后者使用了改进措施。两个算法在运行到相同的Timestop后停止,其内外层搜索的禁忌列表长度分别设置为6和5,当内层搜索探测的可行解数达到2800时跳出迭代循环。将Timestop设置为1,2,3,4,5,10,15,20,25,30秒等10个不同值计算问题的满意解,结果表明,当添加了改进措施之后,算法的搜索效率明显提升:在相同的停机准则下,改进算法满意解质量均不差于原启发式算法;改进算法10秒即可找到使Gmax最低的满意解,而原启发式算法则需25秒才能找到相同的满意解。

4.3 实际进度计划与满意进度计划的比较

项目Ⅰ和项目Ⅱ的实际进度计划Πreal和由算法计算得到的满意进度计划Πdesi如下:

Πreal={(M1,S1),(M2,S2)},其中,M1=(2,1,2,2,2,2,2,2,2,2,2,2,1,1,1,1,2,2,2,1,2,1,2,2,1,2,1,2,1,1,2),S1=(0,0,63,128,128,199,232,232,260,265,316,331,346,335,370,388,335,346,335,410,363,432,393,363,462,447,534,393,556,600,649),M2=(2,2,2,2,2,2,2,2,2,2,2,2,2,1,2,2,2,1,2,2,2,2,1,2,1,1,1,2,2),S2=(195,195,255, 313,313,362,407,411,362,407,463,467,457,553,495,514,578,578,514,525,547,609,601,574,624,624,655,666,696)。

Πdesi={(M1,S1),(M2,S2)},其中,M1=(2,1,2,2,2,2,2,1,2,1,2,2,1,1,1,1,2,2,2,1,2,1,2,2,1,2,1,2,1,1,2),S1=(0,0,63,128, 128,205,238,242,266,267,322,322,341,341,365,383,373,337,411,405,445,427,502,439,457,523,529,587,551,595,644),M2=(2,2,2,2,2,2,2,2,2,2,2,2,2,1,2,2,2,1,2,2,2,2,1,2,1,1,1,2,2);S2=(200,200,260,318,322,367,416,416,367,416,472,472,472,562,500,529,587,587,529,530,562,618,610,589,633,633,664,675,705)。

比较项目Ⅰ的实际进度计划和满意进度计划,可以发现二者的关键差异在于活动7和9执行模式的选择,以及活动5,7,9,13,16和18开始时间的安排,这些差异使得该单项目最大现金流缺口由3813万元上升到了4550.4万元;而在项目Ⅱ的两个进度计划中,关键差异为活动4和12开始时间的安排,它导致实际进度计划下的单项目最大现金流缺口上升了346.6%。如果将项目Ⅰ和Ⅱ综合到一起考虑,可以发现,在满意进度计划下二者匹配得更为合理,通过将项目Ⅱ的进度计划向后平移5个日历天,可使多项目最大现金流缺口由4368.9万元下降到4069.7万元。通过上述比较分析,可以得到如下管理启示:

管理启示1:以最大现金流缺口发生时段为参照,适当地延后该时段之前最后完成的里程碑活动的开始时间,可以使最大现金流缺口下降。

管理启示2:以最大现金流缺口发生时段为参照,适当地提前或者延后在该时段前后两次支付之间完成的非里程碑活动,可以减小最大现金流缺口。

管理启示3:给定多个单项目的满意进度计划,基于其现金流分布整体平移部分单项目进度计划,能够使现金流匹配更为合理并降低最大现金流缺口。

5 结论

论文研究了基于里程碑支付的多模式多项目现金流平衡调度问题。首先构建了问题的非线性整数规划优化模型,通过对模型的分析提炼出其三条性质;随后,针对问题的NP-hard属性,设计了内外层嵌套迭代的禁忌搜索启发式算法,基于问题性质提出算法的改进措施;最后,用一个实际案例对模型和算法进行了验证,通过多项目实际与满意进度计划的比较分析,揭示了二者的关键差异并得到如下管理启示:以最大现金流缺口发生时段为参照,适当延后该时段前最后完成的里程碑活动的完成时间,合理调整在该时段前后两次支付之间完成的非里程碑活动的开始时间,可使承包商的最大现金流缺口下降;给定多个单项目的满意进度计划,基于其现金流分布整体平移部分单项目进度计划,能实现多项目现金流的协调匹配并进一步减小最大现金流缺口。

需要指出的是,本文的研究没有考虑资源约束对项目进度计划安排的影响;而且,当现金流缺口出现时,也没有给出填补缺口的最佳融资方案。未来作者会把资源约束考虑在内,并同时研究如何合理地进行融资以弥补项目实施过程中的现金流缺口,由此推动该问题的研究向更加贴近现实情况的方向迈进。