活动带时间窗的搭接网络的可行性及分析方法研究

带时间窗的搭接网络的可行性及分析方法研究

张静文,李若楠

(西北工业大学管理学院陕西西安71  29)

摘 要 目前大多数搭接网络中的搭接关系是基于最小时距或者最大时距的忽略了同时存在两种时距的情况。本文同时考虑两种时距的结合将时间窗的概念引入搭接时距中,然而时间窗的引入直接导致了网络出现不可行的问题。因此,分析了基于时间窗的搭接网络的可行性问题并提出可行性的判断步骤以及调整方法。最后对于可行的网络给出了时间参数的计算公式并举实例说明计算方法与步骤。

关键词搭接网络时间窗可行性分析;时间参数计算

Abstrac  :Te logia  reltinship in te spliced network mostly bas on ei her minmum timelgs or maximum ti  a  in mos  e  erch t pre  ent,whih ig r  the ituatio hat conta ns to  ime as at th  e t m. his ppe  cobnes the to tim lags ad  trduce  the oncep of tie winows nto te traditional spliced etwok,bu it led to the   work peared not fe  ible then analyes h feas b  i y rblem i t  splic  network ith ti widow  ad pu frwrd he  tep ofjudgment of th fea iility s ell as th ajstment metho. Furtermore this pper rovides th forula of a  culting t e  ram  er  and  ae  an eap e t explin the clcul  ion metod and s  eps.

Keywods sl  cd etwrk; tie idows fea ibility anl   s; sceduling process

网络计划技术产生于20世纪50年代末期,自产 终比较得出了简化的算法比一般的算法效率明显

式也提出了更高的要求 6 年代中期在美国首先 中识别关键链的方法丰富了搭接网络的知识;张钰

的网络计划[3]。 多时候活动间的搭接关系为时间窗约束。本文探讨

间参数计算问题。 接网络中分析研究可以增加搭接网络的适用性,并2搭接网络与时间窗的理论基础搭接网络的可行性问题

活动就可以立即开始。在实践中为了更简便的表示 众所周知在衔接网络与一般搭接网络中不某些活动间的特殊关系产生了搭接网络。在搭接网 会出现网络不可行的问题,但是在含有时间窗的搭络计划中活动间的逻辑关系是由相邻两活动之间 接网络中 由于搭接关系的多样性和时距的复杂性的不同时距决定的。时距指的就是搭接网络计划中 会存在不可行的情形。搭接网络中有两种情况导致相邻活动的时间差值。 由于相邻活动各有开始和结 网络不可行一种是活动不可行活动不可行时网束时间,故基本时距有四种,包括FS(结束到开始)  络必定不可行,但是当活动可行时,网络也不一定可STS 开始到开始),STF(开始到结束),FTF(结束到结 行另一种情况是在活动可行时计算搭接网络的时束)[9],以及由两种基本类型组成的组合逻辑关系。 间参数不能求出一组活动的开始时间使其满足所

一般说来,网络中活动间的时距不是一个确定 有搭接关系的时距从而导致的搭接网络不可行。活动不可行情形

活动的开始或结束时间不早于紧前活动的开始或 活动不可行是指由于某些活动有两个及以上结束时间。但实际中由于工艺或其他原因,两项活 的搭接关系,不能同时满足其时距要求,而导致网络动间时距会有最大的限制即活动的开始或结束时 不可行。为了阐述活动不可行的情形给出部分网络间不迟于紧前活动的开始或结束时间称为最大时 图如图1,假设活动A的开始时间SA=5 FA7距[1]。基于最小时距和最大时距的网络都已经有了 活动的开始时间SB,FB1  活动的开始较多的研究,但对于活动间的时距既满足最小时距 和结束时间由活动A、活动B及其时距决定。又满足最大时距的研究却很少。这种双重约束的问 对于活动A FA7 F=[  4],知FCF题类似于一个时间窗的问题即活动的开始时间或 +FTF,所以FC∈[9,11];对于活动B,S=8 F=[4,结束时间与紧前活动的开始或结束时间之间逻辑 ],知FC=SB+STF所以∈[1   5] 。活动C关系是一个时间区间,即时距为双重约束同时满足 的结束时间是由活动A和活动B共同决定的因此不早于和不迟于,不早于时间区间的下边界不迟于 取由活动A和活动分别求出的活动C的结束时间时间区间的上边界。 的交集作为活动C的结束时间,但在此例中两个活

时间窗指的是一个时间段在不同研究中具体 动得出的活动C的结束时间交集为空,也就是活动含义不同,在搭接网络中时间窗指的是活动与其紧 的结束时间不能同时满足紧前活动的时距所以前紧后活动间时距是一个时间区间各时间参数必 活动C不可行。

路径或者出行费用最少的路径是重点[12 而出行中 le

必不可少的信号灯的控制则是一个典型的时间窗 图1活动不可行情形图示

的应用问题,对时间窗的处理是解决这类问题的关

键。在生产实践中,工艺流程之间也有一定的时间约 在分析带时间窗的搭接网络是否可行时首先束某些工艺需要在前一项工艺开始或结束后的一 需要判断每个活动是否可行再判断整个网络是否段时间内进行这也是时间窗的应用问题。 由于时 可行。判断活动是否可行时,可以先判断活动有几个间窗问题广泛存在,所以将时间窗的概念引入到搭 搭接时距的约束如果只有一个活动时间很容易

确定则活动可行。对于有两个以上搭接时距约束 Step 从第一项活动开始自左至右依次计算的,分别根据搭接关系确定活动的开始时间或结束 每项活动的开始时间 由于有时间窗的约束开始时间如果存在一个时间区间满足所有搭接时距的 时间一般是一个区间。若无规定其s 1=0 f1=  。约束,则活动可行;反之,活动不可行。 Stp2:根据各项活动间不同的搭接时距计算

当出现活动不可行的情况时,需要对活动工期、 紧后活动的开始时间。

搭接时距或两者同时调整使其可行。例如在图1中 Cs①若其紧前逻辑关系为 关系则Sj可以通过改变活动工期来使活动C可行,当活动A ∈Fi+△F i,  )  j∈ jdj。

的工期增加1时 SA5FA=,得到的FC∈[10, 12] Cas②若其紧前逻辑关系为FF关系则Fj∈与由活动B得出的活动C的结束时间有交集,则活 Fi+△FF i,j  j∈Fj-dj。

动可行也可以通过放宽搭接时距使活动C可行, Ca ③若其紧前逻辑关系为S关系,则Sj∈当TF[, 5]时可知C∈[9,  ] 且与由 S+△SS(i j)  j∈Sj+dj。

活动B得出的C的结束时间有交集,因此活动可 a e④若其紧前逻辑关系为SF关系则j行。 ∈ i+△SF i,j)  Sj∈j-dj。

3.2网络不可行情形

当网络中的所有活动都可行时,还需要进一步 活动的开始时间。依次进行可以算出所有活动的判断网络是否可行。判断网络可行的依据是能否能 开始时间,并暂且将每项活动的开始时间区间的最求出网络的中所有活动的最早开始时间并且满足 小值作为该活动的最早开始时间若取得的最早结所有的搭接时距如果满足,则网络可行如果求出 束时间中EFEi i<n表明紧前活动与终点节的一组时间不能满足所有搭接时距关系,则表示网 点搭接关系设臵不正确此时按下述公式确定活动络不可行。当网络不可行时也可以对活动工期、搭 的最早结束时间:

接时距或两者同时调整使网络可行从而求出网络 E=x{EF1, 2, ……, EF}

时间参数计算方法

但是由于时间窗约束是兼具最大时距和最小时距 窗上边界的最早开始时间,进行以下调整且调整必的双重约束网络存在不可行的情况。对于一个网 须在已求出的最早时间的范围内进行。

络有两种不可行的情况对于第一种,可以按照以上 Ca e①若前后两项活动间搭接关系为FS关系,

时间 i代表活动i可以结束的时间 i、EF 、 Sj-t ij  EFi+di。

LSi和L分别代表活动i的最早开始时间、最早 Case④若前后两项活动间搭接关系为SF关系结束时间、最迟开始时间、最迟结束时间,i表示 将前一项活动的最早开始时间推后,即ESi=F活动的持续时间,tij表示时间窗约束的上界,t+  。

示时间窗约束的下界,则其时间参数计算方法如下: Step4:由于被调整的活动的最早时间推后,会引

起其紧前活动和紧后活动的最早时间变化。当检查 系。

其紧前活动时只要两者之间满足的逻辑关系值小 Step7对于不满足时间窗上边界的最迟时间,于等于时间窗约束值的上界减去调整时推后的时 进行以下调整。

间则不需要对其紧前活动进行调整(当被调整活动 ase①若活动间搭接关系为S关系将后一

Cse①若活动与其紧后活动关系为FS关系, S+j。

C a s④若活动与其紧后活动关系为SF关系 前的值则满足时间窗约束不再需要调整(如果两调整其紧后活动为EF=ESi+tij 则ESj=Ej-dj。 活动间的搭接时距是无上界的,也不需要再次调

Step5:对调整过后的活动再判断其与紧前紧后 整)。如果与其紧前活动之间满足的逻辑关系值大于活动间的关系是否满足,不满足按照S  ep3和Step4 等于它们之间时间窗的下界加上活动调整时提前进行调整经过多次检查完所有活动后如果得出一 的值则无需再次调整。

组最早开始时间全部满足搭接时距,即表示已求出 如果被调整的活动的最迟时间提前的值,不满每个活动的最早开始时间,继续计算最迟时间。 足以上所述两种情况。引起其紧前活动和紧后活动

如果在调整的过程中出现循环,即从某项活动 的最迟时间不满足活动间的搭接时距,则需要进一开始调整,调整一圈后又转到此活动,则不能求出最 步调整。对于其紧前活动两者间搭接时距值小于早时间,表示网络不可行,计算结束。 时间窗的下界,作如下调整

S  e6对于已求出的最早时间,令LFn ase①若活动与其紧前活动关系为FS关系,调

则L+

Case③若活动与其紧后活动关系为 关系, i。

则L =L  -t ij  LFi=LSi+i。 s④若活动与其紧前活动关系为SF关

ase④若活动与其紧后活动关系为SF关系,则 系调整其紧前活动为SiLFj-t ij ,则LFi=Li+

Li=LFj- t

如果活动有两个及以上的紧后活动计算其最 对于其紧后活动,提前后两者间的逻辑关系超迟时间时,分别计算后取最小的作为最终的最迟时 过上边界,则按照step7进行调整。按照以上方法进间。然后从左至右依次检查是否满足所有的搭接关 行调整,最终将会求出一组最迟时间。

网络为了说明以上介绍的时间参数的计算方法,

Fgure  Te slice neto kwith time wndow and  me lg

图2带时间窗的搭接网络及活动间的时距

表1中给出了实际中的带时间窗的搭接网络中 A  .8 由图2可知,FF(3, 8)≥5 f= 各活动的工期。当网络不可行时,需要调整工期使网 FF(3, ) 所以f8≥27 s8≥19。

络可行下表同样给出了调整后的活动工期。 Ac  .9:由图2可知 S(8, 9)= 2 ] s9=s8+SS(8, 9) 所以 9≥21,f9≥8。

表搭接网络中各活动的工期 c  .10:由图2可知 由SS[6, 10]=[  7] 

(  )最早时间的计算   知f10≥31  s10≥27。取由活动6活动7及

t.1:根据St 1可知 1=,f1=  1+d1= 活动分别求出的最早时间的交集作为活动 +8=8。 的最早时间,所以7≤s0≤   31≤f6≤34。

Ac   2 由图可知,S(1,   = 3, 7 以上求出了各活动的最早时间的范围然后取

3)

Ac 

S 2

Act 6由图2可知,FF5 6)=[6, ], 6=f5+ 满足FS(2, )= 2,3] 。经检查发现ES6=1   E 5

Ac  .7在图2中,由S F 3, )≥  f7=s3 =3 不满足S(9, 10)=[7, 9]  因此需要根据S SF 3,7 ,知f7≥13,s≥由SS(4, )=[3 7]  ep3调整活动的最早时间。本例中由于活动6与活知s= 4+SS(4 7)从而s≥15,f7≥24。取分别由 动1 之间满足的逻辑关系超过其时距的上限且活动和活动4求得的最早时间的交集所以s7≥1 活动0的最早时间不能再提前只能将活动6的 ,f≥2。 最早时间推后,从而满足时距的要求活动6推迟后

会影响其紧前紧后活动,被影响的紧前紧后活动又 2最迟时间的计算

会继续影响其自身的紧前紧后活动所以必须对所 经过调整所有最早时间区间的最小值即为网有涉及到的活动一一调整。 络的最早时间再根据S  ep自右至左求各活动对于不满足时距的活动调整过程如下 的最迟时间。可知,LF1=10=31 S1ES10=27,由于S1   ES10=27且SS(6,  0)=[ , 并依次求得各活动的最迟时间。

 由于F6=29 EF5=19且(5,6 =[6, 8]  27。

从而调整EF由于ES。

3]由于E2=10 ES3=9且FS(2,3 ≥0从而调 = -2=2  LF8=LS8+d=  。

整紧后活动ES由于E。整紧后活动ES 。由于=23,EF7且FF( ,  ≥5 ct.5:由FF(5, 6[6 8知F5=从而调整紧后活动EF=  。,ES82  Ac  .4:由SS , 7)=[3, ],知S4=LS-t47由于E41  ,E715且SS 4, 7 =   , = 3=1   LF4=L4+d=22。

7],从而调整紧后活动E7=E4+t4,7133=16 At. :由SF( , 7 ≥4知LS=F7-t3,7EF=25 24- 4=20,LF3=L+d3=3且由F(3,8)≥5,知由于ES820,S9= 且SS(8, 9)=[, 5 , LF=  - 从而调整紧后活动ES9=S8+t8,9 =  0+2=2 3=12分别求出后取小得3=2 F325。,EF9=9 Act   由 (2由于E7=25 E1=3,从而调整紧后活动

别活动的工期或者时距调整从而使网络可行调 的最迟时间是否满足搭接网络中所有的搭接时距,整的方法有多种,在调整后,假设的所有最早时间将 经过检查发现,只有LF2=   =  不满足可行,从而根据最早时间进一步求出所有的时间参 F(2,5)=[,3其他活动的最迟时间均满足。调数。 整LS=LF2+t2影响其紧后在不引起其他活动的变动的情况下将活动6 活动6 F6=2 不满足FF(5 6)=[6 8的工期缩短天,则当E6=25时 ES62 且E 再次调整活动的最迟结束时间为LF= 8,则1=2将满足SS(6 10)=[ , 7] 。将F 9, LS6=3,与其紧后活动10满足S(6, 10)=3 7] 。

10)=[  ]区间放宽,即F(9, 10)=[7 10则 调整结束得到网络中各活动的最迟时间即ES9=2  EF0 满足。 1=0,L1=;LS23,F29;L3=1  L

2 ;4=12 F4=22LS5=12LF5   S6=  –80

自由时差最后确定关键路径,在此不再赘述。 大学出版社 003

6结论

率。在实际中,网络的工期和搭接时距在耗费一定的 科学,205(2)21  90

士研究生行,并求出各活动的时间参数和关键路径从而可以 李若楠女,西北工业大学管理学院管理科学与工程专对网络做进一步的优化。搭接网络计划丰富了网络 业硕士在读主要研究方向为项目优化调度项目管理。计划的内容,带时间窗的搭接网络的引入更进一步

增加了搭接网络的适用性。通过对搭接网络时距及

时间窗的意义进行研究给出的计算带时间窗的搭

接网络中时间参数计算方法解决了时间参数计算

的具体问题,并涵盖了较多特殊的情况,为实际中更

进一步分析搭接网络提供了重要方法。

本文研究了含有时间窗的搭接网络中可行性

及时间参数分析方法但鉴于篇幅没有涉及带时间

窗的搭接网络中的工期-费用问题以及不确定工期

下的工期费用问题这些问题的研究更具有深层

次的意义,因此在以后的工作将中作进一步的研

究。

参考文献

[1] 中国建筑学会建筑统筹管理分会工程网络计划技术规

程教程标准]北京:中国建筑工业出版社,1   

[2] 李万庆,孟文清等工程网络计划技术,第一版北京:科学

出版社 200

[3] 杨冰网络计划计算模型的统一系统工程理论与实践

2002(3 :51

[4] 佟鹤晶乞建勋搭接网络向双代号网络的转化技术经

济,209(1 )28: 25-12

[5] 周梦搭接网络的简化计算方法研究: [硕士论文]大连:

大连理工大学,2012

[6]   ma Hji Ykhhali,Seyed Ha san

Ghodsypour Co tig lates   tarting tie of ac  ivi  ies i inte va  -a ue networkswithinimal  m lags[J Euopen   rnal o Oerational Re   rc,20(2010)  