（应用数学专业论文）带有松弛量的平行工序顺序化优化方法探究.pdf

摘要 带有松弛变量的平行工序顺序优化的问题是指从n m 个独立进行的平行工 序中选择m 个调整为顺序工序链的优化问题。该问题恰是项目排序中考虑机动时 间和带有任意松弛变量问题中的一种。其自身的复杂性使得传统的运筹学中的线性 规划和启发式方法都不是解决该问题的较好的办法。本文针对该问题，针对网络中 工序本身具有的机动时间的特性。按照由此推导出的亏值定理从网络自身的规律出 发。推导出工序后移定理和最大亏值定理。在此基础上制定出合理的调整工序的目 标函数和每次选择调整工序的优化方法。最终解决了平行序链顺序化最优决策的问 题。在最优顺序链的基础上，调整得到整个序链全部工序顺序都优化过后的初始序 链。在此基础上，基于在初始序链的基础上通过删除合适的工序可以得到带有松弛 量的平行工序的顺序优化序链的想法。依靠推导出的去工序定理和最小亏值序链定 理给出了选择最优被删除工序的依据和方法。最终解决了带有松弛变量的平行工序 的顺序化优化问题。 关键词：排序；机动时间；松弛变量；亏值 a b s t r a c t t h ep r o b l e mo fm p a r a l l e la c t i v i t i e so fn mp a r a l l e la c t i v i t i e sb e i n ga d j u s t e dt oap r o c e d u r e c h a i ni so l l eo ft y p e so fp r o j e c ts c h e d u l i n gw i 也a c t i v i t yf l o a ta n da r b i t r a r yr e l a x a t i o nq u a n t i t i e s t h e c o n v e n t i o n a ll i n e a rp r o g r a m m i n go fo p e r a t i o n a lr e s e a r c ha n dh e u r i s t i ca p p r o a c h e sb o t hc a nn o ts o l v e t h i sp r o b l e mp e r f e c t l ys i n c et h ec o m p l e xo ft h ep r o b l e mi t so w n i na l l u s i o nt ot h i ss i t u a t i o n ，t h e a u t h o rd e d u c et h em a x i m u md e f i c i e n tv a l u eo fc h a i nt h e o r ya n dr e t r u s i v ea c t i v i t yt h e o r yd e p e n d o nt h em a x i m u md e f i c i e n tv a l u eb e t w e e n a c t i v i t yt h e o r yw h i c hi sp r o p o s e db yv i r t u eo ft h e c h a r a c t e r so ft h ef l o a tt i m eo ft h ew h o l en e t w o r k 。t h e nt h em e t h o do fg e t t i n gt h eo p t i m a lc h a i no f p a r a l l e la c t i v i t i e sc a nb eg i v e n a st ot h ep r o b l e mo fg e t t i n gt h es e q u e n c i n go p t i m a lm e t h o do f p a r a l l e l a c t i v i t i e sw i t hr e l a x a t i o nq u a n t i t i e s ，f i r s tw ec a ng e tt h ei n i t i a lc h a i nf r o mt h eo p t i m a lc h a i nb ys o m e a c t i v i t yo p t i m i z a t i o na d j u s t m e n to nt h ep u r p o s eo f g e t t i n gt h eo p t i m a lc h a i no f p a r a l l e la c t i v i t i e sw i t l l r e l a x a t i o nq u a n t i t i e sf r o mt a k i n go u tt h ep r o p e ra c t i v i t yo ft h ei n i t i a lc h a i na n db a s e do nt h em i n i m a l d e f i c i e n tv a l u ec h a i na n dt h er u l eo fp i c k i n ga c t i v i t yw h i c hw o u l db et a k i n go u t ，t h ea u t h o rf i n a l l y g i v et h ef o u r i d a t i o na n dm e t h o do fg e t t i n g t h eo p t i m a lc h a i no fp a r a l l e la c t i v i t i e sw i t hr e l a x a t i o n q u a n t i f i e s t h u s ，t h i sp r o b l e mc a nb es o l v e dp e r f e c t l y l uh a n ( a p p l i e dm a t h e m a t i c s ) d i r e c t e db yp r o f q i r o n gq i u k e yw o r d s ：s c h e d u l i n g ；a c t i v i t yf l o a t ；r e l a x a t i o nq u a n t i t y ；t a r d i n e s s 摘要 带有松弛变量的平行工序顺序优化的问题是指从n m 个独立进行的平行工 序中选择m 个调整为顺序工序链的优化问题。该问题恰是项目排序中考虑机动时 间和带有任意松弛变量问题中的一种。其自身的复杂性使得传统的运筹学中的线性 规划和启发式方法都不是解决该问题的较好的办法。本文针对该问题，针对网络中 工序本身具有的机动时间的特性。按照由此推导出的亏值定理从网络自身的规律出 发。推导出工序后移定理和最大亏值定理。在此基础上制定出合理的调整工序的目 标函数和每次选择调整工序的优化方法。最终解决了平行序链顺序化最优决策的问 题。在最优顺序链的基础上，调整得到整个序链全部工序顺序都优化过后的初始序 链。在此基础上，基于在初始序链的基础上通过删除合适的工序可以得到带有松弛 量的平行工序的顺序优化序链的想法。依靠推导出的去工序定理和最小亏值序链定 理给出了选择最优被删除工序的依据和方法。最终解决了带有松弛变量的平行工序 的顺序化优化问题。 关键词：排序；机动时间；松弛变量；亏值 a b s t r a c t t h ep r o b l e mo fm p a r a l l e la c t i v i t i e so fn mp a r a l l e la c t i v i t i e sb e i n ga d j u s t e dt oap r o c e d u r e c h a i ni so l l eo ft y p e so fp r o j e c ts c h e d u l i n gw i 也a c t i v i t yf l o a ta n da r b i t r a r yr e l a x a t i o nq u a n t i t i e s t h e c o n v e n t i o n a ll i n e a rp r o g r a m m i n go fo p e r a t i o n a lr e s e a r c ha n dh e u r i s t i ca p p r o a c h e sb o t hc a nn o ts o l v e t h i sp r o b l e mp e r f e c t l ys i n c et h ec o m p l e xo ft h ep r o b l e mi t so w n i na l l u s i o nt ot h i ss i t u a t i o n ，t h e a u t h o rd e d u c et h em a x i m u md e f i c i e n tv a l u eo fc h a i nt h e o r ya n dr e t r u s i v ea c t i v i t yt h e o r yd e p e n d o nt h em a x i m u md e f i c i e n tv a l u eb e t w e e n a c t i v i t yt h e o r yw h i c hi sp r o p o s e db yv i r t u eo ft h e c h a r a c t e r so ft h ef l o a tt i m eo ft h ew h o l en e t w o r k 。t h e nt h em e t h o do fg e t t i n gt h eo p t i m a lc h a i no f p a r a l l e la c t i v i t i e sc a nb eg i v e n a st ot h ep r o b l e mo fg e t t i n gt h es e q u e n c i n go p t i m a lm e t h o do f p a r a l l e l a c t i v i t i e sw i t hr e l a x a t i o nq u a n t i t i e s ，f i r s tw ec a ng e tt h ei n i t i a lc h a i nf r o mt h eo p t i m a lc h a i nb ys o m e a c t i v i t yo p t i m i z a t i o na d j u s t m e n to nt h ep u r p o s eo f g e t t i n gt h eo p t i m a lc h a i no f p a r a l l e la c t i v i t i e sw i t l l r e l a x a t i o nq u a n t i t i e sf r o mt a k i n go u tt h ep r o p e ra c t i v i t yo ft h ei n i t i a lc h a i na n db a s e do nt h em i n i m a l d e f i c i e n tv a l u ec h a i na n dt h er u l eo fp i c k i n ga c t i v i t yw h i c hw o u l db et a k i n go u t ，t h ea u t h o rf i n a l l y g i v et h ef o u r i d a t i o na n dm e t h o do fg e t t i n g t h eo p t i m a lc h a i no fp a r a l l e la c t i v i t i e sw i t hr e l a x a t i o n q u a n t i f i e s t h u s ，t h i sp r o b l e mc a nb es o l v e dp e r f e c t l y l uh a n ( a p p l i e dm a t h e m a t i c s ) d i r e c t e db yp r o f q i r o n gq i u k e yw o r d s ：s c h e d u l i n g ；a c t i v i t yf l o a t ；r e l a x a t i o nq u a n t i t y ；t a r d i n e s s 主要符号表 强：工序的最早开始时间 ：工序o 的最早结束时间 三岛：工序o 的最迟开始时间 弓：工序o 的最迟结束时间 巧：工序o 的机动时间 ：工序o 的前单时差 略：工序o 的前共用时差 喁：工序的后单时差 晖：工序o 的后共用时差 蜴：工序o 的后共用时差 职：节点。的后共用时差 肛：路线。 五：路线p 的长度即路长。 p ( 1 ，i ) ：源点与节点。之间路线。0 0 0 0 五( 1 ，f ) ：路线卢( 1 ，f ) 的路长。 p ( f ，w ) ：节点。与汇点之间路线。 五g 计：路线p ( f ，曲的路长。 以：源点与节点。之间的最大路长。 以：源点与节点。之问的最大路长所在的路线，又称节点。的前主链。 o “：节点。与汇点之间的最大路长。 “。：节点。与汇点之间的最大路长所在的路线，又称节点。的后主链。 p v ：关键路线。 p v ：最大路长。 如v ：过工序o 的所有路线中最大路长所在的老路线，或称过( 弛的特征路线。 心：过工序o 的任意路线。 华北电力大学 声明尸明 本人郑重声明：此处所提交的硕士学位论文带有松弛量的平行工序顺序化优化方法探 究，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工作和取得的研究成 果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得华北电力大学或其他教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名：一鞋监 日期：堕垒墨塑堕旦 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权保管、并向 有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手段复制并保 存学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交流为目的，复制赠送和交 换学位论文：同意学校可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：熟盗 日期：旦圣焦珏! 曼旦 导师签名：耳窟彰 日 期：一0 8 乡 华北电力大学硕士学位论文 引言 网络计划技术产生在2 0 世纪6 0 年代，最初只用于工期的管理。随着技术经济分析 的需要，引进了成本和费用率的概念，从而使网络技术可以更准确的进行概预算，有力 的控制工程的进度和成本。 项目管理尤其是项目进度管理与网络计划技术结合得非常紧密。当前，资源限制下的项 目进度管理( 例如工期最小化) 是项目管理研究的热点问题。资源限制的考虑使得原先 一些项目计划与控制中已成为体系的一些基本概念不再成立。例如，关键路线的概念， 它表示决定项目总工期的工序链，但在资源有限条件下它的这一特性也不再有效! 节点 松弛量与工序机动时间( 四种类型都包括) 的概念在该条件下也类似。关于这些概念在 考虑了资源限制的条件下不能在使用的例子，参见文献 1 】。 在资源限制条件下项目的分析与优化从存理论的角度来说是困难的，从管理的角度 来也是一样。现在已经普遍的认识到，工序排序与资源的适时获得和分配是管理中最重 要的因素。从学术上说，与任意服从资源限制的紧前关系有关的工序排序是n p h a r d 问 题【1 1 】。这意味着寻找该问题最优解( 在任意标准下) 的多项式和花费“最合理”的时 间的观点在大规模的项目中几乎不可行。它解释了( 在运筹学研究者头脑中的观点也是 一样的) 电脑研究方法的使用( 例如，基于计算机可行性的启发式算法，如神经中枢网 络，遗传算法，t a b u 研究，模拟退火) 和枚举法( 分枝定界法) ，等等。 从管理者的角度来看，问题的现实表现难于对定量分析进行准确描述，即使对于描 述起来充分且准确的数学模型来说，对该问题的描述也是有难度的，更不用说解决该问 题了。有关该问题难度性质的更详细的阐述，参见文献 1 】。 平行工序的顺序优化问题是指在资源受限的条件下，将项目施工过程中原本独立进 行的平行工序调整为顺序工序链，使得项目计划总工期推迟最少的问题。该类问题一直 是网络计划优化理论研究的焦点之一。 带有松弛变量的平行工序顺序化优化问题是指从个性质相同的平行工序中选择 m ( m j r ) 个工序调整为顺序工序链的优化问题。从个平行工序中选择m ( 膨s ) 个工序调整为顺序工序链的优化问题是考虑机动时间和松弛变量的平行工序顺序优化 问题的一种，该问题也是一个典型的项目排序问题。但在排序问题的研究中，n p 难解性 是其面临的一个棘手问题。如著名的货郎担问题，就是一个典型的n p c 问题。而n p c 问题至今为止还未找出多项式算法。从个平行工序中选择m ( m ) 个工序调整为 顺序工序链的优化问题的枚举量是c 孑m ! 。这远远大于货郎担i 口- j 题的枚举量m ! ( 必是 城市个数) 。所以该问题的求解非常困难。 在国内，平行工序的顺序优化问题被称为单个工序链的顺序优化问题圆，单个工序链的 优化问题包括两个平行工序的顺序优化口1 ，三个平行工序的顺序优化h 1 ，一直到膨个平 行工序的顺序优化。针对此类问题，可以考虑利用解析法和启发式算法来求解哺- 7 1 。但 是解析法要求把问题化为整数规划模型，一个节点对应一个不等式约束，一个工序对应 一个等式约束。要将整个网络中的节点与工序都化为线性约束，由此得到的整数规划模 型约束条件会很多，模型非常复杂。事实上，整数规划的判定问题本身也是n p c 问题阳1 。 在国外，该类问题是项目排序中机器排序问题b 一训。文献 9 已经提到网络排序技术 可能在机器排序问题中的应用，但缺少对它们应用的描述：文献 1 0 在研究项目排序中 华北电力大学硕士学位论文 的机器排序时采用了析取图法，但它只适用于小型网络。文献 1 1 给出了用网络计划技 术来解决该类问题的启发式算法，它的局限性是没有考虑到网络中每个工序的机动时 间。而工序的机动时间反映了所有前继后继工序对该工序的影响，反映了排序对象和周 围的联系。对于平行工序的顺序优化问题，每个工序的机动时间是一个非常重要的参数， 因此考虑机动时间的平行工序的顺序优化决策问题就显得非常重要。 可见传统的启发式算法和运筹学中的整数规划方法都不能较好的平行工序顺序化 这类问题。本文在考虑工序机动时间的基础上，基于文献 11 的基本定理，和由此推导 出的亏值定理，依据网络自身的特点和规律，推导出了一系列相关的定理。( 最大亏值 定理，后移工序定理，最小亏值序链定理，去工序定理) 从而彻底解决了平行工序顺序 化最优决策问题以至带有松弛变量的平行工序顺序化优化问题。这两个问题是平行工 序顺序化优化的典型代表问题，也是其中涵盖面最广的两个问题。此问题的解决，对平 行工序顺序化优化决策理论的发展有很大的帮助。从一个全新的角度去解决当今运筹学 中的难点问题，具有极高的原创性和创新价值。本文主要分为五部分。第一部分和第二 部分主要介绍文献 11 中的基本概念和基本定理。第三部分主要论述平行工序顺序化最 优决策问题的解决。第四部分侧重于解决带有松弛变量的平行工序顺序化优化问题。第 五部分为主要结论和后续需研究的问题。 华北电力大学硕士学位论文 1 1 引言 第一章基本概念 本章最开始介绍网络技术中的一些关于时间参数的基本概念，在此基础上主要介绍文献 1 ( 乞建勋1 9 9 7 ) 中网络新优化理论的新的重要概念以及基本定理，包括：路长定理 与机动时间定理等。从而奠定新优化理论的方法基础。 1 2 基本概念 1 2 1 、基本概念 ( 1 ) 网络计划图：由圆圈和箭线组成的代表一项工程计划的图。 ( 2 ) 工序：即图中箭线。代表一项工程中的一道工艺过程或局部工作。即消耗时间也 消耗资源。一般用大写字母表示，或用箭线两端的圆图表示。同一通道上的两个的工序 之间无其它工序称他们为紧前紧后的关系；否则称为前继后继的关系。 ( 3 ) 节点：即图中圆圈。代表工序可能的开始时间或结束时间。一般用来表示。同一 通道上的两节点之间无第三个节点称其为紧前紧后的关系；否则称为前继后继的关系。 总开始的节点叫源点；总结束的节点叫汇点。 ( 4 ) 工序的工期：完成工序消耗的时间称为工序的工期，记为瓦或l 。 ( 5 ) 路线：从源点开始顺着箭线方向直到达汇点的一条通道，叫一条路线。路线上 每个工序的工期之和成为该路线的路长。记为p 。全部路线中最大路长的路线称为关键 路线。关键路线上的工序称为关键工序。总工期等于关键路线的长。 3 华北电力大学硕士学位论文 1 2 2 、基本作图规则( c p m 网络) ( 1 ) 网络中不允许有回路。 ( 2 ) 紧前工序全部结束后，紧后工序才能开始。 ( 3 ) 箭线与工序一一对应。 ( 4 ) 相邻两节点之间只允许有一道工序。 ( 5 ) 源点与汇点唯一。 1 3 时间参数 网络计划技术是系统工程的方法，它研究问题从全局出发，从局部与周围环境的联系中 去把握事物。时间参数正是一个局部的工序与周围的环境以及与全局联系的一种具体描 述，因此，研究时间参数就是研究局部与整体的关系。网络计划技术的优越之处皆从时 间参数而来。因此，研究网络的时间参数是网络计划的中心任务之一。 1 3 1 、最早时间参数 最早时间参数主要反映一个工序与前继工序的关系。它有三个时间参数：工序的最 早开始时间，工序的最早结束时间，节点的最早开始时间。 ( 1 ) 工序的最早开始时间 在网络计划中，工序最早可能的开始时间，记为e s o 或e s a ( 2 ) _ 7 2 序的最早结束时间 在网络计划中，工序最早可能的结束时间，记为砸，或e f a 工序的最早开始时间加上该工序的工期就等于该工序的最早结束时间。即： e f a = e s a + l 根据c p m 网络图的作图规则( 2 ) ，只有工序( 妁的全部紧前工序都结束后，该工序 才能够开始。所以工序。( d 得最早开始时间等于其全部紧前工序最早结束时间的最 大值，即 e s o = m a x e f 毛j ，e 吃护，e f , 。f ) ( 卜4 1 ) 因o o 与o 相同的紧前工序，所以0 码= 强 ( 卜4 2 ) 即共开始节点的工序最早开始时间相等。 ( 3 ) 节点的最早开始时间 某节点的任一紧后工序的最早开始时间，称为该节点的最早开始时间，也是该节点 的开始时间。显然 j z s , = e s 口 由式( 卜4 - 1 ) 可推知 4 ( 1 - 4 - 3 ) 华北电力大学硕士学位论文 e s , = m a x e f k , f ，必：f ，e f t ，) ( 卜4 4 ) 即节点的最早开始时间等于其紧前工序最早结束时间的最大值。 1 3 2 、最迟时间参数 最迟时间参数主要反映工序与其后继工序之间的相互关系。它也有三个时间参数： 工序的最迟开始时间，工序的最迟结束时间，节点的最迟结束时间。 ( 1 ) 工序的最迟开始时间 在不影响总工期的前提下，工序最迟可能开始的时间。记为墨i 或三s ( 2 )工序的最迟结束时间 在不影响总工期的前提下，工序最迟可能的结束时间。记为l 鼻，或矾。 工序的最迟结束时间减去工期就等于工期最迟开始时间，即 三e = 叱一l 由定义可知，当工序不能在最迟结束的时间结束或不能在最迟开始的时间开始， 则总工期必定要推迟。 根据作图规则2 ，紧前工序全部结束后，紧后工序才能开始。因此，工序的最迟 结束时间应当等于其紧后工序最迟开始时间的最小值，即 珥= m a x l s j 屯，三，l ) ( 卜4 5 ) 因为结束节点相同的工序都有相同的紧后工序，所以 珥= 三磊。 ( 卜4 6 ) 即共结束节点的工序，最迟结束时间相同。 ( 3 ) 节点的最迟结束时间 节点的任一紧前工序的最迟结束时间称为该节点的( 最迟) 结束时间。即 蜗= 三弓 ( 卜4 7 ) 由( 卜4 - 5 ) ，( 卜4 - 7 ) 得 三弓= m i n t s j k , ，上如，工屯) ( 1 4 8 ) 节点的最迟结束时间等于今后工序最迟开始时间的最小值。 1 4 机动时间参数 现代项目管理中，在项目前期及项目进行过程中，对项目做进度计划和控制是非常 重要的。网络计划( c p m ) 是进行项目进度计划和控制过程中非常重要的工具，而机动 时间又是c p m 网络中的关键参数，它从全局考虑项目中各工作间的关系，与其他参数 相比，具有更好的可以从全局把握各工作间关系的性质。在工程项目施工过程中，考虑 到不推迟总工期的条件下，每个工序所拥有的空闲时间( i d l et i m e ) ，机动时间就作为其 衡量的尺度。对于时差的研究从五十年代后期就已经开始了。b a t t e r s b y ( 1 9 6 7 ) 和t h o m a s 5 华北电力大学硕士学位论文 ( 1 9 6 9 ) 给出如下四个概念：总时差( t o t a lf l o a t ) ，安全时差( s a l t yf l o a t ) ，自由时差 ( f r e ef l o a t ) 和独立时差( i n t e r f e r e n c ef l o a t ) ；e l m a g h r a b y ( 1 9 7 7 和1 9 9 5 ) 给出了这四 个时差的分析和陈述。但是针对网络本身的复杂性，这四个时差还不足以反映出工序之 间时差的内在联系，本章中作者又给出了前共用时差和后共用时差的概念，并为了概念 的系统性，把安全时差更名为前单时差，自由时差更名为后单时差。自从这两个时差的 引入，使得c p m 网络中，紧前和紧后工序的时差关系变得清楚起来。 1 4 1 总时差 工序( f ，) 的最迟结束时间减去最早结束时间称为工序( f ，) 的总时差，记为碣或矾。 码= 珥一珥 ( 1 - 5 - 1 ) 1 4 2 前共用时差( 前干扰时差) 一个工序与它的紧前工序所共享的机动时间，该时差的使用影响紧前工序的机动时 间。 l f = l f n - e s u ( 1 5 2 ) 略是工序“，) 和它的紧前工序( 七，f ) 可以共用的时差，若紧前工序( 七，力不用，( f ，力 可用，若紧前工序( 七，i ) 使用，则( f ，歹) 不能使用。记为 原来对机动时间的定义只考虑机动时间的使用对紧后工序的影响和对整个路线的影 响，本书中的定义考虑了机动时间的使用对紧前工序的影响。 工序( f ，j ) 的前共用时差是总时差的一部分，既是工序( f ，j ) 的总时差的一部分，又是 工序( f ，力的紧前工序( 七，i ) 的总时差的一部分 1 4 3 前单时差( 安全时差) 一个工序在不影响该工序最迟开工条件下所拥有可利用的机动时间的最大值，该时 差的使用不影响紧前工序的时差。记作厶喁。 喁= l s , j - l f 盯 ( 1 5 3 ) 1 4 4 后共用时差( 后干扰时差) 一个工序与它的紧后工序所共享的机动时间，该时差的使用影响紧后工序的机动时 间。记作玛 6 华北电力大学硕士学位论文 蝎= 嵋一脚 ( 1 - 5 - 4 ) 玛是工序( i ，歹) 和它的紧后工序o ，足) 可以共用的时差，若工序，力不用，( 五足) 可 用，若工序( i ，j ) 使用，则u ，k ) 不能使用。 工序o ，歹) 的后共用时差是总时差的一部分，既是工序( i ，) 的总时差的一部分，又是 工序( f ，j ) 的紧后工序( ，k ) 的总时差的一部分。 1 4 5 后单时差( 自由时差) 一i 、上厅征个影啊菜后上厣最早口j 再邑升工条件f 所拥有可利用的机动时间的最大 值，该时差的使用不影响紧后工序的时差。 、 f f x = e s i k 一晖 ： 卜珥一 ： i 。扣舛叫 汗i 一h i ：卜弘叫j 6 哦矾 ( 念( 焉 坞 珥 ， 1 4 6 相邻两工序问机动时间的关系 由图1 5 1 可以看出： ( 1 ) 工序“，) 的前共用时差玛先用，前单时差后用。 ( 2 ) 工序( 七，f ) 的后单时差用学先用，后共用时差蜴后用。 ( 3 ) 节点( f ) 的时差( 奶一磷) 既是紧前工序( 七，i ) 的后共用时差吗厶，也是紧后工 序o ，力的前共用时差吗，即三巧一e s = 群= 略。从图2 3 1 可以看出，这部分机 7 华北电力大学硕士学位论文 动时间( 尼，i ) 使用完，则( j ) 就不能再使用；若( 七，i ) 不使用，则( f ，j ) 可以继续用，所以 称为共用时差。 推论1 若哦甄j ，n = l ，2 ，3 ，则砰= o ，即共结束节点的工序中，最早结束时 间最大的工序，其后单时差必定为零。 证明磷= m a ) 【 犯l f 吒，甄，甄，) 7 e s j = n 墙x 媾f u ，e f k 。，e f q ，e f t 。j ，e f , j = e f 。 所以 f f 拿= e s j e f = e f 一e f = 0 推论2 若三s 冬三，万- 1 ，2 ，3 ，则喁- - 0 ，即共开始节点的工序中，最迟开始时 间最小的工序其前单时差为零。 证明由三弓= m i n t s i , ，三- ，三跣 ， 可知= 觚n 犯岛，三黾，三黾，三黾， - 三岛 所以 f f 4 = l s4 一l f i = l s 4 一l s 4 = 0 1 4 7 机动时间使用的方式 人们习惯上都认为，j 个工作的机动时间是可以任意使用的。例如，某工作的机动 时间是1 0 天，则该工序的工期延长七八天甚至1 0 天都可以不管，只要不超过1 0 天， 都不对总工期造成影响，总工期都不会推迟。 事实上，总工期虽然不推迟，但该工序的某些后继工序的机动时间却要减少，尤其 是当该工序的机动时间( 1 0 天) 全部用完以后，它的一系列的后继工序会因此而变成新 的关键工序，从而大大地增加总工期推迟的危险性。 网络计划技术是系统工程的方法，研究问题是从全局出发，从局部与周围环境的联 系中去把握事物。时间参数是一个局部的工序与周围的环境以及与全局联系的一种具体 描述，因此，研究时间参数就是研究局部和整体的联系，下面就是从时间参数方面来研 究机动时间的使用方式问题。 8 华北电力大学硕士学位论文 图1 5 2 图1 5 2 网络中的工序( 4 ，9 ) ，最早开始第5 天，工期2 1 天，最早结束第2 6 天；最迟 结束3 8 天，机动时间( 3 8 2 6 ) = 1 2 ( 天) 。 若工序( 4 ，9 ) 的机动时间全部用完，例如工序( 4 ，9 ) 的工期延长1 2 天，由2 1 天变成3 3 天，则( 1 ) _ ( 4 ) 一( 9 ) _ ( 1 1 ) _ 怒叶( 1 5 ) 的路长就变为6 0 天，因而成为新 关键路线，所以工序( 1 ，4 ) ，( 4 ，9 ) ，( 9 ，1 1 ) ，( 1 1 ，1 3 ) ，( 1 1 ，1 4 ) ，( 1 4 ，1 5 ) 就变为新关键工序。而关键 工序的工期每延长1 天，总工期就要延长l 天。因此，工程总工期被推迟的危险就大大 增加了。 例如，工序( 1 4 ，1 5 ) 最早开始时间4 8 天，最迟结束6 0 天，工期4 天，则最迟开始( 6 0 4 ) - - 5 6 ( 天) ，机动时间为( 5 6 4 8 ) = 8 ( 天) 。因此，在工序( 4 ，9 ) 的机动时间没有使用时， ( 1 4 ，1 5 ) 的工期延长五六天甚至8 天，总工期都不推迟。 但是当工序( 4 ，9 ) 的1 2 天机动时间用完之后，例如( 4 ，9 ) 的工期由2 l 天延长到3 3 天， 此时( 1 4 ，1 5 ) 的工期每延长1 天，总工期就延长1 天，( 1 4 ，1 5 ) 的工期若再延长8 天，总工 期就延长8 天。 因为路线( 1 ) 一( 4 ) 一( 9 ) _ ( 1 1 ) _ ( 1 4 ) _ ( 1 5 ) 的长就变成 5 + 3 3 + 8 + l o + ( 4 + 8 ) 】= 6 8 ( 天) ，比原来的关键路线 ( 1 ) _ ( 3 ) 一( 6 ) _ ( 8 ) 一( 1 0 ) _ ( 1 3 ) _ ( 1 5 ) 的长6 0 天还长8 天，所以总工期推迟8 天。 由此可见，机动时间的使用可能会大大增加总工期推迟的危险性，因而在对机动时 间的管理上，决不可能采取放任自流的方针，任其自由的使用。相反，在没有必要的情 况下，尽管有机动时间，也不能随便使用。 9 华北电力大学硕士学位论文 在网络优化的资源均衡时，使用机动时间降低费用是应该的。其实质是增加总工期 延期的危险，换取了费用的降低。 是否在所有的情况下，机动时间的使用都会引起总工期延期的危险呢? 也不一定， 下面分情况讨论这个问题。 ( 1 ) 当某工序的后单时差为零，则此时全时差等于后共用时差，因而该工序的机动时 间使用l 天，则紧后工序的机动时间减少1 天。所以，这种情况下，机动时间的使用必 然增加总工期被推迟的危险。 例如，工序( 6 ，9 ) 的最早开始时间是第9 天，工期是2 l 天，则最早结束时间为( 2 l + 9 ) = 3 0 ( 天) ，等于工序( 9 ，1 1 ) 的最早开始时间3 0 天。( 6 ，9 ) 的最迟结束是第3 8 天，所以机 动时间为( 3 8 - 3 0 ) = 8 ( 天) 。同理，( 9 ，1 1 ) 的机动时间为 4 6 一( 3 0 + 8 ) 】- 8 ( 天) 。( 6 ，9 ) 的机 动时间每使用1 天，即( 6 ，9 ) 的最早结束每推迟1 天，( 9 ，1 1 ) 的最早开始和最早结束也都 要推迟l 天，因而( 9 ，1 1 ) 的机动时间也要减少l 天。尤其是当( 6 ，9 ) 的机动时间使用8 天， 则( 9 , 11 ) 的机动时间也减少8 天，变为( 8 8 ) ：0 ，因而成为新关键路线：因此总工期被 推迟的危险性越来越大。 ( 2 ) 当工序a 的后单时差砑 0 1 ) a 的实际开始时间e = 哦，则在最初的丹斧天的机动时间里，机动时间的使用 不增加总工期被推迟的危险性。 2 ) 当l e s a ，则 剧芽一( 墨一鹦) 】天内，机动时间的使用不增加总工期被推迟 的危险性。 例如，( 1 ，4 ) 如果在最迟结束时间第7 天结束，而( 4 ，9 ) 实际上只能在第7 天开始，而 ( 4 ，9 ) 的最早开始时间是第5 天，所以( 4 ，9 ) 的最早开始时间被推迟( 7 5 ) - 2 ( 天) ，( 4 ，9 ) 的后单时差职拿，) = 硒一职。9 ) = 3 0 - ( 2 1 - 1 - 5 ) = 4 ( 天) 。所以在( 4 2 ) = 2 天时间内机 动时间的使用不增加总工期被推迟的危险性，即( 4 ，9 ) 如果在第8 天开始或者第9 天开 始，紧后工序的机动时间都不减少，因而总工期被推迟的危险性不增加。 因此就一般情况而言，机动时间的使用大都会减少紧后工序的机动时间，是总工期 被推迟的危险性增大。所以对机动时间的使用必须加以控制，决不可采用放任自流的管 理方式。 l o 华北电力大学硕士学位论文 2 1引言 第二章基本定理 在网络计划的研究中，传统的数学显得无能为力。因为网络是由工序组成的，而工序 之间的时间、费用等参数是彼此独立的，本质上它需要一种离散数学的工具，传统的 连续数学将无能为力，但现在的离散数学研究的对象又不是网络计划图，因而不能能适 应它本身的特点，所以也无能力解决网络计划研究中出现的问题。若把它归结为线性规 划问题又将产生大量的约束条件，使计算工作量十分巨大。我们从网络计划图自身的规 律出发，建立了一套理论和方法，并在一系列的网络研究中取得了大量的突破。 2 2 路长定理及其推论 引理1 设任意节点。与源点z f - j 的任意路线为 叫9 文k 弘电卜叫分争卜囝 那么我们可得路长为 p ( 1 ，d = 砖一哦 ( 2 1 - 1 证明由码= e s , ，e f , j = 砖十弓 可得f f 譬= e s j e f 4f f 拿= e s j e s 4 一t 所以 f f 惫n = f f 会+ f f 瓮j rf f 怠+ f f 釜+ 。f f 拿七f f 瓮+ f , f 弘a + f f 会 = ( e 咒二- e s , 一石。) + ( e 咒一e s o 一互6 ) + ( e 蔓一e 叉一) + ( e 兄一e 叉一乙) + + ( e 墨一e s 一乃) + ( e 一e s ：一) + ( e 甄一e s 一巧) + ( e 霉一g s 一五，) = e s , 一e s , 一五。一一一一巧一一乙一瓦 因为 e s , = 0 p ( 1 ，i ) = 瓦+ 死+ + 乙+ + 乃+ + 乙+ t m 所以f 嗡。o = 砖一p ( 1 ，力，即可得p ( 1 ，o = e s , - f 磺力。证必。 推论1 令= ，则五( 1 ，w ) = 矾一f f ：= 墨一f f ： 即任意一条路线的路长都等于总工期减去这条路线的后单时差。 引理2 设任意节点o 与汇点之间的任意路线为 华北电力大学硕士学位论文 f 叫9 h 弘一h 9 叫争 溯 则路长 p o ，叻= e 一奶一f ( f ( 2 - 1 - 2 ) 证明：因为岛= 嵋一毛可得f f o = l s o l f ,= 三巧一l f , 一乃 所以 f f 心n = f r a + 。f f 啦七。f f k + 凸f f d + ，f f 哆七。f f f g + f f 咖+ f f 啦。 = ( z f , 一必一毛) + ( 三最一三弓一) + ( 奶一z f , 一乃) + ( 三一l f , 一) + + ( 三c z f , 一z ，) + ( l e l f , 一瓦) + ( l e l f 一乙) + ( 三e 一三c l ) = l 凡一三f p ( f ，们 所以卢( f ，w ) = c 一三e 一，：( l 蝴 推论2 令。，则五( 1 ，w ) = 玩一职一以而媚= o ，l f w = e s , 即 芦( 1 ，计= 墨一晖 即任意一条路线的路长都等于总工期减去这条路线的前单时差。 路长定理设过工序的任意路线 则路长 i z ( i ，j ) = l f 。- t f 穿一，e ( 1 ) 一，( 帅 证明：由引理1p ( 1 ，f ) = e s , 一f 喘f ) 和引理2i - t ( i ，w ) = l f - l f , 一晖( 。 因为路线 p ( f ，歹) = p ( 1 f ) + ( f ，) + p ( f ，w ) 所以路长五o ，- ) = 砘i ) + t c + - p ( i ，w ) = e s , 一麟，) + 毛+ 矾一弛一6 砜 而 e s , + 乃。一l f , = 一珥 由此可得肛( f ，j ) = l f w - - 码一f 碥力一晖( 五砷。 定义当用谂，) = o ，则称p ( 1 ，f ) 为节点的前主链，记为心。 当矾( 呐= o ，则称p ( 五计为节点的后主链，记为一。 1 2 ( 2 1 - 4 ) 推论3 以= 砖，节点的前主链的长度就是节点的最早开始时间。 推论4 肛，p ( 1 ，d 即节点的前主链是节点与源点之间路长的最大路线。 一0 推论5 i t ，= l f - t e = 一三鼻，节点的后主链的长度等于总工期渐趋节点的 最迟结束时问。 一o 推论6 弘，卢o ，叻。即节点与汇点之间最长的路线就是节点的后主链。 2 3 机动时间定理及其推论 机动时间定理通过任工序瓴力的路长最大的路线如v 与关键路线p v 的路长之差等 于该工序总时差，即 一v v 碣= p 一心