Ths s tral erson

Ths s tral erson 硕士学位论文 论文题目 工序网络图机动时间的研究 研究生姓名指导教师姓名专业名称研究方向 石浩闻振卫运筹学与控制论运筹学组合优化 论文提交日期 2013-6-19

Ths s tral erson

工序网络图机动时间的研究 摘要 摘要 在工程项目管理中, 网络计划技术 (CPM/PERT) 早已为人们所熟悉和广泛使用 一个工程项目总是由之间存在着一定的先后关系的一些工序 ( 也叫活动 ) 所构成 表示一个工程项目通常采用双代号或单代号网络图, 本文仅采用双代号网络图来考虑相应的管理问题 工序机动时间的研究是对项目的进度进行科学管理的基础 通常一个工序的工期延长会引起它的一些后继工序的机动时间的变化 我们知道, 一个工序的工期延长到一个阈值后, 它的后继工序的机动时间不再会随该工序工期的进一步延长而发生变化, 人们称这种性质为工序机动时间的守恒性 本文分析了工序机动时间的性质, 给出了工序机动时间守恒性的充要条件, 并举例对守恒性进行了具体地分析和说明 在双代号网络图中, 某个关键工序的工期压缩一个单位, 哪些以及多少工序的机动时间会受到影响? 压缩哪个关键工序能使机动时间受影响的工序个数最少? 本文也对此进行了分析讨论, 并得到相应的结论, 同时也用实例加以说明 关键词 : 网络计划技术 ; 双代号网络 (AOA); 机动时间守恒性 作者 : 石浩 指导老师 : 闻振卫 I Ths s tral erson

Abstract Stdy on Float n Actty Networks Stdy on Float n Actty Networks Abstract: The network plannng technqes (CPM/PERT) hae long been famlar to researchers and practtoners and hae been wdely sed n proect management. A proect conssts of acttes n whch there exst precedence relatons. Proects are sally denoted by actty on arc (or on node) networks (AOA or AON). Ths artcle ses only the AOA. The research on actty floats s one of the scentfc bases for proect management. Usally an extendng of an actty processng tme wll case float changes n some of ts sccessor acttes. It s well known that when the draton of an actty extends to a threshold, the floats of all ts sccessor acttes wll no longer change wth the frther extendng of ths actty draton. Ths phenomenon s called the conseraton of actty floats. In ths paper, the propertes of the conseraton of actty floats are analyzed, the necessary and sffcent condton for the conseraton of actty floats s proded and examples are gen to descrbe the conseraton specfcally. In the AOA network, f the draton of a key actty s compressed by one nt, whch and how many actty floats wll be affected? And whch key actty whose draton s compressed by one nt wll case the least nmber of acttes whose floats are changed. We wll dscss ths sse, prode the correspondng conclsons and ge llstratng examples. Key words: Network plannng technqes; Actty networks; Float conseraton Wrtten by Sh Hao Spersed by Wen Zhenwe II Ths s tral erson

Ths s tral erson 工序网络图机动时间的研究 目录 目录 第一章引言...1 1.1 网络计划技术概述...1 1.2 网络计划时间参数及计算...2 1.3 机动时间的基本概念...3 1.4 总时差定理...4 第二章工序机动时间的守恒性......6 2.1 工序机动时间守恒性的概念描述...6 2.2 机动时间守恒性的充要条件...7 2.3 算例...12 第三章工期压缩问题...14 3.1 问题简介及描述...14 3.2 网络图中只有 1 条关键路线...14 3.3 网络中只有 2 条关键路线的情况...19 第四章总结与展望...24 参考文献...25 致谢...26

Ths s tral erson

工序网络图机动时间的研究 第一章引言 第一章引言 1.1 网络计划技术概述 一个大型的工程项目往往由很多较小的工序组成 工序之间存在 着错综复杂的关系, 使协调管理的难度很大 管理人员为了对项目的 总体情况有较全面的了解进而有效地控制项目的进展, 必须借助科学 的管理方法 网络计划技术又称统筹法 ( 或简称 CPM/PERT) 是一个推动现代 项目管理发展的重要工具, 它是由美国杜邦公司于 1956 年提出的 [1] 随着理论方法的逐渐发展, 该工具得到了人们越来越多的使用 从上 世纪 60 年代起, 以 Battersby Elmaghraby 和 Thomas 等为代表的学 者们开始研究网络计划中机动时间, 并提出了目前国际上通用的五个 时差概念 [1]: 节点时差 (node float) 总时差 (total float) 自由时差 (free float) 安全时差 (safety float) 和干扰时差 (nterfere float) 此外, 在网 络计划中的时间参数的计算上, 针对双代号网络图可能存在虚出或虚 入节点所导致的时间参数计算出错的情况,Elmaghraby 和 Kambrowsk(1990) 提出了虚入节点和虚出节点时间参数的修正方法 [2] 现今网络计划技术已经广泛应用于大量的工程项目管理中, 同时 也极大地促进了项目管理技术的发展 1.1.1 符号与定义 用 本文的研究基于双代号 (AOA) 网络图 设 D 是一个工序网络图, t 表示工序 (, ) 的工期, 对于 D 上的一个节点 ( ), 我们分别用 P( ) 和 S ( ) 来表示节点 ( ) 的紧前节点集合和紧后节点集合, 分别用 ET 和 1 Ths s tral erson

第一章引言 工序网络图机动时间的研究 LT 表示节点 ( ) 的最早和最迟时间 分别用 ES EF LF LS 表 示工序 (, ) 的最早开始 ( 或开工 ) 时间 最早结束 ( 或完工 ) 时间 最迟 结束时间 最迟开始时间 称节点 ( ) 是节点 ()( ( ) ) 的一个后继节点是指, 存在一条从节点 () 到节点 ( ) 的路段 ; 我们把节点 () 的所有后继节点组成的集合记为 L () 对于一个给定的节点 ( ) 和它的某个后继节点 (), 我们用 μ 表示一条给定的从节点 ( ) 到节点 () 的路段 ; 用 μ 来表示一条给定的 关键路线 除了通用的概念与符号 [4] 外, 还涉及以下概念 定义 1.1 (1) 对于给定的节点 (), 其前主链定义为从源点 ( 1) 到节点 () 的 ( 任意 ) 一条最长路 ( 段 ), 我们用 μ - 表示其中给定的一条 (2) 节点 () 的后主链定义为从节点 () 到汇点 (n) 的 ( 任意 ) 一条最 长路 ( 段 ), 用 μ + 表示其中给定的一条 (3) 节点 () 的特征路线定义为由其前主链 节点 () 自己 和其后 主链组成的任意一条路线, 用 μ 表示其中给定的一条 (4) 一条路段 μ 的自由时差 FFμ 定义为该路段上所有工序的 自由时差之和 ; 一条路段的安全时差定义为该路段上所有工序的安全 时差之和 [6] 1.2 网络计划中的时间参数及其计算 1. 2.1 节点时间参数的计算及修正方法 (1) 节点时间参数的计算方法 [1] 1 对于 = 2, 3,..., n, 按下式依次计算节点 ( ) 的最早 2 Ths s tral erson

工序网络图机动时间的研究 第一章引言 时间 ET ET1 = 0 ET = max ( ) P( { ET + t } ) (1) 最迟时间 2 再让 = n - 1, n - 2,..., 1, 按下式依次计算节点 ( ) 的 LT LTn = ETn LT = mn ( k ) S ( { LT t } ) k k (2) (2) 节点时间参数的修正方法 [5] 1 从左向右依次检验, 若节点 ( ) 是虚入节点 ( 所有入弧都是虚工 序的节点 ), 按下式修正 : ( ) P( ) { } LT = max LT, = 2, 3,..., n - 1 (3) 2 再从右向左依次检验, 若节点 ( ) 是虚出节点 ( 所有出弧都是虚 工序的节点 ), 按下式修正 : = { }, = n - 1, n - 2,..., 2 (4) ET mn ET ( k ) S ( ) 1.2.2 工序时间参数计算方法 : k 工序 (, ) 的最早开始 ( 或开工 ) 时间 ES 最早结束( 或完工 ) 时间 EF 最迟结束时间 LF 最迟开始时间 LS 的计算方法如下 [6]: 1.3 机动时间的基本概念 ES = ET EF = ES + t LF = LT LS = LF t = ET + t = LT t (5) 在网络计划中, 传统的机动时间概念主要包括, 工序的总时差 ( 总机动时间 ) 自由时差 安全时差和节点时差等 下面分别给出这几 个时差的定义 [6]: 3 Ths s tral erson

第一章引言 工序网络图机动时间的研究 工序 (, ) 的总时差用 TF 表示 : TF = LS ES = LF EF = LT ET t (6) 工序 (, ) 的总时差的意义是, 当所有其他工序的工期保持不变, 在不影响总工期的条件下, 工序 (, ) 的工期的最大延长量, 或者说 工序 (, ) 可以任意使用的 ( 总 ) 机动时间的最大值 工序 (, ) 的自由时差 ( 后单时差 ) 用 FF 表示 : FF = ES EF = ET ET t (7) k 工序 (, ) 的自由时差的意义是, 当所有其他工序的工期保持不 变, 在不影响其紧后工序的最早开工时间的条件下, 工序 (, ) 的工 期的最大延长量 工序 (, ) 的安全时差 ( 前单时差 ) 用 SF 表示 : SF = LS LF = LT LT t (8) k 工序 (, ) 的安全时差的意义是, 当所有其他工序的工期保持不 变, 在不影响其紧前工序的最迟完工时间的条件下, 工序 (, ) 的工 期的最大延长量 节点 () 的时差 : TF = LT ET (9) 节点时差位于相邻的工序之间, 紧前工序对该时差的使用会对紧后工序的机动时间造成或多或少的影响, 同理紧后工序对该时差的使用同样也会对紧前工序的机动时间造成或多或少的影响 1.4 总时差定理引理 1[6] 对于任意的节点 (), 它的前主链上的所有工序的 4 Ths s tral erson

工序网络图机动时间的研究 第一章引言 自由时差均为 0; 它的后主链上的所有工序的安全时差均为 0 引理 2[6] 对于任意的节点 (), 它的前主链的路长等于节点 () 的最早时间 ; 它的后主链的路长等于关键路线的路长 ( 总工期 ) 减去节点 () 最迟时间 5 Ths s tral erson

第二章工序机动时间守恒性 工序网络图机动时间的研究 第二章工序机动时间守恒性 在工程项目管理中, 对工序机动时间的合理使用至关重要 我们 说某个工序使用了机动时间是指, 该工序的工期延长了一定的量, 并 且该延长量不大于该工序相应的时差 本章着重分析一个工序的工期 延长对后继工序的机动时间的持续影响 在机动时间的使用中, 当一个工序的工期的延长量超过该工序自 身的自由时差后, 它的后继工序的机动时间就可能会因此而发生变 化 那么, 随着一个工序的工期的延长量逐渐增大, 它的后继工序的 机动时间是否会持续发生变化呢? 事实上, 一个工序的工期的延长量 达到一定程度后它的后继工序的机动时间是恒定值 ( 不再会随延长量 的增大而发生变化 ), 这就是苏志雄 张立辉 李星梅等提出的工序 机动时间的守恒性 [3], 并且他们给出了一个机动时间守恒的充分条 件 本章给出了机动时间守恒的充分必要条件 这不仅解决了机动时 间守恒性的刻画问题而且即使针对充分条件也改进了他们的结果, 这 在理论上具有重要的意义 同时, 守恒性问题的解决在处理项目管理 中的机动时间使用和资源分配等方面, 能提供理论依据, 对管理者更 灵活地掌握和控制项目进程有很大帮助, 因此也具有重要的实际意 义 2.1 工序机动时间守恒性的概念描述 假定工序 (, ) 以外的所有其它工序的工期都保持不变 当工序 (, ) 的工期延长使其最早结束时间推迟, 那么它的后继工序的机动 时间 ( 各种时差 ) 可能会受其影响而发生改变 6 Ths s tral erson

工序网络图机动时间的研究 第二章工序机动时间守恒性 定义 2.1.1 假定除工序 (, ) 外, 所有工序的工期保持不变 当工序 (, ) 的工期延长到一定量后, 那么其所有后继工序的机动时 间都将保持恒定, 也就是说, 这些工序的机动时间都将不再随工序 (, ) 的工期的进一步延长而发生变化 这种现象叫作关于工序 (, ) 的工序机动时间的守恒性 [3] 研究机动时间守恒性是完善网络计划理论的一项有意义的工作 由于机动时间的守恒性通常是在总工期也延长的情况下表现出来的, 因此在这里, 我们重点分析某工序工期的延长对其后继工序机动时间 的影响, 而并不顾及工序工期的延长对总工期的影响 2.2 机动时间守恒性的充要条件 引理 3[6] 当工序 (, ) 的延长量大于等于自由时差 FF 时, 新得 到的网络图中工序 (, ) 的自由时差为 0 引理 4[6] 当工序 (, ) 的自由时差为 0 时, 则节点 () 的前主链过 工序 (, ) 引理 5[6] 对于一条自由时差为 0 的路段 μ, 节点 () 的前主链 过该路段 ; 对于一条安全时差为 0 的路段 μ, 节点 ( ) 的后主链过该 路段 假定除工序 (, ) 以外的所有其它工序的工期保持不变, 而工序 (, ) 的工期从 t 延长到 t (>t ) 记: FFμ Δ = max { FFμ } + FF (10) L ( ) 其中,μ 表示从节点 ( ) 到节点 () 的 ( 任意 ) 一条最长路段, 而 表示该路段上所有工序的自由时差之和 7 Ths s tral erson

第二章工序机动时间守恒性 工序网络图机动时间的研究 定理 对于任意给定的工序 (, ), 我们有以下的描述机动时间守恒性 定理 1 对于一个给定的网络图 D 以及任意一个给定的工序 (, ), 假设工序 (, ) 的工期延长量为 T, 而所有其他工序的工期保 持不变 则关于工序 (, ) 的工序机动时间守恒的充要条件是 : 证明首先证明充分性 ( ) T Δ (11) 设工序 (, ) 的工期已由原来的 t 延长成 t = t + T, 而所有其他 " " 工序的工期保持不变 把新得到的网络图记为 D 并把 D 的所有时 间参数符号均记为在原参数符号后加 (") 的形式 显然, 当工序 (, ) 的 工期延长量充分大时, 由前主链的定义可知, 在新得到的网络图中, 对于节点 ( ) 的每一个后继节点 (), 节点 的前主链过工序 (, ) 现 在设 T = Δ + ΔT ( ΔT 0) 为 D, 并尤其记当 T = Δ ( 即 Δ T =0) 时的网络图 对于节点 ( ) 的任一后继节点 (), 由式 (10) 中 Δ 的取法以及引理 4 可知, 存在节点 (w) 是节点 ( ) 的一个后继节点或 (w) = ( ) 使 : ( ) P( ) { ET + t } = max { EF } EF ET = max = ( ) P( ) 因为, 当工序 (, ) 的工期延长量超过其自由时差 FF 时, 工序 (, ) 自由时差已经使用完了, 由引理 3 和 4 可知 w EF = ET + t + Δ + ΔT = ET " 即 ET = ET + ΔT 8 Ths s tral erson ET + t + Δ = EF = ET

工序网络图机动时间的研究 第二章工序机动时间守恒性 对于节点 ( ) 的任一后继节点 (), ET = = max ( ) P( max ( ) P( ) = ET { ET + t} ) { ET + ΔT + t } + ΔT 其中归纳假定, 作为节点 的后继节点 () ( 或 () = ( ) ), 式 ET = ET + ΔT 已经成立 对于节点 (n) LT n = ET n = ET n + ΔT = LT n + ΔT 对于节点 ( ) 的任一后继节点 () LT = mn ( ) S ( ) { LT t } = mn { LT + ΔT t } = LT + ΔT ( ) S ( ) 其中归纳假定, 作为节点 的后继节点 ()( 或 () = (n) ), 式 LT = LT + ΔT 已经成立 由式 ( 6), 工序 (, ) 的后继工序 (, ) 的总时差满足 TF = LT = ( LT = TF = LT ET 9 Ths s tral erson + ΔT ) ( ET ET t t + ΔT ) t 类似地, 由式 ( 7) ( 8), 工序 (, ) 的后继工序 (, ) 的安全时差和自 由时差分别为 SF =, FF = SF FF 综上所述, 工序 (, ) 的后继工序的机动时间将不再随 Δ T 的增大 而变化, 体现了机动时间的守恒性 再证必要性 ( ) 由式 (10) 定义可知 Δ 0, 工序 (, ) 的工期延长量 T 0, 若 Δ

第二章工序机动时间守恒性 工序网络图机动时间的研究 = 0, 则 T Δ (= 0) 已成立 ( 事实上 Δ = 0 说明工序 (, ) 在关键路线 上, 那么显然工序 (, ) 的每个后继工序的机动时间都不随工序 (, ) 的工期延长而改变 ) 下设 Δ > 0 反证, 假定工序 (, ) 的工期延长量 T < Δ ( ΔT < 0) 形证明必要性 下面分两种情 情形 ( 1) 当 Δ = FFμ + FF n, 其中 μ n 表示从节点 ( ) 到节点 (n) 的 ( 任意 ) 一条最长路段, 所以由前主链定理, 此时我们有 所以 有 n n LT = ET = ET n ET n = ET n, 从而对任意的节点 ( ) L( ), 由后主链定理我们 LT = LT 所以由公式 ( 8), 对工序 (, ) 的任意后继工序 (, ), 我们 SF = LT LT t = LT LT t 即安全时差保持不变 当 FF μ 0 n, 在这个路线段存在最后一道自由时差不为零的工 序, 记为工序 (, ) 当工序 (, ) 的工期的延长量 T 满足 mn FF μ + FF < T < Δ 时, 由前主链定理我们有 ET = ET + Δ + ΔT mn FFμ FF ET = ET 从而由公式 ( 7) 有 10 Ths s tral erson