第14卷第12期计算机集成制造系统Vol.14No.122008年12月Computer Integrated Manufacturing SystemsDec.2008文章编号:1006-5911(2008)12-2431-05收稿日期:2007-12-24;修订日期:2008-04-28。
Received 24Dec.2007;accep ted 28Apr.2008.基金项目:国家973计划资助项目(2005CB724100);国家863计划资助项目(2007AA04Z110,2007AA04Z190);国家自然科学基金资助项目(70271053,70772056)。
Foundation items:Project supported by the National Basic Resear ch Program ,China(No.2005CB724100),th e N ational H igh -T ech.R&D Program,China(No.2007AA04Z110,2007AA04Z190),and the National Natural Science Founda -tion,China(No.70271053,70772056).作者简介:管在林(1966-),男,江苏高邮人,华中科技大学机械科学与工程学院副教授,博士,主要从事约束理论、制造系统建模与仿真等的研究。
E -mail:zlgu an@h 。
基于贡献度的项目调度方法研究管在林1,马 力1,何 敏2,邵新宇1(1.华中科技大学机械科学与工程学院数字制造装备与技术国家重点实验室,湖北 武汉 430074;2.武汉烽火通信科技股份有限公司,湖北 武汉 430074)摘 要:为改进传统的项目管理方法,提出了一种由统计理论得出的指标)贡献度来决定在关键链识别过程中的冲突解决策略,以达到识别出项目关键链的目的。
为使调度计划在不确定性环境下能够顺利实施,该调度方法充分考虑了项目执行过程中工序的随机性。
在此基础上,提出了一种关键链识别方法,最后针对标准问题库PSPL IB 中的典型算例,应用M atlab 进行了仿真验证。
关键词:项目管理;项目调度;关键链;瓶颈;贡献度中图分类号:T P391 文献标识码:AProject scheduling method based on the contribution indexG UA N Zai -lin 1,MA Li 1,H E M in 2,SH A O X in -yu1(1.Stat e K ey L ab of Digital M anufact ur ing Equipment &T echnolo gy ,School of M echanical Science &Eng ineering ,H uazhong U niversit y of Science &T echno lo gy ,W uhan 430074,China;2.Fiber Ho me T elecommunication T echnolo gies Co.,L td.,Wuhan 430074,China)Abstract:T o improv e tr aditional pro ject manag ement methods,a conflict r eso lutio n strateg y in identify ing the cr itical chain of the pr oject by using the contributio n index co ming fr om the st atistical t heo ry was pro po sed.T o r ealize smo oth implementatio n o f project scheduling under uncer tain env ir onment,the r andomness o f the pro ject procedur e during the pr oject ex ecution pr ocess w as taken into consideratio n in this method.Based o n the str ategy ,a new crit-i cal chain identificat ion metho d was int roduced.Finally ,based o n one standar d instance f rom the w ell know n PSPL IB benchmar k set,simulatio n ev aluatio n to this method in M atlab env ir onment w as pr esented.Key words:pr oject management;pro ject scheduling ;critical chain;bott leneck;co nt ribution index0 引言在当前装备制造业成为我国重点发展方向的背景下,有必要改善传统的项目管理理论与方法,验证新方法的可行性,并最终将其应用在大型机电装备的设计、加工和装配过程的规划与管理过程中。
高德拉特(Goldratt)博士于1986年提出了约束理论(T heo ry of Co nstraints,TOC),强调以系统整体的观点进行生产管理。
之后,他将TOC 引入到项目管理领域,提出了一种基于瓶颈识别及缓冲管理的新方法)))关键链项目管理(Critical Chain Project M anag em ent,CCPM )方法[1]。
传统的关键路径法(Critical Path Metho d,CPM )在确定关键路径时,主要依据预先估计的任务时间与任务间的逻辑关系,并没有充分考虑资源约束对项目计划的影响[2]。
而CCPM 方法则认为决定整个项目效率的计算机集成制造系统第14卷是一条考虑了任务相依性以及项目资源约束的、决定项目完工时间的最长活动链)))关键链(Cr itical Chain,CC)。
CCPM的核心是识别项目中的瓶颈,并通过设立缓冲以及对缓冲的管理机制,来保证瓶颈环节的顺利运转。
迄今为止,已提出了许多不同的关键链识别方法[3],但或多或少都存在一些局限,其中较为典型的是在关键链识别的过程中,武断地将工作时间截取50%作为关键链调度方法的参考时间[1]。
在计划阶段,项目被分解成若干活动,并对各活动所需的时间与资源数量进行估计,明确各项活动之间的先后逻辑关系后,即可得到针对整个项目的网络图。
本文提出一种基于统计理论的贡献度算法,该算法鉴于网络计划中的活动时间是随机变量,借助活动时间的期望和方差等统计学参数来确定网络计划中某个活动对于整个项目的影响程度,即贡献度,从而找到制约整个项目进度的瓶颈)))关键链,最终针对该网络计划,得到一个在不确定性环境下依然能够顺利实施的可行活动调度计划。
1基于项目调度计划评价的数学模型现假设项目中各活动持续时间是相互独立的随机变量,且在项目网络G(N)中只有一条计划线路占据支配地位,该计划线路就是关键链。
相应地,项目总工期就是关键链上所有活动的随机工期之和,项目平均持续时间和方差就是对应关键链上各个活动时间的平均值总和及关键链上各活动的方差总和。
一个好的项目调度计划应该使项目平均工期和方差均维持在较低水平,即最小化某个以项目工期和方差为自变量的目标函数f(E(D(G)),Var(D (G)))。
为讨论方便,提出以下数学模型:min f(E(D(G)),Var(D(G)))。
(1)m in WI P=E J j=1(1|S j|@E i I Sj(SST i-SF T j))。
(2) s.t.S ST i-SF T j\d j,i I S j。
(3) Ej I Atr jk[R kt,k=1,,,K,t=1,,,T。
(4)式中:G(N)为一个基于节点的随机项目网络计划图;D(G)为项目总工期;E(D(G))为项目总工期的期望;Var(D(G))为项目总工期的方差;i,j为任务的下标;k为资源种类的下标;t为时刻的下标;d j 为活动i的随机工期;S j为活动j紧后工作集合;S ST i为活动i的计划开始时间;SFT j为活动j的计划结束时间;r jk为活动j所需要的k种资源的数量;A t为(t-1,t)时间段内正在进行的活动集合; R kt为t时刻k种资源可用量。
以工作j(j=1,,,J)代表项目中的J项活动。
活动1代表项目中唯一最早开始的活动,活动J是唯一最晚完成的工作,分别代表整个项目的开始和结束。
项目调度计划可以用J元组S=(SS T1, S ST2,,,SS T J)表示,其中SST j为活动j的计划开始时间。
一个可行计划是指各项工作开始时间已经确定,且满足紧前关系及资源约束的调度计划。
目标函数式(1)最小化项目工期均值和方差;目标函数式(2)最小化项目在制品水平;式(3)代表紧前关系约束,式(4)代表资源约束。
此外,在CCPM方法中,其应对项目执行过程中的不确定性的策略是将关键链上工序各自的安全时间提取出来,并放置在关键链尾部作为项目缓冲,从而吸收不同工序波动带来的累加效应。
因此,即使对于不同类型的随机分布类型(如均匀分布、正态分布、指数分布等),该模型的鲁棒性也是有一定保证的。
本文就是在该模型的基础上,使用一种启发式算法求出决定项目工期的关键链。
2贡献度概念的引出使用启发式算法进行排序时需用到优先调度规则,通常用到的规则有最迟开始时间(Latest Start T ime,LST)、最迟结束时间(Latest Finish T ime, LFT)等。
然而,这些方法只考虑了活动本身当前的紧急程度,并未从整体的角度来考虑该活动对整个项目目标实现的贡献程度。
因此,本文引入两个参数来综合衡量某个活动对整个项目的/贡献0程度,即关键指数CI和关联指数[4-5]C UI。
定义1关键指数CI j是指项目中某项活动a j 出现在关键链上的概率。
其数学表达为C I j=Pr{a j I p l B P p h IP B L(p l)\L(p h)}。
(5)式中:A{a j|j=1,,,J}表示项目中所有活动的集合;P为项目网络计划中所有路径的集合;p l为项目网络计划中编号为l的路径;L(p l)为路径l的长度。
定义2关联指数C UI j指项目中某项活动a j 与项目总工期D的关联程度,其数学表达为CUI j=|C or r(a j,D)|2432第12期管在林等:基于贡献度的项目调度方法研究=|Cov(a j,D)Var(a j)@Var(D)|。