（机械设计及理论专业论文）网络计划技术及其在大型矿山设备维修中的应用研究.pdf

摘要 ，7 网络计划技术是五十年代发展起来的种行之有效的项目管理工 具，如f 可利用计算机进行网络优化的集成管理已成为网络技术发展的重 大课题。 本文研制丌发了计算机辅助网络图自动绘制软件，实现了单代号 网络图到双代引网络图的自动转换；针对模糊网络关键路线问题，基于 模糊网络流模型，提出了确定网络关键路线的参数线性模型，得到了模 糊刚络关键路线的更全面的结果：从遗传算法基本原理出发，设计了带 有修复算子的约束优化问题求解方法，用于网络资源均衡优化，该法具 有速度快，精度高的特点：从工序的时- 资特性入手，结合矿山企业的 特i i ，建立了以资源利用效率为优化目标的非库存资源网络优化的数学 模型，并为其提供了有效的算法。 i 德兴铜矿采矿场计算机集成管理与生产系统( c 1 m p s ) 涵盖了生 产、维修、物资供应、财务、人事和办公自动化等多方面内容，并与卡 车调度系统紧密衔接，是一套高效的矿山管理系统。本文阐述了维修( 大 修理) 管理子系统的具体实现。在该子系统的开发中，我们成功地应用 了j ：述研究成果，实现了c i m p s 集成网络优化管j 里功能，取得了良好 的效果。， 关；鼬词；网络技术，关键路线_ c m 伊s 刁广叭弓，；乌，工j a b s t r a c t n e t w o r kt e c h n i q u ei sa ne f f e c t i v ep r o j e c t m a n a g e m e n tt o ( d w h i c hi n i t i a t e di n5 0 s t h eu t i l i z a t i o no fc o m p u t e ri nn c t 、o t k o p t i m i z i n g i n t e g r a t e d - m a n a g e m e n t h a sb e c o m e af o c u si nt h e d e v e l o p m e n to f n e t w o r kt e c h n i q u ea tp r e s e n t t h i sp a p e rd e v e l o p san e wa u t o g e n e r a t i o nt o o lo fa i d i n g n e t w o r kd i a g r a m i t st h ef i r s tc o m p u t e ra l g o r i t h mt h a tt r a n s f o r m sa s i n g u l a r - e m b l e mn e t w o r kt o b i e m b l e mn e t 、 o r k ：b a s i n go nt h e t h e o r e mo fg e n e t i ca l g o r i t h m ，t h i sp a p e rd e s i g n sag e n e t i cs e a r c hw i t h ar e p a i r i n go p e r m o rf o rc o n s t r a i n to p t i m i z a t i o n p r o b l e m s ，t h e o p t i m i z a t i o no f r e s o u r c ei na r r o wn e t w o r kt e c h n i q u e s o nt h eb a s e o fr e s e a r c h i n gt h ec h a r a c t e r i s t i c so fa c t i v i t i e s r e s o u r c e t i m ea s “c ! i a st h ec u r r e n ts i t u a t i o no fb i gs t r i pm i n e sp l a n t ，t h i sp a p e r e s t a b l i s h e st h en o s m r a g er e s o u r c en e t w o r ko p t i m i z i n gm a t h e m a t i c s m o d e la n di n t e g r a t e d n e t w o r ko p t i m i z i n gm a t h e m a t i c sm o d e l ，a m ： a tt h ee f f i c i e n c yo fr e s o u r c e 。t h e s er e s e a r c ho u t c o m e sh a v eb e e n a p p l y i n g i nt h em a i n t e n a n c em a n a g e m e n ts u b - s y s t e mo fd e x i n g c o p p e r m i n e s t o p e c o m p u t e ri n t e g r a t e dm a n a g e m e n t a n d p r o d u c t i o ns y s t e m ( c i m p s ) s u c c e s s f u l l y , w h i c hr e a l i z e sn e t w o r k o p t i m i z i n gm a n a g e m e n t 。 t h ec i m p so fd e x i n gc o p p e rm i n es t o p ei n c l u d e sl o t so l 、 c o n t e n t ss u c ha sp r o d u c t i o n ，m a i n t e n a n c e ，m a t e r i a ls u p p l y ，f i n a n c i a ! a f f a i r s ，e m p l o y e e sm a n a g e m e n ta n do f f i c e a u t o m a t i o n i ta l s oh a s c l o s el i n k sw i t hd i s p a t c h i ti sa ne x c e l l e n tm i n em a n a g e m e n to l h i g he f f i c i e n c y 。t h i sp a p e rd e l i b e r a t e s t h ec o n c r e t er e a l i z a t i o n 。 m a i n t e n a n c em a n a g e m e n ts u b s y s t e m 。 k e yw o r d s ：n e t w o r kt e c h n i q u e ，c r i t i c a lp a t h ，c i m p s 第一章文献综述 第一章文献综述 引述 没器是企业的主要生产手段，是生产力的重要标志之一。由r 人量引进先进设备， 国内许多人型矿山在装备上己达国际先进水平，与世界发达国家相比，主要差距在设备 的管理、使用和维修的水平上。在国外，有专门的设备维修厂家，如美国底特律柴油机 维修中心、康明斯柴油机维修中心、g e ( 电气) 维修中心以及德来赛道路机械维修中心等 这些单位 艮小但专业性很强，为r 保让维修设备的高效率，维修中心1 f 常注重l 序的配 置【l 】。们是在国l = | ，人多数矿山企业远离t 业城市，交通不便，不具备由设备供府商剑 矿山办修理厂的条川，加上国内l ：业水平有限，靠大规模国产化或专业外委修理均小具 备条件，只能立足r 矿山本身。我国的设备维修实行的是汁划预修制。在大修等项日的 管理中，普遍运用“横道图”的方法，或者用手 绘制网络图的方法，以报表的形式制 定生产周期以及爿、年度计划，这种传统的管理手段和方法r 作耸人、效率低，反映的 生产信息滞后生产管理需要，往往造成等i ：、误i + 等现象，延长了i 期，增加了成本， 修理质鞋也得不剑保证。为了故变这种情况，在为德兴铜矿开发的维修管理信息系统中， 我们将刚络计划技术融入其中，取得了很好的效果。 第一节网络计划技术的发展过程及其现状 网络计划技术义称网络方法，是一种夫于生产组织平管理的数学方法。第一二次世界 人战后些【业发达国家在计划的方法上进行了大量的研究j 作，创立并采川了一砦计 划管理的新方法，其中最具有代表性的要算关键路线法( c r i t i c a lp a t hm e t h o d ，简称c p m 】 和计划评审技术( p r o g r a mv a l u a t i o na n dr e v i e wt e c h n i q u e s ，简称p e r t ) 。1 9 5 7 年，c p m 首先在杜f g ( d u p o n t ) 公司得到戍i j ，该公司将c p m 应用于路易斯维h i ) 来表示口 “。箭示图前后关系非常明确，便丁计算机管理。冈此， 本文所讲的网络幽都指箭示图。 长删以来网络幽的绘制一直靠手 作业，存在速度慢、凋整凼难的缺点，使得网络 技术的竹川未能得剑充分的发挥，同时也阻碍了网络技术的发展，迫切需要开发一套网 络图白动生成软件。人们在这方面进行了一些研究，但公开发表的资料较少。美国学者 ar e nt h e s e n 讲述了一种实现网络图自动生成的方法随机网络生成法 1 0 】。这种方法需 要一个集成元件随机网络生成器，而且生成的网络图与它代表的实际1 ：序的关系不 完全相同。这种方法只能应j l f ir 电子模拟网络分析，不适j hr 计算机管理。在系统中， 我t fj 乖j ；4 j 一个简单的图形库( 包括线、圆、箭线等图形) 开发了一套这样的软件，该软 件完全按 ! = c 网络计划表中的信息米自动画图，容易修改，便r 优化调整。 第一节存储方式的研究 一网络图数据在数据库中的表示形式 在系统中我们选用的数据库服务器( d b m ss e r v e r ) 是m ss q ls e r v e r ，前端开 发1 具为p b 。直接输入的和优化后的网络图数据以主从表的形式存在于数据库中。i 序 编号、i 序名称、l ：时等数据存丁主表中，而每道工序的紧前i ：序、紧后i 序等表示网 络图逻辑关系的数据存于从表中，主表和从表之间用外键关联。 _ 二关联矩阵3 系统在绘制网络图时，需要进行大量的计算和分析，为了避免从数据库中频繁地检 取数据，我们把网络图表示成易于计算机读取的关联矩阵形式。关联矩阵有i 种形式， 分别表1 i 两个肯点问、两个箭线间和常点与箭线的关系，如果肯点b 为竹点a 的肝继1 ， 点，则a ( a b ) = 1 ：如果节点b 为1 ，点a 的紧前节点，则a ( a ，b ) = 1 ：如果肯点b 既不是1 ， 点a 的后继肯点，也不是紧前仃点，则a ( a ，b ) = o 。 二链表 当网络图已经生成后，各节点有了编号，我们又将网络图表示成便于遍历和夯找的 链表形式。即将后继恬点形成一个密集表，同时设置指针来表明每个结点的第一个登记 蔓：童旦鳖圈自垫给剑塑鲑的堑蕉丛窒 项在这个丧中的地址。结构如幽( 2 1 ) ： 为了庄计算机里实现这个格式，系统中用到两个一维数组，第一个数组p ，_ l j 爿存放 后继节点的密集表第二个数组p i n d e x ，用来存放每个具体结点的第一个先导在p 中 的地址。这样第i 个结点的第一个后继将用p ( p i n d e x ( i t h ) ) 来检索，而第i 个结点的第 二个后绺将用p ( p i n d e x ( i t h ) + 2 ) 来检索。0 用来表示没有任何，| 亓继。 jf 薹5 9 鎏 l 一 ie 心 八t 结点 。 第一个后继指针 图2 一l 用密集表表示网络结构 篇一个 结点后继 毹个 结点后继 镑三个 结点后继 第四个 结点后继 第 个 缩点后继 第一个空付 第二节网络图自动生成软件的开发研究 一网络图绘制的步骤和规则 绘制网络图的步骤一般为二步：任务分解、作网络图年结点编号。在绘制网络剀日寸 必须遵守r 述规则： 6 箜兰重圈堡笪自麴坌剑墼鲑盟丑蕉丛窒 1 网络图是有向的，幽形从左向右排列，不应有同路： 2 历个结点之间只能有一条箭线相连，如果两个结点之间有多项平行作业，应该加 入1 ：作时间为零的虚作业： 3 进入某结点的箭线，其1 作必须全部完成后，从该点引出箭线的j ：仃才能开始： 儿进入该结点的诸箭线中任务一项r 作未结束，从该点发山的所有箭线的l ：作均 不能开始； 4 1 i 能从箭线的中间引山另一条箭线： 5 小允许出现只有先行i 序而无后继j ：序，或只有后继】序而无先行1 序的中间l 序 网络图的白动绘制在系统中的实现 以电动轮大修部份数据为例，它的数据如表2 1 。 表2 一l6 3 0 e 电动轮人修i ：序明细表 项目代码项目内容紧前j = 序 i ： f 1 ( 大) 人数 a 0 1 清洗 1 1 a 0 2 设备解体 a 0 131 0 a 0 3 人梁修理 a 0 2 2 2 9 a 0 4 后桥壳修理 a 0 25 3 a 0 5 大梁后桥壳组装 a 0 4 a 0 3o 58 a 0 6 悬挂缸修理 a 0 236 a 0 7 悬挂缸组装 a 0 636 a 0 8 悬挂缸安装 a 0 7 , 4 0 5056 a 0 9 前桥修理 a 0 2 1 27 a 1 0 前桥组装 a 0 946 a 1 l 前桥安装 a 1 0 ，a 0 8056 a 12 动力机组分斛 a 0 2o56 a 1 3 动力机组修理 a 1 21 04 a 1 4 动力机组组装 a 1 329 a l5 动力机组安装 a 1 4 a 1 10 56 a 1 6 轮马达修理 a 0 266 a i7 轮马达组装 a 1 645 a i8 轮马达安装 a 1 7 a 1 50 58 a 1 9 准备轮胎 a 0 27l a 2 0 前后轮安装 a 1 9 ，a 1 8 ，a 2 1 0 57 a 2 1 严台修理 a 0 259 a 2 2 、严台安装 a 2 1 ，a 1 9 ，a 1 8 0 56 a 2 3 i 乜气修理 a 0 21 01 2 a 2 4 l u 气安装a 2 3 ，a 2 2 ，a 2 0 56 a 2 5 管道修理 a 0 268 a 2 6 管道安装 a 2 4 a 2 5o55 a 2 7 i u 气静态测试 a 2 6 052 a 2 8 系统调试 a 2 713 a 2 9 i u 气动态测试 a 2 8o54 a 3 0 下斗修理 a 0 22 6l o a 3 l 午斗安装 4 3 0 a 2 9o 56 a 3 2 收尾 a 3 l 2 8 箜兰重 型堡圈自动鳖剑筮鲑的噩蕉盟壅 为使j i 说明，选取前面儿道l 序手j 作部份网络幽如i - 图2 2 网络图 首亢，由l + 序明细表得剑【序之间的邻接矩阵，( 或者说基ri ：序的关联矩阵，陬为 市点的数域和编号没有确定，不能得到基于节点的关联矩阵。) 如图2 2 可刚r 面的邻接 矩阵表示，为了便丁说明，在矩阵中加入了t = 序代码。 其次，系统判断是否有数据错误，算法步骤如f ： 1 在关联矩阵中寻找数据全为零的行，如果这样的行存住，则存在：孤立的l ：守，数据 小o o o 0 o oo0 舢。一 9 0 删。o o o o o o o o o 栅。一 7 0 觚o o o o ，o o o o o 6 袱。o o o o o o o o o 5 0 删o。o o o o o o o似。螂。讹。一。一。 2 3 4 5 6 7 8 9 0 喜|榔似螂蛳彻僦栅伽 误： 2 判断网络关联矩阵a 的阶数n ，如果n 小于或等于l ，则数据上e 确，程序结来 3 如果n 1 ，寻找每一项数据都不等于1 ( 该l ：序没有后继1 j 序) 的行； 如果找剑，就去掉这些行及与之相对应的列，形成一个n i ( n 为关联矩阵的阶，i 每一 项数据都不等丁- 1 的行的个数) 为阶的矩阵，用产生的矩阵替代a ，返同第2 步：如果 找不到，则数据有误，网络出现循环； 最后，生成网络幽，其具体步骤如下： 生成n 个盯点( n 为l ：序数) ，每个节点发出一根箭线代表一道上序，该i 序称为 该节点的外向箭线( 图2 - 3 a ) ： 找出每道序的紧前1 ：序，并且生成指向这个节点的箭线，称为内向箭线( 图2 3 b ) ： 合并具有一个或多个相同内向箭线的节点( 图2 3 c ) ： a 0 2a 0 矾0 4a 0 3a 0 2 ：* 廷p 9 娜 0it1 0i j0 a 0 2 a 0 3 a 0 4 a 0 5 a 0 6 a 0 7 a 0 8 a 0 9 a 1 0 a 1 1 a a 0 2 尚 t 棚 a 0 3 ，a 0 4 a 0 6 a 0 帆0 5a 0 7 a 0 2a 0 9 1 0a 0 8 尚菇尚尚蒿 丫丫丫丫丫 + a 0 7a 0 8a 0 9a 1 0a 1 1 b a 图2 3 网络图在计算机中的形成剀 将内向箭线与外向箭线相同的箭线联结，当由一个任点发出的两道【：序义指向同 一个仃点时，增加一个肖点并用虚线相联( 图2 3 d ) ； 生成一个结点，将没有与内向箭线相联的外向箭线指向这个1 y 点： 按先后次序对每个节点重新编号。 9 0 | ；v宁!；0宁m0宁m 宁艘 电动轮( 6 3 0 e ) b m p ( 4 8 0 x 9 5 0 x16 mb m p ) 铲。粪黔、 i 誊萋 簧 7 一a 、。 一烈辞 跌 墨9 囊 f_峭st。)袋 畸o)一龆 n o 婚 。帐崎。j謇 一 ，j 。、。 ， 罾妙， 、 一岬。j b 目e 一嫩扰，o叫州 ，卜、“ 篷。)燃一o量 一譬。一赡 暾 峭。8爨。 “v 搿 、， g 卜 一oo嚣+h鬻 髫尊；m爱 一峨吖黛i翁 啤峨o - o |i蝌。毋肇吖 u p 套 崎岱警 一q嚣h疑 、， 囊， 岭 03gh一翘 0 3 一誊# f ￥崎n 墨 ￥o 式曼 _ 。、 攀 复：重圆终笪自麴鳖剑鏊壁盟五蕉堡塞 第三节单代号网络到双代号网络的转换 在实现网络的白动生成的过程中，一个关键问题是单代号网络向双代号网络图的转 换。由l 序明细表不能直接得到舣代号网络，只能通过单代号网络的转换得到。 从幽论的观点石m i i ”1 ，规范的单代号网络图是一个a o v ( a c t i v i t yo l lv e r t e x ) 网，规范 的双代号网络图是一个a o e ( a c t i v i t yo ne d a g e ) 网。对丁单代号网络计划图，i ：作明细表 中i = 作相当于a o v 网的节点，而l 作关系则确定了节点的关联，冈此可以得到相席的单 代号网络剀。我”j 以表2 一l 中的a 0 1 ，a 0 2 ，a 0 3 ，a 0 4 ，a 0 5 元道f ：序为例，它们形成的单 代号网络图如图2 4 。 图2 - 4单代号网络 由邻接矩阵可以求出单代号网络图中育点和边之间的芙联矩阵，即行对应幽的i ，点， 列对麻幽的边。列出所有的行，依次寻找邻接矩阵a 的元素。如= 1 ，则对府幽的一条 边，丁是关联矩阵b 中增加一列( 设为第k 列) ，且b a = l ，b j k = - 1 。r 式即为幽2 - 4 的关 联矩阵。 4 0 1 爿0 2 4 0 3 a 0 4 爿0 5 1 22 3 10 11 01 00 oo 3 4 2 55 4 0 0 0 010 1 00 一l01 o一1 l 式中：数字“12 ”表示a 0 1 、a 0 2 之间的箭线，其余类推。 我们通过对这个关联矩阵的变换来实现单代号网络图与般代号网络图的转换。 按 ! 幽论理论i ，a o v 网和a o e 网都属于有向连接图。若有对应于同 l ：作明细 表的单代号网络图g ，= ( v i ，e i ) 和双代号网络图g2 = ( v2 ，e ：) ，v - ，v 。表示节点集合，e e ，表示边的集合。单代号网络图中，v 。对应工作集，e 对应关系集，域代号网络幽 中，v ，对麻关系集，e ，对麻i 作集。它们的对应关系用图2 - 5 表示 0 筮= = 三：羹! ! 鳖圈旦麴丝劁墼盐曲珏丝逝壅 啦净璐 图2 - 5单代号和烈代号网络对应关 可以舀“jg 。g ：存在一种对偶关系即a o v 蚓巾的节点v ( 单代号网络图中的任务 p 。) 对应a o e 网中的边e ，( x 2 代号网络圈中的任务p ) 。在这种对应关系的映射p 对转置后 的g 关联矩阵p 经过一定变换可以得到g 。的关联矩阵。其变换的步骤如r ： j 关联矩障转置后，对所有元素取反 因为边年| j1 7 点互换后，节点和i 边的引入羊引出关系上e 蚶和原来的相反，所以要反0 。 如矧2 6 所示，v ，点对应的行向量为f 【一；。：。1 r 变换之后边e j 对应 扩 的剧向蛄为 k e f l 一1 单代号蚓络幽取代弓刚络图 v 1 - - i f 1 集l 一一e 2 e 1 - 笑系集+ v 2 图2 - 6点边转换 。v 。作为e j 的结康1 i 点，e k 的开始1 ，点。在a o v 网转换之历所有 i ? 点和边的引入利引出关系都发生，类似的变化，所以转置斤都必须把元素变弓。 2 合并牡点 经过第一步变换的矩阵p 中，若菜一别中“j ”出现的次数多于一次，则需对矩阵 p 做妇f 变换： 星：童 型鳖崮旦麴丝剑塑笠的扛蕉丛壅 k 。 - k 。 a np d m 卜 “n ，+ 以m f + k n j k m k 。+ 1 “。一1 1 1 变换前矩阵p 中第k 列从第n 行元素到第m 行元素均为“l ”，而关联矩阵中一列 “1 ”只能出现一次，为此，把行向量k 。，k 。，k 。相加剑向鼙k 即 k 。= k 。+ k + + k 。 其中，a 。舢= a wo a 川，o o a m ， 对。我们定义如r ：0 0 0 = 0 ，0 0 一1 = 一1 ，一1 0 0 = 0 ，1 0 l = 1 。这种转 换的意义是，若一个i ：序有多个紧前一r 序，则转换后每一个紧前j ：序的结束1 ，点合并成 r 一个性点。 3 增加虚任务 经过第一步变换的矩阵p 中，若某一列中“一l ”出现的次数多r 一次，则需对矩 阵p 做如r 变换： a ， h ih 0 ；o0 口。j1 111 a ，“。i - 1 0 0 0 。i0 0 1 ；00 假没某一列中“一1 ”的次数为m ，则矩阵p 增加m 1 列；第i 行增加的元索全部 为“1 ”，从第i + l 行开始依次在f + k 行、n + k 列的位置取“一1 ”，1 k m 。这种# 0 换的物理意义为在单代号网络图中从同一忸点引出的紧后i 序多丁- 一个的情况r ，龠一要 增加虚任务；每增加一个紧后i ：序就增加一个虚任务。 4 增加总开￥点 经过上述二步变换后的矩阵一定存在一列，该列除“l ”出现一次外，其余，c 豢 都是0 ，这一列对虑取代号网络图的第一项作业，在关联矩阵中增加一行，在该列何爿 上的元素为“l ”，其余元素为0 。 5 增加完1 仃点 经过上述四步变换后的矩阵一定存在一列，该列除“1 ”出现一次外，其余元素部 楚“0 ”，这一州对应比代号网络图的最后一项作业，在关联矩阵中增加一行，仡该列位 置上的元素为“一l ”，其余元素为“0 ”。 6 删除多余的虚任务 如果n 个虚任务所对鹿的列向量线性相关，则其中的n - 1 个多余的虚任务v 以删 筮三童圈缕笪臼垫丝剑墼型：的珏筮婴窒 除其中的任意n 1 个列向鼙。这是闳为每一列中只的“l ”禾j “一l ”防个1 | 零几系，持 仃n 个列向苗线性相天，则每一列中相同的元素只能出在相同的位置一，即这此虚f f 务 连接的是相同的h 点，庵将多余虚任务删除掉。 7 合并多余仃点 如果经过上述第一、第一步变换之后得到的矩阵p 中存在一个方阵它的冗素全部 为1 ，则方阵所在的行合并，行向氅相加采_ e j 第一二步中，l | j 剑的法则。直观解释是，如果多 个1 y 点的g l 入边相同，而引出边f 同，则这些1 ，点可以合并同一个诲点。如剧2 7 、， 合并前 图2 - 7 多余节点合并图 第四节小结 合并历 本章阐述了网络图数据在计算机中的二种表示形式，研制并开发了计算机辅助网络 图i 】动生成i 具，首次给出了由单代号网络图到双代号网络幽转换的算法，实现了嗍络 幽在计算机中的白动绘制。开发的网络图自动生成i 具有良好的通刚性和可移械性，具 有相当高的使_ l j 价值和良好的推广前景。 塑三重苤壁堕缝鱼定婴塞 第三章关键路线确定研究 借助网络幽，可以计算有关时间参数，决定关键t ：序和关键线路，更合理地使瑚人 力、物力和资金等1 r 库存资源，利用较短的时间和较少的费删完成全部任务。 第一节时间参数计算 网络时间参数的计算包括：确定各项作业的作业时间；计算每项作业的最甲开始、最 甲结束、最迟开始、最迟结束时间，计算时差等。 一作、皿时间的确定 作业时间是指完成一项序所需要的时间，用符号t 表刁 ，表示i 序i - j 作业日寸侧， 确定作业时间有_ 二种方法： 1 肯定型。在确定各项作业时间时，只确定一个时间值b 。这种方法一般应用丁不 可知冈素较少，或者有先例可循的情况下，可根据工时定额或劳动定额资料米估计各项 i 。序的 1 业时间，也可以h i 其它统计资料和经验数据，蹦统计分析的办法米确定。其公 式为：t ，= b 。 2 1 r 肯定刑。这种方法是用三个时间值来估计作业时间值。应用丁不具备j ：时定 额和时间消耗统计资料，且未知和不确定的因素较多的情况卜。先确定三种不同的时问 值： ( 1 ) 最乐观时间：完成某r 序可能出现的最短时间，用符号a 表示； ( 2 ) 最可能的时间：完成某项作最可能出现的时间，以符号m 表示； ( 3 ) 最保守的时间：完成某项l ：作可能出现的最长时间，以符号b 表示。 然后，j j 平均时间：，= ( d + 4 m + b ) 6 来表示该i 序的时间。这实际是一个估计值， 其偏筹为：盯= ( 6 一a ) 6 。 这种确定时间的方法建立在假设二种时间为某一随机变最概率分布( 如b 分布) 的 二个有代表的分最的基础上。 二项目时间参数的计算公式e 2 4 墨三蔓苤壁堕垡鱼宣婴塞 网络时间参数的计算主要是算出作业最早开始时间、作业最迟开始时间、作业最迟 结束时间和作业最早结束时间，再用它们之差算出每道l 序的时差，为计划进度的安排 提供选抒的可能性。 作业最甲开始时间，指一个作业能够开 的最早时间川。) 表示，计算公式： ，( 1 一n = 0 r ( ) 2m a x ( t e s ( 一1 ) + ( t 一) ) ( k i j ) ( 式3 1 ) 式中：i 表示箭尾事项编号，j 表示箭头事项编号，t ( kj ) 表示紧前l ? 序1 ：期。 作业最迟开始时间，指在不影响整个任务按期完成的条什r ，本作业最迟必须开始 的时刻，i hf “，1 表示，其计算公式： t n ( ，一m = q 一，( ) ， ，一j ) 2m i n ( t 。s ( 一) 一t ( , - s ) ) ( i j v ”， i q l j f ( v ) f ( v ) 2 ) 若到任意n ：n ( i ，) 爿，v 。v ”， 贝1 1 f ( v 。) f ( v ”) 。 证明：记x 。( x ”，) 为v ”( v ) 时问题( 1 ) 的最优解。4 b i 殳( v ，v ”v ，v ( i ) a 。 冈为对v ( i ，) 爿，x ”0 且x 0 ，那么有v x ” v x = f ( v ) 。 此时，x 也为 v = v 时问题( 1 ) 的解。故厂( v ) v x ”。进而可得f ( v ) f ( v ”) 。冈此( 1 ) 成立。类似可证( 2 ) 。 由定理( 1 ) u 丁知，n 。( 口) 和 ，。( 口) 分别为【0 ，1 上的严格增函数和严格减函数， 闵此其反函数，( ) 和虬( ，) 存在，且，( o ) = ，( o ) = ，。 由上述分忻可知。( ，) 与n p ( 1 ) - n n a ( ，) 具有如f 关系 定理2 ： 。( f ) = ，( f ) n 。1 ( f ) ，【，】 。一饥，。【? ，乃 o ，o t h e r 证明：任意给定，。 f ，? ，设d 。：f 一1 ( f o ) 。此时口：，一( 1 一妒为问题( 4 ) 的。r 行解，故t 巾1 ( ，o ) ，另外，由定理1 可知，对a a o 和v v ( a ) 有 ，( v ) f ( t 一( 1 一a ) ，) f ( t 一( 1 一a o p ) = ，o 。因此，对 a o ，不存在向昔v = ( v 。) 使得，v ) 为问题( 4 ) 在，= ，o 时的可行解。故有九，) ( ，。，) = d o = p - - i ( ，o ) n 类似可证，( ) ( ，。) ：，一1 ( 毛) ， ? ，- 。 由定理( 2 ) 呵知，虽然我们以项目计划人员所持的态度不同为皋础，建立 了确定网络关键路线的参数线性规划模型( 式3 一l0 ) 和( 式3 一l1 ) ，f r 该模 型实质j ：等价十利川扩张原理描述的问题( 式3 9 ) 。只不过在模型( 式3 10 ) 筻三童苤壁竖垡塑室丛塑 和( 式3 一l1 ) ， 】给予参数a 风险态度的含义。 为了分析方便，我们将( 式3 10 ) 和( 式3 一l1 ) 表_ 为含参数 五【0 , 2 】的线性规划形式。对旯 0 ，1 】，仃 m 势 ( r v + ( 旯一1 ) r , a ) x r x 工 ( 式3 “l4 ) l j ，* 对 f 1 2 】青 m 势 ( f u + ( 五一1 ) d ) x i x 盖) ( 式3 一l5 ) i ，j d 式l l 五【0 ，1 】表示项目计划人员为乐观艰，其值越小，则表示项h 计划人员越峨 观：五 1 , 2 】表示项目讨戈0 人员为保守犁，其值越人，j l l i j 表示项目计划人受越保守， 通过求解参数线性规划l q 题( 式3 ld ) 和( 式3 i5 ) ，可得剑m 问【o 2 j 女j 个划分 p = p ，= 【o ，丑】，p 2 = 五l ，五2 】，一p 。= f 丑。，2 1 j ， 由线性脱划知t 5 易知，对应参数五风( 仇p ) ，( 式3 一i4 ) 和( 式3 一j j 的最优毖对应刚络的关键i ：序，进而可得关键路线。 ：j 尊倒 考虑矧3 2 所示的1 6 v 1 4 9 发动机大修网络模剐的天键路线。其网络参势山 i 、= ( 3 2 ，1 ) ，f 1 3 = ( 7 ，l ，3 ) ，2 ；= ( 5 , 2 ，1 ) ，f 2 4 = ( 5 2 1 ) f w = ( 7 , 2 ，1 ) ，3 5 = ( 8 2 2 ) ，4 5 = ( 3 ，1 ，2 ) ，“= ( 4 , 2 ，3 ) ，5 6 = ( 5 2 1 ) 。 筮三重 苤焦堕垡堕枣堡窒 幽3 2 1 6 v 一1 4 9 发动机人修网络模刑 利用模刑( 式3 一l4 ) 和( 式3 15 ) ，得网络关键路线的参数模型线性模型如p 对于旯 0 , 1 】有 m a x ( 1 + 2 2 ) x l2 + ( 6 + j t ) x l3 + ( 3 + 2 2 ) x 2 3 + ( 3 + 2 2 ) x 2 4 + ( 5 + 2 a ) x 3 4 4 - ( 6 + 2 2 ) x 3 5 + ( 2 + 2 ) x 4 5 + ( 2 + 2 a ) x 4 6 + ( 3 + 2 五) 石5 6 】 对丁兄【1 , 2 】有 m a x ( 2 + 2 ) x l2 + ( 3 + 4 2 ) x 1 3 + ( 4 + 旯) 石2 3 + ( 4 + a ) x 2 4 + ( 6 + a ) x 3 4 + ( 6 + 2 2 ) x 3 5 + ( 1 + 2 2 ) x 4 5 + ( 1 + 3 2 ) x 4 6 + ( 4 + 五) z 5 6 】 s t x i2 + 一3 = 1 x 2 j + x 2 4 一x 1 22 0 x 1 4 + x 3 5 一x 13 一x 2 32 0 y 4 5 + 0 4 6 一x 2 4 一x 3 4 。0 x 5 6 一x 3 5 一x 4 520 一x 4 6 一x 5 62 1 求解上述模刑可得关键路线和完i 期结果见f 表。 箍三重羞壁堕缝塑室婴窒 丧3 一i 天键路线及l ：程完j 期计算结果表 取值防间关键路线 i 群完】：期 0 ，2 3 l 一3 4 - 5 6 1 6 + 6 2 3 ，1 1 2 3 4 5 6 1 4 + 9 凡 1 3 2 1 2 3 4 5 61 7 + 6x 3 2 ，2 i 3 - 4 5 - 6 1 4 + 8 第三节小结 本章提出网络l 划时间参数的计算机算法，指出了传统关键路线算法的不足分忻r 模糊网络关键路线问题，基r 模糊网络流模型，利用扩张原理，提山了确定网络关键路 线的参数线性规划模型。从所得结果来看，其蕴含着项目计划人员的风险态度的深层含 义。这无疑对网络关键路线的分析赋予了更多的信息。 2 4 第四章网络资源优化分析 第四章网络资源优化分析 网络理论的核心问题就是如何在网络上进行资源的最优分配。经过几十年的府川和 研究，人们提出了多种网络优化的数学模型，这些模型利方法在实践中取得r 良女r 的效 果，但是它们都是以时间最短为优化目标，忽视了资源的使用效率。本章以资源的使州 效率为优化目标，即以资源的停l ：量最小为优化目标，建立资源优化的数学模硝。 第一节工序和网络图的时资特性分析 一1 序的时资特性 资源变化在一定范围内，可以认为i ：序的完1 ：时间与完成该i ：序所占用的资源数昔 成反比j 。即有f 述时资特性关系： ，。：墅 。 x ， 约束条r l ： x ，。x x ，。瓢 式中： q “表示t = 序i j 的i 二程量用： t “表示完成i ：序u 所占用的时间； x 。表示完成r 序所占用的资源； x 。，表示完成某一【程项目或者某一单项 作所需用的最少资源数量： x i 表示进一步增加资源数量而不能改变完成工作所_ l i ；| 的时间的资源数量。 如果我们探讨的是无限可分的资源，那么上式可用图4 - 1 a 表示，当资源在医问( x 。 x i j , m i x ) 上是整数时，那么上述关系应该是离散的( 图4 - l b ) 。 第四章网络资源优化分析 t l j t m “ t m i n a 图4 - 1工序时一资特性 b 我们住这里只考虑无限可分的资源，在研究具体问题和算法时再来研究整数解的特 点。 _ 二网络图中各项i ：作的相且影响及其时资特性 1 各项i + 作的相且影响 设有二项按平行作业进行的i ：作，其l 作量分别等 二q 。q 。，q 。它们的时资特 性曲线( 如图4 - 2 ) 。假定已成功地将资源总数分配到各项：作中，使： t l _ 2 ：绝：盟：一q l - 4 x i 一2 x 1 3x 1 4 ( 4 2 ) x 1 2 + x 1 3 + x l 一42 x ( 4 3 ) 在此情况f ，关键时间将等于t k = t 1 2 = t 1 3 = t 。各 序停i 时间等r 零。 假设通过某种方式将