资源描述：
《等效子网络构建的理论与方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第13卷第1期管理科学学报Vol.13No.12010年1月JOURNALOFMANAGEMENTSCIENCESINCHINAJan.2010①等效子网络构建的理论与方法乞建勋,李星梅,王强(华北电力大学工商管理学院,北京102206)摘要:关键路线法(criticalpathmethod,CPM)网络计划是项目管理最得力的工具之一.通过研究CPM网络图自身的规律性,给出了从源点到任意节点,以及从任意节点到汇点最长路线的路长计算公式,进而推导出反映总时差与路长关系的定理———总时差定理,并在其基础上,设计出构造等效子网络的简单方法,分析了方法的正确性,且得出该
2、方法的计算复杂度为O(n).实证表明,该方法简单易行,便于应用.对于时间-费用优化问题,可以用少数几条路线组成的子网络代替由几十条、几百条路线组成的原始网络,使计算工作量得到简化.关键词:项目管理;时差;等效子网络;时间-费用优化中图分类号:TB114.1文献标识码:A文章编号:1007-9807(2010)-01-0040-050引言的特点,就会发现工序之间的轻重份量是不同的,有些工序必须重点考虑,有些则可以不予考虑.近十多年现代项目管理取得了飞速发展,目如把100d的总工期压缩到90d,只要把网络中路前它不但形成一门新的学科,而且已经成为一种长大于90d的路
3、线全部压缩到90d就可以了,至职业.美国项目管理协会(ProjectManagementIn2于路长小于等于90d的路线,无论压缩与否,对总stitute,PMI)编制的项目管理知识体系(project工期的缩短都不会产生任何影响,因此无需考虑.managementbodyofknowledge,PMBOK)把项目在一般情况下,小于等于90d的路线占多数,去掉管理划分为九大领域,其中“时间管理”和“成本这些路线后可以大大减少计算工作量.这种想法[1]充分利用了网络计划自身的特点,但是长期以来管理”是其核心的两大领域.而“时间-费用”问题是这两大领域的交叉,应用极
4、其普遍.不能实现,因为寻找所有路长小于等于90d的路但是目前“时间-费用”问题的优化方法计线是十分困难的.国内外已有学者考虑用简单网算工作量太大,如经典的“工期一定,求费用最络去代替原始网络,即等效子网络(辅助网络),[2]低”,“费用一定,求工期最短”等问题,通常用线但在该网络的构造上,要么方法比较复杂,要[3]性规划法求最优解,先把计划网络化为一个线性么没有理论依据.规划模型,把费用最低或工期最短作为目标函数,运用CPM网络计划最大优点是可以计算出[4-5]利用单纯形法求解.但是因为计划网络中的每个每个工序的时差,从而判断每个工序在全局工序都对应一个变量和两
5、个约束条件,因此,化成中的地位.但是目前对时差的研究还很缺乏.[6-7]的线性规划模型中变量和约束条件很多,计算工1956年杜邦公司提出CPM网络计划后,作量十分巨大.事实上,线性规划方法没有考虑Battersby和Thomas分别于1967和1969年给出四网络计划自身的特点,对每个工序不管其重要程个时差概念:总时差,安全时差,自由时差和干扰度如何,都是同等看待.如果考虑到网络图自身时差;Elmaghraby于1977年给出节点时差概①收稿日期:2007-01-16;修订日期:2009-09-26.基金项目:国家自然科学基金资助项目(70671040);教育部
6、博士点基金资助项目(20050079008).作者简介:乞建勋(1946—),男,河北邢台人,教授,博士生导师.Email:xingmeil@163.com第1期乞建勋等:等效子网络构建的理论与方法—41—[5][5]念,并给出这些时差的分析和陈述.针对网1.2基本定理络本身的复杂性,这五个时差还不足以反映时差在CPM网络图中,为了给出时差与路长的关的特性以及工序之间时差的内在联系.为使CPM系,即总时差定理,本文先给出源点(1)与任意节网络计划中,紧前和紧后工序的时差关系变得清点(i)之间,以及任意节点(j)与汇点(w)之间最楚,乞建勋教授于1997年给出前共
7、用时差和后共大路长的计算公式,如以下引理所述:用时差概念,把安全时差更名为前单时差,自由时引理1源点(1)与任意节点(i)之间的最[8]3差更名为后单时差,并于2006年又给出两个新大路长μi等于节点(i)的紧后工序(i,j)的最早时差概念:前共后单时差,前单后共时差,为了有开始时间ESij,即3利于概念统一,把干扰时差细分为双单和双共时μi=ESij(1)[9]差,且在2007年初步研究了时差的规律性,分证明在双代号网络图中,任意工序最早开析了工序时差传递性问题,提出基于双代号网络始时间都等于其紧前工序最早结束时间最大计划的标值算法,量化了任意工序使用时差时对
8、值,即[10-12]整个
