集成时间缓冲与资源流的多技能项目鲁棒调度方法.pdf

第3 2卷 第5期 2 0 2 3年9月系 统 管 理 学 报J o u r n a l o f S y s t e m s&M a n a g e m e n tV o l.3 2 N o.5S e p.2 0 2 3 文章编号:1 0 0 5-2 5 4 2(2 0 2 3)0 5-0 9 1 6-1 1收稿日期:2 0 2 2-0 6-2 7 修订日期:2 0 2 2-1 0-3 1 基金项目:国家自然科学基金资助项目(7 1 9 7 1 0 9 4,7 1 7 0 1 0 6 7,7 2 0 7 1 0 7 5);广东省自然科学基金资助项目(2 0 2 1 A 1 5 1 5 1 1 0 9 6 9)作者简介:胡振涛(1 9 8 8-),男,博士生。研究方向为项目调度、组合优化。通信作者:崔南方(1 9 6 3-),男,博士,教授。E-m a i l:n f c u i m a i l.h u s t.e d u.c n 集成时间缓冲与资源流的多技能项目鲁棒调度方法 胡振涛1,崔南方1,胡雪君2,张 艳3(1.华中科技大学 管理学院,武汉 4 3 0 0 7 4;2.湖南大学 工商管理学院,长沙 4 1 0 0 8 2;3.东莞理工学院 经济与管理学院,广东 东莞 5 2 3 8 0 8)【摘要】在项目调度问题研究中,向调度计划中插入时间缓冲以及对资源流进行鲁棒优化调整是应对项目不确定性的主要手段。然而,现有研究多将两者分开探讨,且鲜有涉及多技能项目鲁棒调度方法的研究。基于此,在构建的多技能项目鲁棒调度模型的基础上,深入剖析了时间缓冲与资源流调整在调度计划鲁棒性方面的交互影响,并以此为理论基础,设计了集成时间缓冲与资源流的多技能项目鲁棒调度算法。算法以迭代交互的方式逐单位向调度计划中插入时间缓冲,并随之调整资源流,能在更大程度上利用两者对调度计划鲁棒性的交互提升效应。对单项目案例和案例集的实验结果表明:相比于分阶段的鲁棒优化方法,集成式的鲁棒优化算法能进一步提升调度计划的鲁棒性,降低项目的进度偏离成本。关键词:多技能项目;鲁棒项目调度;时间缓冲;资源流 中图分类号:F 2 2 4 文献标志码:A D O I:1 0.3 9 6 9/j.i s s n 1 0 0 5-2 5 4 2.2 0 2 3.0 5.0 0 5 I n t e g r a t e d T i m e-a n d R e s o u r c e-B a s e d R o b u s t S c h e d u l i n g A l g o r i t h m f o r M u l t i-S k i l l e d P r o j e c t s HU Z h e n t a o1,C U I N a n f a n g1,HU X u e j u n2,ZHANG Y a n3(1.S c h o o l o f M a n a g e m e n t,H u a z h o n g U n i v e r s i t y o f S c i e n c e a n d T e c h n o l o g y,Wu h a n 4 3 0 0 7 4,C h i n a;2.B u s i n e s s S c h o o l,H u n a n U n i v e r s i t y,C h a n g s h a 4 1 0 0 8 2,C h i n a;3.S c h o o l o f E c o n o m i c a n d M a n a g e m e n t,D o n g g u a n U n i v e r s i t y o f T e c h n o l o g y,D o n g g u a n 5 2 3 8 0 8,G u a n g d o n g,C h i n a)【A b s t r a c t】I n s e r t i n g t i m e b u f f e r i n t o p r o j e c t s c h e d u l e a n d a d j u s t i n g t h e r e s o u r c e f l o w a r e t h e m a i n m e t h o d s t o d e a l w i t h t h e u n c e r t a i n t y p r o j e c t i n t h e r e s e a r c h o f p r o j e c t s c h e d u l i n g p r o b l e m.H o w e v e r,m o s t o f t h e e x i s t i n g r e s e a r c h e s d i s c u s s e d t h e m s e p a r a t e l y a n d r a r e l y i n v o l v e d t h e r o b u s t s c h e d u l i n g m e t h o d f o r m u l t i-s k i l l e d p r o j e c t s.T h e r e f o r e,b a s e d o n t h e c o n s t r u c t i o n o f a r o b u s t s c h e d u l i n g m o d e l f o r m u l t i-s k i l l e d p r o j e c t s,t h i s p a p e r i n v e s t i g a t e d,i n d e t a i l,t h e i n t e r a c t i o n b e t w e e n t i m e b u f f e r s a n d r e s o u r c e f l o w o n t h e r o b u s t n e s s o f p r o j e c t s c h e d u l e.I t d e s i g n e d a r o b u s t s c h e d u l i n g a l g o r i t h m f o r m u l t i-s k i l l e d p r o j e c t t h a t i n t e g r a t e d t i m e b u f f e r s a n d r e s o u r c e f l o w,w h i c h i n s e r t s t i m e b u f f e r s i n t o p r o j e c t s c h e d u l e u n i t b y u n i t a n d a c c o r d i n g l y a d j u s t s t h e r e s o u r c e f l o w i n a n i t e r a t i v e a n d i n t e r a c t i v e w a y,m a k i n g f u l l u s e o f t h e i n t e r a c t i v e i m p r o v e m e n t o n t h e r o b u s t n e s s o f p r o j e c t s c h e d u l e.T h e e x p e r i m e n t s o n a s i n g l e-p r o j e c t i n s t a n c e a n d a p r o j e c t i n s t a n c e l i b r a r y s h o w t h a t c o m p a r e d w i t h s t a g e d r o b u s t o p t i m i z a t i o n m e t h o d s,t h e i n t e g r a t e d r o b u s t o p t i m i z a t i o n a l g o r i t h m c o u l d f u r t h e r i m p r o v e t h e r o b u s t n e s s o f p r o j e c t s c h e d u l e a n d r e d u c e t h e d e v i a t i o n c o s t o f p r o j e c t e x e c u t i o n.第5期胡振涛,等:集成时间缓冲与资源流的多技能项目鲁棒调度方法9 1 7 K e y w o r d s:m u l t i-s k i l l e d p r o j e c t;r o b u s t p r o j e c t s c h e d u l i n g;t i m e b u f f e r;r e s o u r c e f l o w 资源受限项目调度问题(R e s o u r c e C o n s t r a i n e d P r o j e c t S c h e d u l i n g P r o b l e m,R C P S P)主要研究内容是:在项目的活动及资源等约束下求解一个符合目标的调度计划,作为项目实施期进度安排的依据。其中,最常见的优化目标有工期1、成本2、净现值3和 资 源 均 衡4等。多 技 能 项 目 调 度 问 题(M u l t i-S k i l l e d P r o j e c t S c h e d u l i n g P r o b l e m,M S P S P)是R C P S P的一种,与传统R C P S P不同的是,其中的资源具备多技能,可以在不同活动中承担不同的任务,因此,其资源分配方式更加灵活,解空间更大,求解难度也更高5。然而,在项目实施过程中存在不确定因素,这些不确定因素可能会使项目中某些预设的参数发生变化,进一步导致项目的实际进度与调度计划之间产生偏差。这种进度上的偏离往往伴随着额外的成本,如财务成本、库存成本、组织协调成本等6,为应对这一问题,学者们提出了鲁棒项目调度方法。作为最有效也是成本最低的鲁棒项目调度方法之一,预应式鲁棒调度一直以来受到学者的广泛关注。其核心思想是在项目计划期便考虑项目实施期的不确定性,并在调度计划中加入鲁棒性措施,以生成一个具备抗干扰能力的调度计划。该调度计划应满足以下两点:符合项目的一切约束;当实施该调度计划时,即便发生随机事件的干扰,也具备一定的保持进度不变的能力。预应式鲁棒调度主要从时间和资源两个方面对调度计划进行优化。基于时间的鲁棒调度方法通过主动推迟调度计划中活动的开始时间,为其设置时间缓冲,为可能发生的不确定事件预留时间,其研究重点是缓冲位置和大小的计算。根据目标函数的不同,缓冲的设置方法也不同。G o l d r a t t7结合约束理 论 和 鲁 棒 项 目 调 度 提 出 了 关 键 链 缓 冲 管 理(C r i t i c a l C h a i n B u f f e r M a n a g e m e n t,C C/BM),向调度计划中插入时间缓冲以起到吸收不确定因素干扰的目的。刘士新等8根据缓冲在调度计划中位置的不同将之分为项目缓冲和接驳缓冲。缓冲大小的计算方式有剪贴-粘贴法和根方差法等9-1 0。然而,这种集中式的缓冲管理方法往往只考虑项目或活动延迟概率的大小,很少关注延迟所引起的损失情况。为此,有学者提出了分散式缓冲管理方法,如基于活动开始时间关键度(S t a r t i n g T i m e C r i t i c a l i t y,S T C)的时间缓冲设置方法1 1,综合考虑了活动的延期风险及活动的延迟损失,将时间缓冲分散地设置在项目各个活动前。然而,现有的集中式和分散式的时间缓冲管理方法都存在风险估计不准确、缓冲设置方式不合理等不足。在资源方面,主要是针对资源流的鲁棒优化,所谓资源流指的是资源在活动间的传递1 2。活动之间会因为共用资源而产生先后约束,通过调整资源流改变活动间的约束关系便是基于资源的鲁棒调度方法的主要研究内容。D e b l a e r e等1 3提出基于活动的短视优化法,优先从活动的紧前活动选择资源。梁洋洋等3从净现值的角度,以最小化惩罚成本为 目标提出了 资源流网络 的 优 化 算法。在多技能项目中,多技能资源的特性使活动间的资源流更加灵活多变,对资源流鲁棒优化方法也有更高的要求。然而,现有基于资源的鲁棒调度研究多是针对单技能资源,缺乏对多技能资源的关注。此外,时间缓冲与资源流调整之间存在交互影响,这是现有鲁棒项目调度研究领域少有涉及的。基于此,本文构建了多技能项目鲁棒调度问题优化模型,并深入剖析了时间缓冲与资源流调整之间的交互影响机制;提出了集成时间缓冲与资源流调整的多技能项目鲁棒调度算法,对一个单项目案例和一个项目案例库进行了大规模仿真实验以检验算法的性能。最后,本文总结了研究内容并提出了下一步的研究方向。1 问题建模及分析1.1 问题描述与建模 项目网络采用节点式表示,共包含n个活动节点,其中:起始节点1和终止节点n表示虚活动;活动之间存在工序约束。G=(V,E)表示项目网络,其中:V=1,2,i,j,n为活动集合;E为有向弧,表示活动的工序约束。Pi为与活动i有先后约束关系的前序活动的集合;活动i的时间为随机变量,其期望值为di。R=1,2,k,K为项目中的资源集合,资源总数量为K。项目涉及L种技能,以F=1,2,l,L表示。资源具备多技能,当资源k具备技能l时,R Fk l=1;否则,R Fk l=0。活动i对技能l的需求量用T Fi l表示。本文研究在活动时间不确定的环境下,以最小化项目进度偏离成本为目标,多技能项目的鲁棒调度方法。其前提条件是已有一个可行的基准调度计划,通过对该调度计划进行时间和资源上的调整以9 1 8 系 统 管 理 学 报第3 2卷达到提高其鲁棒性降低项目进度偏离成本的目的。多技能项目基准调度计划的制定已有较多的研究成果,如基于优先规则的并行调度1 4、遗传规划算法1 5以及基于动态资源权重的启发式算法1等。S Tb表示基准调度计划中各活动的开始时间,其中活动i的开始时间为S Tbi。xb表示基准调度计划中的资源分配方案,其中xbk l i表示资源k以技能l的形式被指派到活动i中。向S Tb中插入时间缓冲的过程即为基于时间的鲁棒优化过程,S Tr表示经过鲁棒优化后各活动的开始时间。调整xb的过程即为基于资源的鲁棒优化过程,xr表示经过鲁棒优化后的资源分配方案。在不确定环境下,项目有一个截止工期D,超过D的调度计划是不被接受的,即在向S Tb中插入缓冲时调度计划的最长工期为D。由于不确定因素的存在,在项目实施期活动的实际时间可能与其期望值不同,以di表示。活动的实际开始时间也不一定完全符合调度计划,以S Ti表示。项目活动的实际进度偏离调度计划时会产生重调度成本、额外库存成本等,项目实际工期超过D会产生逾期成本。以ci表示活动i的边际进度偏离成本,其中cn为项目逾期成本。本文所研究的问题以最小化项目进度偏离成本为目标构建模型,即:m i nTD C=ni=1S Ti-S Trici(1)s.t.S Tri+diS Trj,j,iPj(2)S Tri+diD,i(3)Kk=1xrk l iR Fk l=T Fi l,i,l(4)sti=1,S TritS Tri+di,i0,其他(5)ni=1Ll=1stixrk l i1,k,t(6)S Tri0,1,D,xrk l i0,1(7)k,l,i其中,式(1)表示目标函数,TD C表示整个项目的总进度偏离成本。在项目实施过程中,活动存在3种类型的进度偏离:开始时间偏离、持续时间偏离和结束时间偏离。其中,活动开始时间偏离会带来额外的物料库存成本、计划调整成本等。活动持续时间偏离为外生变量,不受系统影响且无法通过调度手段改变,因此不予考虑。而结束时间偏离所造成的影响一般可转化为其对后续活动开始时间上的影响。因此,本文所考虑的进度偏离成本中活动的偏离量以开始时间偏离量表示。式(2)表示项目的调度计划不可违背活动的先后关系约束。式(3)表示调度计划的工期不可超过项目截止工期。式(4)表示必须满足活动对技能的需求。式(5)中sti表示调度计划中在时刻t时活动i的状态,其中t表示时间。当sti=1时,表示活动i在时刻t处于进行中;当sti=0时,表示活动i在时刻t未开始或已完工。式(6)表示在任意时刻t,对于任意的资源k而言,使用它的活动不可多于一个,即限制了资源冲突。式(7)表示决策变量的可行域。1.2 时间缓冲与资源流调整的交互影响分析 首先引入项目案例(I),其项目网络及相关参数如图1(a)所示,如活动2的活动时间为1天,需要1单位技能F1、0单位F2及0单位F3。其中,有向实线表示活动的先后关系约束,虚线为图1(c)这一调度计划所对应的资源流。图1(b)为该项目的资源-技能情况。项目内共有3个资源3种技能,其中,资源R2为多技能资源,同时具备技能F1和F2。图1(c)为该项目一个工期最短的基准调度计划的甘特图。其中:横轴表示时间,纵轴表示资源;矩形中的数字表示对应的活动编号;括弧内表示对应资源在活动中所使用的技能,如资源R2在活动2中使用了技能F1;点线表示项目的截止工期,即D=9。图1(d)是实施图1(c)中调度计划时一个可能的实际进度,其中,阴影部分表示相应活动在实际进度中超出期望值的部分,如活动2的期望时间为1天,因为不确定因素拖期了1天,实际时间为2天。由图1(d)可以看出,由于活动2的拖期,活动3的 开 始 时 间 被 推 迟 了1天,即 当S Tb3=1,d2=2时,S T3=2,活动3的进度和计划之间出现了偏差。由项目网络图可知,活动2和3之间不存在工序上的约束关系,两者存在先后约束的原因在于共用同一资源R2。同理,活动8和6之间也是相同的情况。为了减少进度偏离,图2(a)展示了一个插入时间缓冲后的调度计划,各活动开始时间为S Tr,其中,黑色矩形表示活动前的时间缓冲。对比图2(a)和图1(d)可知,在设置时间缓冲后,即便活动2出现拖 期,活 动3也 会 依 照 调 度 计 划 开 始,即 当S Tr3=2,d2=2时,S T3=2。这便是时间缓冲对调度计划鲁棒性的影响机制。在资源流调整方面,由图2(c)可以看出,活动6和7原本使用的资源R2被替换为R3,这使得活动8和6之间不再有先后约束关系。对比图2(c)和图1(d)可知,当活动8拖期时,活动6将不会随之延期。这便是资 源 流 对 调 度 计 划 鲁 棒 性 的 影第5期胡振涛,等:集成时间缓冲与资源流的多技能项目鲁棒调度方法9 1 9 图1 项目案例(I)F i g.1 P r o j e c t i n s t a n c e(I)图2 调度计划的鲁棒优化F i g.2 R o b u s t o p t i m i z a t i o n o f s c h e d u l i n g p l a n响机制。传统的鲁棒项目调度方法将时间缓冲与资源流调整视为提高调度计划的两个方面,而未考虑两者的交互影响。图2(b)展示了先设置时间缓冲后调整资源的调度计划。由图2(b)可以看出,当活动2和4交换所使用的资源后,时间缓冲的情况发生了变化,活动3前的缓冲量减少,而活动5前的缓冲增加。这表明,资源流调整会影响时间缓冲的大小。进一步,图2(d)展示了先调整资源后设置时间缓冲的调度计划。由图2(d)可以看出,由于在调整资源时调度计划中没有足够的时间,导致活动2和4之间不能交换资源。而活动2和4之间通过交换资源可以删除活动2和3之间的约束,可能会提高调度计划的鲁棒性。这表明,时间缓冲会影响资源流调整的范围。综上所述,时间缓冲与资源流调整之间存在交互影响,在对调度计划进行鲁棒优化时,如果将两者分开进行,最终调度计划可能会存在不合理的部分,如图2(b)中时间缓冲被侵蚀,图2(d)中部分需调整的资源未调整。基于此,本文设计了集成时间缓冲与资源流的鲁棒调度方法。2 集成时间缓冲与资源流的鲁棒调度算法设计 通过前文分析可以看出,分阶段的鲁棒调度方法存在如下缺陷:调整资源流时会改变活动前时间缓冲的大小,导致某些活动前产生过多缓冲,而另一些更需要缓冲的活动前缓冲却被侵蚀;设置时间缓冲后活动间会产生更多的空闲时间,这为资源流提供了更多的调整空间,而阶段式的鲁棒调度方法并不能有效利用这部分优势。基于此,设计了迭代交互式的鲁棒调度方法,每次向调度计划中插入1单位的时间缓冲,而后进行资源流调整,这能有效利用时间缓冲所带来的调整空间,避免了上述第2个缺陷。此外,为避免第1个缺陷,设计了缓冲回退机制,每次资源流调整结束后,便重新评估调度计划,将活动前过多的缓冲回退。而由于整个算法是迭代交互进行的,缓冲被侵蚀的活动会在后续迭代过程中再次被设置缓冲。这种迭代交互式的鲁棒调度方法在求解过程中通过不断评估更新后的调度计划指导下一次鲁棒优化过程,综合考虑了时间缓冲和资源流对调度计划鲁棒9 2 0 系 统 管 理 学 报第3 2卷性的影响,也包括两者间的交互影响。算法伪代码如下所示:算法1 集成时间缓冲与资源流的鲁棒调度算法输入 S Tb,xb,D,V输出 S Tr,xr1.S TrS Tb,xrxb,T D C+2.通过M o n t e-C a r l o模拟计算各活动的期望进度偏离成本E(D Ci),计 算项 目总 期 望进 度 偏 离 成 本E(T D C)=ni=1E(D Ci)3.w h i l e E(T D C)TD C d o4.T D CE(T D C),V V5.w h i l e V d o6.j=a r g m a xiV E(D Ci)7.将活动j及其后续活动推迟1单位时间,得到新的调度计划S T r8.通过M o n t e-C a r l o模拟计算S T r的期望进度偏离成本E(D C i)及E(T D C)9.i f E(TD C)S Tj)cj(9)式中:A Pj为调度计划中活动j在资源上的前序活动集合;p(*)为*发生的概率;L P Li j为活动i、j间的最长路径。由式(9)评估调整资源前后调度计划的 TD C,若 TD C下降,则说明调整后鲁棒性增强,接受该次调整,否则拒绝调整。2.2.3 资源流鲁棒优化算法流程 基于上述分析,设计了资源流鲁棒优化算法,其伪代码如下所示:算法2 资源流鲁棒优化算法输入 xb,V,R输出 xr1.xrxb2.通过式(9)计算调度计划的估计进度偏离成本 T D C3.f o r i=1n d o4.f o r k=1K d o5.i f lFxk l i=1&资源k引起的活动约束为第3类约束 t h e n6.从R中选出与资源k交换后不产生时间冲突的资源集RAk7.从RAk中选出与资源k交换后能满足所交换活动技能需求的资源集合Rak8.T D C s,X 9.f o r z=1Rak d o1 0.kzRak中的第z个资源1 1.交换kz与k得到新的资源方案xrz,计算其估计进度偏离成本 T D Cz1 2.i f 交换后新增的活动约束为第1类约束 t h e n1 3.xrxrz,T D C TD Cz;b r e a k1 4.e l s e i f 交换后新增的活动约束为第2类约束 t h e n1 5.xrxrz,T D C TD Cz;b r e a k1 6.e l s e1 7.XXxrz,T D C s TD C sT D Cz1 8.e n d i f1 9.e n d f o r2 0.i f m i n TD C s T D C t h e n2 1.z=a r g m i n T D C s2 2.xrX(z),TD C TD C s(z)2 3.e n d i f2 4.e n d i f2 5.e n d f o r2 6.e n d f o r2 7.r e t u r n xr在算法2第7行,需要判断交换后的资源能否满足所交换活动的技能需求。在传统的单技能项目中,这种判断是简单直接的,只需要对比所交换的资源两者是否是同类资源即可。然而,在多技能项目中,并不能通过简单对比得出结论。这是由于资源具备多技能,即便交换的两者不是同类资源,也可能会存在以下情况:通过调整其他资源在活动中担任的技能,使交换后的资源组合能满足活动的技能需求。也即,两个资源能否交换,不仅取决于其自身的技能禀赋,还受到对应活动中其他资源的影响。由此,这一问题转化为:交换后各自活动所使用的资源组合能否满足相应活动的技能需求。设交换后活动i的资源组合为Ri,由于在同一时刻每个资源只能被使用一次,尽管资源具备多技能,这些技能也是互斥的,故有以下约束:lFxk l i1,kRi(1 0)kRixk l iT Fi l,l(1 1)xk l i0,1,l(1 2)以xk l i为未知数,只需要判断方程组式(1 0)(1 2)是否有解,即可判断当前资源组合Ri能否满足活动i的技能需求。然而,进一步分析可以看出,方程组式(1 0)(1 2)是0-1型线性整数规划问题,属于N P难问题,一定规模时难以求解。针对该问题,提出以下技能归并法予以解决。2.2.4 技能归并法 技能归并法首先将Ri的技能9 2 2 系 统 管 理 学 报第3 2卷视作技能供给,将活动i的需求视作技能需求,通过对不同数量的技能合并,对比供给与需求的大小。若在任意组合下供给均不小于需求,则Ri可满足活动i,以F S B=1表示;否则,F S B=0。算法伪代码如下所示:算法3 技能归并法输入 i,T Fi l,Ri输出 F S B1.F S B12.f o r z=1L d o3.S Czs czyy=1,2,Lz ,其中,s czy表示从集合1,2,L 中取出z个元素的组合,索引y用于标记每个组合在集合S Cz里的位置4.f o r y=1Lz d o5.S U P P L Yzk kRi,ls czyR Fk l0 6.D EMAN Dzls czyT Fi l7.i f S U P P L Yz D EMAN Dz t h e n8.F S B0;r e t u r n9.e n d i f1 0.e n d f o r1 1.e n d f o r1 2.r e t u r n F S B算法3第3行列出了要归并的z个技能的所有组合,第5第9行检验归并后的技能能否被当前资源满足,其中,S U P P L Yz和D EMAN Dz分别为技能归并后的资源供给数量和活动需求数量。在检验过程中,一旦出现供给数量不足,则立刻跳出所有循环,F S B=0;若能通过所有组合的检验,则F S B=1。由算法3可以看出,技能归并法的最坏时间复杂度为:oLz=1Lz =o(2L)。在求解该问题时,胡振涛等1构建了二分图模型,并以H u n g a r i a n算法求解1 6,其时间复杂度为o lFT Fi l+Ri 3。一般情况下,项目中技能的数量远少于资源的数量,L的值远小于lFT Fi l+Ri。此外,在求解过程中,若资源不足以满足活动的技能需求,算法3会在检验的中途跳出,大幅缩短了运行时间。因此,尽管技能归并法为指数级的时间复杂度,但一般情况下其求解速度远高于H u n g a r i a n算法。2.3 缓冲回退过程 为解决资源调整后的缓冲效用变化问题,设计了缓冲回退过程。在每次资源流调整后,判断各活动前的缓冲量,若活动前存在缓冲,则减少其1单位的缓冲,并评估新调度计划的期望进度偏离成本;若能降低成本,则接受该次回退。算法伪代码如下所示:算法4 缓冲回退过程输入 S Tr,V,E(T D C)输出 S Tr1.f o r j=1n d o2.i f m a xiPjA Pj(S Tri+di)S Trj t h e n3.将活动j提前1单位时间开始,得到新的活动开始时间S T r4.通过M o n t e-C a r l o模拟计算S T r的期望总进度偏离成本E(T D C)5.i f E(TD C)E(T D C)t h e n6.S TrS T r,E(TD C)E(TD C)7.e n d i f8.e n d i f9.e n d f o r1 0.r e t u r n S Tr3 实验设计及结果分析 为验证本文提出的算法,设计了单项目案例实验和 项 目 案 例 集 实 验。相 关 程 序 使 用M a t l a b R 2 0 1 7 a编写,测试平台为W i n d o w s 1 0操作系统,处理器 为I n t e l(R)C o r e(TM)i 7-6 7 0 0 C P U 3.4 0 GH z。3.1 单项目案例实验3.1.1 实验设计 为了分析集成式鲁棒项目调度与传统鲁棒项目调度的不同,以前文中的项目案例(I)为实验对象,项目的截止工期D=9,各活动的边际进度偏离成本为0,2,2,1,0.5,1,2,2,1 0,活动时间服从均值为di、标准差为的对数正态分布,考虑了低、中、高3种不确定程度,相应地,0.3,0.6,0.9。在算法参数方面,风险评估时的模拟次数Ns i m=1 0 0 0;在仿真模拟方面,对每个环境下的调度计划进行1 0万次模拟,以保证结果的置信度。3.1.2 结果分析 表1列出了基准调度计划(B S)、先插入时间缓冲后调整资源流的调度计划(B R)、先调整资源流后插入时间缓冲的调度计划(R B)以及采用集成式鲁棒优化算法求解调度计划(I B R)在不同不确定程度下仿真模拟的进度偏离成本。由表1可见,在不同不确定程度下,集成式的鲁棒优化算法都优于其他算法。为展示算法的优化过程,图3展示了随着算法运行调度计划的变化情况。第5期胡振涛,等:集成时间缓冲与资源流的多技能项目鲁棒调度方法9 2 3 表1 不同不确定水平下各调度计划的总期望进度偏离成本T a b.1 T o t a l e x p e c t e d d e v i a t i o n c o s t s u n d e r d i f f e r e n t l e v e l s o f u n c e r t a i n t yB SB RR BI B R=0.32.2 30.3 80.8 20.1 1=0.67.9 05.2 45.3 53.0 7=0.91 8.0 21 4.7 21 3.7 11 0.8 8其中,图3(a)3(b)为活动5插入缓冲,图3(b)3(c)调整活动6和7的资源流,图3(c)3(d)为活动3插入缓冲,图3(d)3(e)调整活动2和4的资源流,图3(e)3(f)回退活动5前1单位的缓冲,剩余均为插入缓冲。由调度计划的变化过程可以看出,算法在优化过程中能根据时间缓冲与资源流的交互影响不断调整缓冲大小和资源流向,明显优于图2中分阶段式的鲁棒优化方法。图3 集成时间缓冲与资源流的鲁棒优化过程F i g.3 R o b u s t o p t i m i z a t i o n p r o c e s s o f i n t e g r a t i n g t i m e b u f f e r s w i t h r e s o u r c e f l o w3.2 项目案例集实验3.2.1 实验设计 在实验对象方面,采用W a n g等1 7所设计的多技能项目案例集,选择其中的3 6 0个项目案例,每个项目案例包含3 2个活动。项目特征参数有3个:网络复杂度(N C)、需求因素(R F)和技能 水 平(S L),参 数 含 义 参 考W a n g等1 7和C o r r e i a等5的研究。其中:N C1.5,1.8,2.1,R F0.2 5,0.5,0.7 5,1.0,S L0.4,0.6,0.8。因此,共有3 6种不同的参数组合,每个参数组合下包含1 0个项目案例。项目中活动的边际进度偏离成本由0,1 0 随机生成,即ci0,1 0,结束节点的边际进度偏离成本cn=iV1 0cin,也表示项目的边际逾期成本。为对比算法在不同环境下的表现,考虑了项目的工期宽松度及活动的不确定程度。用项目的截止日期与基准调度计划项目工期的比值作为衡量工期宽松度的指标,即=D/S Tbn,其中,S Tbn为基准调度计划中结束节点活动n的开始时间,它等于基准调度计划的项目工期。工期宽松度分为低、中、高3档,1.1,1.3,1.5。项目的活动时间服从对数正态分布,其均值等于项目案例库的预置时间,不确定程度用分布函数的标准差衡量,也分为低、中、高3档,0.3,0.6,0.9。在算法方面,基准调度计划的获取参考胡振涛等1的研究,鲁棒优化算法对比了先插入时间缓冲后调整资源流(B R)、先调整资源流后插入时间缓冲(R B)以 及 本 文 所 提 出 的 集 成 式 鲁 棒 优 化 算 法(I B R),其中,本文算法中风险评估时的模拟次数Ns i m=1 0 0 0。在仿真模拟方面,对每个环境下的调度计划进行1 0万次模拟。3.2.2 结果分析 表2列出了3 6 0个项目案例在不同工期宽松度和不确定程度下,通过不同算法所求解的调度计划,最后仿真得到的平均进度偏离成本。首先分析不确定程度对项目进度的影响。可以看出,随着不确定程度的增大,无论以何种算法求解,项目的进度偏离成本都在增大。这是因为不确定风险水平越高,项目的活动时间随机性也就越大,对调度计划的干扰也更强,即便鲁棒优化策略也不能完全抵消这种干扰。其次分析工期宽松度的影响。随着工期变宽松,调度计划中可设置的时间缓冲量增多,资源流调整的空间也随之增大,项目鲁棒性增强,进度偏离成本降低。最后分析不同算法的求解性能。两种分阶段的鲁棒优化方法并无明显差别,相较之下,本文所设计的集成时间缓冲和资源流的鲁棒调度算法具有明显优势,且在任何工期宽松度和不确定程度下均优于分阶段的算法。9 2 4 系 统 管 理 学 报第3 2卷表2 不同工期宽松度及不确定程度下各算法求解的期望进度偏离成本T a b.2 E x p e c t e d d e v i a t i o n c o s t s u n d e r d i f f e r e n t s l a c k s a n d u n c e r t a i n t i e s s o l v e d b y d i f f e r e n t a l g o r i t h m s=0.3=0.6=0.9B RR BI B RB RR BI B RB RR BI B R=1.15 5 5.2 75 5 6.0 14 6 5.7 31 7 9 1.5 81 7 9 0.7 91 6 0 6.2 63 2 7 1.8 23 2 7 0.6 73 0 1 7.1 6=1.31 4 3.2 61 4 1.5 41 1 6.0 21 0 7 8.7 81 0 7 8.9 59 4 6.5 32 6 3 0.8 72 6 3 3.9 22 4 0 1.9 3=1.54 7.7 54 6.9 43 5.2 46 0 9.4 96 1 0.2 75 3 1.1 42 0 0 4.4 62 0 0 3.7 11 8 1 8.6 4 为分析在不同类型项目中算法的表现,图4统计了在=1.3,=0.6时各项目参数下算法求解的平均进度偏离成本。首先分析N C,当N C较小时,表示项目网络复杂度低,活动间的约束较少,项目的鲁棒性相对较高,故其对应的进度偏离成本更低,集成式鲁棒调度算法相较于其他算法的优势比较平均。接着分析R F,它表示活动对资源的需求程度,当R F=0.2 5时,表示每个活动仅需要1种技能,活动间因资源而产生的约束较少,鲁棒优化空间小,因此,集成式算法的优势相对较小。可以看出,当R F增大时,集成式算法的优势