关键链汇入缓冲区的设置方法.docx

文章编号 :100725429 (2007) 0520051205关键链汇入缓冲区的设置方法徐小琴 , 韩文民(江苏科技大学 经济管理学院 , 江苏 镇江 212003)摘要 : 在介绍现有关键链 ( Critical c hai n sc he duli ng , CCS) 汇入缓冲区 ( Fee di ng b uff er ) 设置方法及其优缺点的基础上 ,提出一种改进的汇入缓冲区设置方法 。将汇入缓冲区的设置划分为汇 入位置和汇入缓冲区大小的确定 ,并分析了缓冲区设置过程中的资源冲突问题 。关键词 : 关键链 ; 汇入缓冲 ; 资源平衡中图分类号 : F224文献标识码 : AThe Sett ing Study f or Feeding Buf f er of Crit ical Cha in Schedul ingXU Xiao2qi n , H A N We n2mi n(J ia ng su U niver sit y of scie nce a nd t ec h nolo gy , Zhe njia ng 212003 , Chi na)Abstract : Ba sed o n t he set ti ng st udy fo r f eedi ng buff e r of critical chai n scheduli ng a nd it s merit s a nd pitf all s , t hi s p ap er develop s a n a dva nce d met ho d of f eedi ng buff e r . The set ti ng off eedi ng b uff er i s divi ded i nto co nfi r mi ng of f eedi ng po sitio n a nd buff e r size , t he n t he re so urce co n2f lict i n set ti ng p roce ss i s a nal yze d.Key words : critical chai n scheduli ng ; f eedi ng buff er ; re so urce bala nce两种设置方法 :剪切粘贴法 2 ( Cut a nd Pa st e Met h2o d) 和根方差法 2 ,3 ( Roo t Squa re Er ro r Met ho d) 。(1) 剪切粘贴法剪切粘贴法的具体做法是 :根据传统方法估计 项目中每项作业的执行时间 , 然后从每项作业执行时间中消除安全时间j , 并根据消除后的执行时间 进行项目调度 , 最后将非关键链上作业被剪掉的安全时间总和的 1/ 2 作为非关键链的汇入缓冲 , 即引言对不确定因素的有效管理是关键链的最大优 点 。CCS 应用了 风险 聚 合的 统计 学 原理 1 ,2 , 将 传 统项目管理中单个作业考虑的安全时间“聚 合”起 来 ,置于作业“链”之后 , 这样可 以有 效缩 短安 全 时 间 ,从而缩短项目总周期 。CCS 根据统计学 原理 , 通过在非关键链的末尾设置时间缓冲区 ,最大限度 地减少非关键性作业的延误对关键性作业所造成的 影响 ,提高非关键链不“碰撞”关键链的概率 ,从而提 高整个项目的完工概率 3 。将关键链看成是作业的 组合 ,而不是作业的序列 4 。也就是说 ,关键链不仅 可以是串连结构 ,还可以是串并连混合结构 ,这有利 于对问题的系统处理 。在对待非关键链时同样也存 在这样的问题 。11jFB I =( 1)2j I式 ( 1) 中 I 是非关键链上作业的集合 , FB I 表示设置在非关键链后的汇入缓冲区的大小 。( 2) 根方差法根方差法的具体做法是 :首先用两种方法估计 各项作业的执行时间 , 采用传统方法估计作业 j 的执行时间记为 s j , 采用关键链方法估计作业 j 的执 行时间是 a j , 两者之差为现有汇入缓冲区设置方法依据现有的资料 ,关于 CCS 汇入缓冲区大小有2j则项目缓冲区大小为= sj - aj( 2)收稿日期 :2006210210 ; 修回日期 :2006212210作者简介 :徐小琴 ( 19812) , 浙江衢州人 , 硕士研究生 , 主要研究方向为工业工程与供应链管理 。业 X 的持续时间和消耗的资源均为 0 ,即为虚作业 。2jFB =( 3)资源 R1 、R2 、R3 的可用量均为 1 个单位 。表 1 项目信息j CC非关键链 I 的汇入缓冲区大小为2jFB I =( 4)作业持续期所用资源工艺紧后作业j I剪切粘贴法的优点是简单易行 , 缺点是缺乏理论依据 , 容易产生缓冲区过大或过小的现象 。缓冲 区过小的情况发生在非关键链上的作业较少时 。假 如一条非关键链只有一个作业 , 它的安全时间是 a ,根据剪切粘贴法 , 在这个作业后设置的缓冲区大小 为 a/ 2 , 这样 , 这个作业冲击关键链的可能性就变大 了 , 这显然对项目的完成不利 。根方差法与剪切粘贴法比较 , 主观盲目性要少 一些 , 从某种程度上避免了管理者与执行者之间在时间估计上的矛盾 。根方差法同样会犯缓冲区过大 的毛病 , 但避免了缓冲区过小的毛病 。作业号安全时间AB C D E F GH69548735R3R1R1R3R3R1R2R234224312XD E F G H H X 0 0 0 D 汇入缓冲区的设置CCS 认为 ,缓冲区 应该 设置 在“非关 键链 汇 入 关键链的位置”,但对于什么样的位置是“非关键链 汇入关键链的位 置”没有 详细 说 明 。因 此 , 现 有 的 CCS 文献将“非关键链汇入关键链的位置”简单地 理解为在项目网络图中非关键作业与关键作业有工 艺约束的地方 。然而 ,这样的理解却忽视了资源约 束的存在 。综合上述问题 ,要完成汇入缓冲区的设 置 ,需要分别确定汇入位置以及缓冲区大小 。3图 1 项目网络图为便于说明问题 ,采取的例子是一个简单的项目案例 ,其关键链的识别依据文献 4 的关键链识别 方法 ,文中所举例子的关键链可以简单地由两个可 行进度得出 ,其可行进度 S 和 S ( 甘特图) 是综合考 虑工艺约束和资源约束的条件得出的 。例如 ,作业 B 和作业 C 不存在工艺约束 ,但是由于都需要资源R1 ,而本文预先假定的资源 R1 只有 1 个单位的可 用量 ,所以当先安排作业 B 时 ,作业 C 必须等待作 业 B 完成后释放出资源 R1 ,才能进行 ;反之 ,将作业 C 先安排时 ,作业 B 必须等待作业 C 完成后才能进 行 。再如 ,作业 E ,其工艺约束为作业 C ,但是由于 作业 D 和作业 E 都需要资源 R3 ,而本文预先假定的资源 R3 只有 1 个单位的可用量 ,作业 D 占用了 资源 R3 后 ,作业 E 就必须等待作业 D 完成后释放 出资源 R3 才能进行 ,所以作业 E 与作业 D 存在资 源约束 。可行调度计划不是唯一的 ,只要同时满足 工艺和资源的约束即可 。首先生成一个以最早时间开始的可行调度计划 为 S = (0 ,0 ,9 ,9 ,14 ,14 ,22 ,25) ,其计划长度为 30 ,甘特图如图 2 所示 。最晚时间 开 始 的 可 行 调 度 计 划 S= ( 4 , 0 , 9 ,3 . 1汇入位置的确定在资源受限情况下 ,因为资源约束与工艺约束同样会影响计划的执行 ,所以在某个特定的调度计划中 ,决定各个作业执行的先后顺序不仅由工艺约 束决定 ,同时也受到资源约束的影响 。本文在补充 借鉴文献 5 的基础上 ,将“紧后作业”的概念分为工 艺紧后作业和资源紧后作业 。由于资源紧后作业与可行调度计划密切相关 ,不同的调度计划其资源紧 后关系也不同 。资源紧后作业的概念首先是指在特 定调度计划 S 中 , 忽略各个作业之间的工艺约束关 系 , 当作业以最晚时间开始 , 所有因为资源冲突而阻 碍作业 j 不能以更晚的时间执行 , 并且最晚开始时间等于作业 j 的最晚结束时间的作业称为最晚时间 资源紧后作业 ;而作业以最早时间开始则称之为最 早时间资源紧后作业 。下文以例 1 的分析来具体阐述汇入位置的确 定 。例 1 , 一个项目由 9 个作业组成 ,其详细信息如表 1 所示 ,其项目网络图如图 1 所示 。在表 1 中 ,作10 , 14 , 18 , 22 , 25) , 其计划长度为 30 。此时 S 和 S 的计划长度不变 , 均为 30 。计算总时差 T S = ( 4 ,0 ,0 ,1 , 0 , 4 , 0 , 0 ) ; 得 到 关 键 链 为 : B C E G H , 而本例的关键路径为 :B D F H ,关键链与关键 路径是不相同的 ,其主要区别是关键路径仅考虑工艺的约束关系 ,而关键链则同时考虑了工艺和资源 的约束关系 ,详见文献 6 。由以上分析得出汇入位置的判定准则 :使各个 作业以最晚时间开始 , 如果非关键性作业 j 的结束 时间等于某一关键性作业的开始时间 , 并且该关键性作业是作业 j 的工艺紧后作业或最晚时间资源紧后作业 , 则作业 j 之后为汇入位置 。使例 1 中各个作业以最晚时间开始 ,画出甘特 图 ,如图 3 所示 。则汇入点的确定分析如下 :( 1) 非关键性作业 D 的结束时间等于关键性作业 E 的开始时间 ,且作业 E 是作业 D 的最晚时间资 源紧后作业 ,故作业 D 之后是汇入位置 ;(2) 非关键性作业 F 的结束时间等于关键性作 业 H 的开始时间 ,且作业 H 是作业 F 的工艺紧后 作业 ,故作业 F 之后是汇入位置 。图 2以最早时间开始的可行调度计划 S图 3 汇入点的确定非关键链时应对汇入位置前的作业包括工艺约束和资源约束下的作业进行分析 ,将汇入位置 j 前面的3 . 2汇入缓冲区大小的确定(1) 非关键链的确定非关键性作业 i 左移一个单位时间 , 作业 i 和所有因为工艺约束或资源约束必须也左移一个单位时间 的作业都属于汇入位置 j 的非关键链 。如例 1 中 ,汇入位置 1 的非关键链为 A D ; 汇入位置 2 的非 关键链为 F 。在分析汇入缓冲区大小时 ,回顾原有的剪切粘贴法和根方差法 ,为防止根方差法设置缓冲区容易 过大的缺陷 ,本文引入了非关键作业自由时差概念 , 以控制缓区的大小 。现有的 CCS 理论对非关键链的确定没有论述 ,而事实上 ,汇入缓冲区是为非关键性作业提供缓冲 服务的 。不同的非关键链其后的汇入缓冲区大小也 有一定的区别 ,确定非关键链的目的是为了根据非关键链的特点计算汇入缓冲区的大小 。现有的 CCS 理论在确定非关键链时采用的是 观察法 ,这种方法在小型项目中或结构简单的项目 网络图中是有效的 ,对于大型项目 ,本文认为在确定(2) 非关键链标准方差的计算概率论中的“标准方差”概念为汇入缓冲区大小 的确定提供了参考 。例如 , 对于正态分布的随机数 X , 记均值为 , 方差为, 则随机数 X 小于 +的 概率为 :由时差往往不同 , 因此 , 讨论自由时差的计算 , 必须是在某一特定调度计划中 , 在不影响所有工艺紧后 作业和最早时间资源紧后作业 的开 始时 间 的前 提 下 , 某一作业相对于其最早时间可以推迟的时间量 称为作业的自由时差 7 ( Free Slac k) 。针对某一调度计划的某一作业的自由时差可以 根据式 ( 9) 计算 。+ 1 ( t - ) 2= - e -P X +22 d t 0 . 84 5( )2式 ( 5) 用在汇入缓冲区大小的确定中的含义是 :如果汇入缓冲区的大小等于非关键链的标准方差 , 则关 键链有 84 %的 概 率 不 受 非 关 键 链 延 误 的 影 响 , 当 然 , 式 ( 5) 应变为式 ( 6) 。( 9)FS j = mi nES i - E F jERi S j S j其中 , FS j 表示作业 j 的自由时差 , S j 表示作业j 的工艺紧后作业集 , S j 表示作业 j的最早时间资源紧后作 业 集 , ES i 表 示 作 业 i 的 最 早 开 始 时 间 ,E Fj 表示作业 j 的最早结束时间 。(4) 确定汇入缓冲区的大小 比较非关键链的标准方差与非关键链最后一个2I +( t -I )1e-+ = 0Idt 0. 84 6( )P X222其中 ,I 为非关键链 I 的总长的均值 。由此可见 , 非关键链标准方差计算有着很重要的意义 。对 于非关键链方差的计算 , 可以参考计划评审法 7 中关于事件节点方差的计算 , 由此提出下述计算非关键链方差的方法 。对于图 4 所示的串连结构的非关键链 , 其方差 等于该非 关 键 链 上 所 有 作 业 的 方 差 之 和 。在 图 4作业的自由时差 ,取小者为汇入缓冲区的尺寸大小 。这样做的目的是为了避免汇入缓冲区过大所带来的三种可能后果 :非关键链的开始时间早于关键链的 开始时间 ;关键链出现间隙 ;出现非关键链与关键链 的资源冲突 。所谓的“非关键链的开始时间早于关键链的开 始时间”是指非关键链最前面的作业的开始时间早于关键链最前面的作业的开始时间 。例 1 中不存在 这个问题 ,但是在其他的关键链项目中 ,因为汇入缓 冲区设得太大了 ,使得某些作业开始时间太靠前了 ,中 , 假设各个作业的方差分别是 2 、2 、2 、2 、2 , 则1 2 3 4 5这条非关键链的方差2= 2+2+2+2+2( 7)12345会造成这种情况 ,这会给项目的完成带来不利影响 。图 4 串连结构的非关键链对于图 5 所示的串并连混合结构的非关键链 , 其方差等于该非关键链中持续时间最长线路上的所有作所谓的“关键链出现间隙”是指关键链出现了时间间隙 ,也就是说关键链上的作业不是连续执行的 。在例 1 中 ,考虑在作业 A 、D 组成的非关键链后设汇入缓冲区 FB ,依据公式 (9) 计算得作业 D 的自由时 差为 1 ,如果取缓冲区的大小为 2 ,如图 6 所示 。在 图 6 中可以看到 ,关键链在作业 C 和作业 E 之间出现了一个单位时 间 的间 隙 , 这正 是因 为 缓冲 区 FB设得太大的缘故 。业之和 。在图 5 中 , 假设各个作业的方差分别是2 、12 2 2 2 2 2 2 2 22 、3 、4 、5 、6 、7 、8 、9 和10 , 其中矩形的长度代表作业的持续期大小 , 则这条非关键链的方差为2= 2+2+2+29 +20( 8)1461非关键链的方差计算出来以后 , 开平方即可得非关键链的标准方差 。图 5 串并连混合结构的非关键链( 3) 非关键作业自由时差的计算 本文的自由时差是在考虑资源约束条件下 , 而在资源受限情况下 , 按不同的调度规则 , 可以制定出 多个调度计划 , 在不同的调度计划中 , 各个作业的自图 6 出现间隙的关键链所谓的“非关键链与关键链的资源冲突”是指非 关键链上某些作业与关键链上某些作业存在的资源 冲突 。这种资源冲突可由缓冲区的设置引起 。现在考虑在例 1 中由作业 F 组成的非关键链后设汇入缓冲区 FB ,作业 F 的自由时差为 4 ,当取FB = 5 时 ,在图 7 中 ,作业 C 与作业 F 存在资源冲 突 ,很明显是因为汇入缓冲区 FB 的设置而引起的 。关键链方法采用设置缓冲区的办法 。本文提出的关键链汇入缓冲区的设置方法 ,在分析现有的方法基 础上 ,作了一定的改善 ,从理论上论证了其可行性 , 但是还有待进一步的实践检验 。参考文献 : 1 Gol drat t E M . 关键链 :突破项目管理的瓶颈 M . 北京 : 企业管 理出版社 ,2004 . 2 刘士新 ,宋健海 , 唐加福. 关键链 一种项目计划与调度新方 法J . 控制与决策 ,2003 ,18 ( 5) :5132516 . 3 Her roelen W , L eu s R. On t he merit s a nd pitf all s of critical chai n scheduli ng J . J o ur nal of Op eratio n s Ma nagement , 2001 , 19 :5592577 . 4 刘士新 ,宋健海 ,唐加福. 基于关键链的资源受限项目调度新方 法J . 自动化学报 ,2006 ,32 ( 1) :60266 . 5 Raz T , Ma r shall B . Eff ect of re so urce co n st rai nt s o n float calcu2 latio n s i n p roject net wo r k s J . Int er natio nal J o ur nal of Project Ma nage ment ,1996 ,14 ( 4) :2412248 . 6 韩文民 ,徐小琴. 关键链技术及在生产计划中应用问题探讨 J .商场现代化 ,2005 ,12 : 19220 . 7 关根智明. 计划评审法和关键路线法 M . 北京 : 机械工业出版 社 ,1983 .图 7 缓冲区太大造成的资源冲突纵观以上情况 ,其共同特点是汇入缓冲区的大小大于其对应的非关键链最后 一个 作业 的自 由 时 差 ,如果限定汇入缓冲区的大小不能大于其对应的非关键链最后一个作业的自由时差 ,则可以消除这些后果 。4资源冲突的消除由汇入缓冲区的设置而引起的资源冲突除了“非关键链与关键链的资源冲突”外 ,还有“非关键链与非关键链的资源冲突”。所谓的“非关键链与非关 键链的资源冲突”是指某一非关键链上某些作业与另一非关键链上某些作业存在的资源冲突 。限定汇入缓冲区的大小不能大于其对应的非关键链最后一 个作业的自由时差 ,可以消除“非关键链与关键链的 资源冲突”,但不能消除“非关键链与非关键链的资源冲突”。要消除“非关键链与 非关 键链