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

带时间窗的搭接网络的可行性及分析方法研究张静文，李若楠（西北工业大学管理学院，陕西 西安 710129）摘 要：目前大多数搭接网络中的搭接关系是基于最小时距或者最大时距的，忽略了同时存在两种时距的情况。本文同时考虑两种时距的结合，将时间窗的概念引入搭接时距中，然而时间窗的引入直接导致了网络出现不可行的问题。因此，分析了基于时间窗的搭接网络的可行性问题，并提出可行性的判断步骤以及调整方法。最后，对于可行的网络给出了时间参数的计算公式并举实例说明计算方法与步骤。关键词：搭接网络；时间窗；可行性分析；时间参数计算Abstract：The logical relationship in the spliced network mostly base on either minimum time lags or maximum time lags in most research at present, which ignores the situation that contains two time lags at the same time. This paper combines the two time lags and introduces the concept of time windows into the traditional spliced network, but it led to the network appeared not feasible then analyzes the feasibility problem in the spliced network with time windows, and put forward the steps of judgment of the feasibility as well as the adjustment method. Furthermore, this paper provides the formula of calculating time parameters and takes an example to explain the calculation method and steps.Keywords：spliced network; time windows; feasibility analysis; scheduling process1引言网络计划技术产生于20世纪50年代末期，自产生以来由于其理论上的正确性、技术上的先进性，成为现代生产管理的科学方法。并在广泛的应用中得到了创新和发展，产生了巨大的经济效益1。但随着现代工程技术复杂性越来越高，对网络计划形式也提出了更高的要求，60年代中期在美国首先产生了一种称为搭接网络技术的新方法，随后不少国家相继仿效，经过不断改进并在生产中得到推广应用2。搭接网络技术的引入，可以更简便的表达某些工序间的特殊关系从而更易编制和控制复杂的网络计划3。目前，搭接网络已经引起众多学者和研究人员的注意，对其进行了深入的探索研究，并取得了较多的成果。佟鹤晶4介绍了在五种逻辑关系下不同搭接类型对应的双代号关系，并提出了搭接网络向双代号网络转化的步骤；周梦5给出了含有最小时距和最大时距的搭接网络时间参数的一般计算方法，并提出了两种情况下简化的时间参数计算方法，最终比较得出了简化的算法比一般的算法效率明显提高的结论；Siamak Haji Yakhchali6通过模糊数理论解决了工期不确定下搭接时距为最小时距的最早最迟开始时间计算方法；廖钰7首次将关键链项目管理运用到搭接网络中，提出了在搭接网络中识别关键链的方法，丰富了搭接网络的知识；张钰琴8基于CPM研究了搭接网络中的时间-费用问题，给出了时间费用优化方法的具体步骤。虽然搭接网络的研究已经涉及到很多方面，但活动之间搭接关系为时间窗的网络的研究却很少，然而在实际中很多时候活动间的搭接关系为时间窗约束。本文探讨搭接时距为时间窗的情形，当搭接时距是时间窗类型时，首次出现因为搭接时距而产生的活动不可行和网络不可行的情况。这种情况在传统衔接网络和搭接网络中均未出现，因此本文将分析探讨带有时间窗的搭接网络的可行性判断步骤、调整过程及时间参数计算问题。2搭接网络与时间窗的理论基础目前研究最多的是网络计划技术，其网络中活动间的关系是衔接关系，即只要紧前活动结束，紧后活动就可以立即开始。在实践中为了更简便的表示某些活动间的特殊关系产生了搭接网络。在搭接网络计划中，活动间的逻辑关系是由相邻两活动之间的不同时距决定的。时距指的就是搭接网络计划中相邻活动的时间差值。由于相邻活动各有开始和结束时间，故基本时距有四种，包括FTS(结束到开始)，STS(开始到开始)，STF(开始到结束)，FTF(结束到结束)9，以及由两种基本类型组成的组合逻辑关系。一般说来，网络中活动间的时距不是一个确定的时间点，而是不早于某个时间点或不迟于某个时间点。搭接网络中的时距一般指的就是最小时距即活动的开始或结束时间不早于紧前活动的开始或结束时间。但实际中，由于工艺或其他原因，两项活动间时距会有最大的限制，即活动的开始或结束时间不迟于紧前活动的开始或结束时间，称为最大时距10。基于最小时距和最大时距的网络都已经有了较多的研究，但对于活动间的时距既满足最小时距又满足最大时距的研究却很少。这种双重约束的问题类似于一个时间窗的问题，即活动的开始时间或结束时间与紧前活动的开始或结束时间之间逻辑关系是一个时间区间，即时距为双重约束，同时满足不早于和不迟于，不早于时间区间的下边界，不迟于时间区间的上边界。时间窗指的是一个时间段，在不同研究中具体含义不同，在搭接网络中时间窗指的是活动与其紧前紧后活动间时距是一个时间区间，各时间参数必须依据此区间求得。时间窗的概念已经在很多方面得到广泛的应用。例如，物流配送是现代物流系统的一个重要环节，而按客户对送货时间的要求进行车辆调度，是一个带有时间窗的车辆调度问题，时间窗指的是客户对送货时间的要求11；交通网络的优化问题已经被深入研究，在交通网中求出最短出行路径或者出行费用最少的路径是重点12，而出行中必不可少的信号灯的控制则是一个典型的时间窗的应用问题，对时间窗的处理是解决这类问题的关键。在生产实践中，工艺流程之间也有一定的时间约束，某些工艺需要在前一项工艺开始或结束后的一段时间内进行，这也是时间窗的应用问题。由于时间窗问题广泛存在，所以将时间窗的概念引入到搭接网络中分析研究可以增加搭接网络的适用性，并且可以为研究实践中活动间搭接时距为时间窗的项目分析优化提供思路。3搭接网络的可行性问题众所周知，在衔接网络与一般搭接网络中，不会出现网络不可行的问题，但是在含有时间窗的搭接网络中，由于搭接关系的多样性和时距的复杂性会存在不可行的情形。搭接网络中有两种情况导致网络不可行，一种是活动不可行，活动不可行时网络必定不可行，但是当活动可行时，网络也不一定可行；另一种情况是在活动可行时计算搭接网络的时间参数不能求出一组活动的开始时间使其满足所有搭接关系的时距，从而导致的搭接网络不可行。3.1活动不可行情形活动不可行是指由于某些活动有两个及以上的搭接关系，不能同时满足其时距要求，而导致网络不可行。为了阐述活动不可行的情形给出部分网络图，如图1，假设活动A的开始时间SA=5，FA=7；活动B的开始时间SB=8，FB=11；活动C的开始和结束时间由活动A、活动B及其时距决定。对于活动A，FA=7,FTF=2，4,知FC=FA+FTF，所以FC9，11；对于活动B，SB=8,STF=4，7,知FC=SB+STF，所以FC12，15。活动C的结束时间是由活动A和活动B共同决定的，因此取由活动A和活动B分别求出的活动C的结束时间的交集作为活动C的结束时间，但在此例中两个活动得出的活动C的结束时间交集为空，也就是活动C的结束时间不能同时满足紧前活动的时距，所以活动C不可行。Figure 1. The situation that the activity is not feasible图1活动不可行情形图示在分析带时间窗的搭接网络是否可行时，首先需要判断每个活动是否可行，再判断整个网络是否可行。判断活动是否可行时，可以先判断活动有几个搭接时距的约束，如果只有一个，活动时间很容易确定，则活动可行。对于有两个以上搭接时距约束的，分别根据搭接关系确定活动的开始时间或结束时间，如果存在一个时间区间满足所有搭接时距的约束，则活动可行；反之，活动不可行。当出现活动不可行的情况时，需要对活动工期、搭接时距或两者同时调整使其可行。例如在图1中，可以通过改变活动工期来使活动C可行，当活动A的工期增加1时，SA=5，FA=8，得到的FC10, 12与由活动B得出的活动C的结束时间有交集，则活动C可行；也可以通过放宽搭接时距使活动C可行，当FTF=2, 5时，可知FC9, 12，且与由活动B得出的C的结束时间有交集，因此活动C可行。3.2网络不可行情形当网络中的所有活动都可行时，还需要进一步判断网络是否可行。判断网络可行的依据是能否能求出网络的中所有活动的最早开始时间，并且满足所有的搭接时距，如果满足，则网络可行；如果求出的一组时间不能满足所有搭接时距关系，则表示网络不可行。当网络不可行时也可以对活动工期、搭接时距或两者同时调整使网络可行，从而求出网络的时间参数。下面具体介绍带时间窗的搭接网络的时间参数的方法，并举例说明。4时间参数计算方法搭接时距是时间窗类型的网络，计算时间参数的方法与传统的网络中计算时间参数的方法类似，但是由于时间窗约束是兼具最大时距和最小时距的双重约束，网络存在不可行的情况。对于一个网络有两种不可行的情况，对于第一种，可以按照以上所讲的办法判断，第二种只能通过先计算其最早时间，如果能找出一组最早时间满足所有搭接时距则表示可行；否则，网络不可行，再通过修改工期或者逻辑关系使其满足所有约束。下面介绍带时间窗约束的搭接网络的时间参数计算方法。假设含有时间窗的搭接关系网络有n项活动，每项活动都连续进行，且必须在搭接时距为时间窗的约束下进行，其中ij，si代表活动i可以开始的时间，fi代表活动i可以结束的时间，ESi、EFi、LSi和LFi分别代表活动i的最早开始时间、最早结束时间、最迟开始时间、最迟结束时间，di表示活动i的持续时间，表示时间窗约束的上界，表示时间窗约束的下界，则其时间参数计算方法如下：Step1：从第一项活动开始自左至右依次计算每项活动的开始时间，由于有时间窗的约束，开始时间一般是一个区间。若无规定，其s1=0，f1=d1。Step2：根据各项活动间不同的搭接时距计算紧后活动的开始时间。Case若其紧前逻辑关系为FS关系，则SjFi+FS(i,j)，FjSj+dj。Case若其紧前逻辑关系为FF关系，则FjFi+FF(i,j)，SjFj-dj。Case若其紧前逻辑关系为SS关系，则SjSi+SS(i,j)，FjSj+dj。Case若其紧前逻辑关系为SF关系，则FjSi+SF(i,j)，SjFj-dj。若活动j有两个以上紧前活动，则应该分别算出每个搭接时距下活动j的开始时间，并取交集作为活动j的开始时间。依次进行可以算出所有活动的开始时间，并暂且将每项活动的开始时间区间的最小值作为该活动的最早开始时间，若取得的最早结束时间中EFnEFi（in）表明紧前活动与终点节点搭接关系设置不正确，此时按下述公式确定活动n的最早结束时间：EFn=maxEF1, EF2, , EFn同时，在终点节点n与使EFn得到调整的节点间增加一条虚箭线，以修正其搭接关系，EFn即网络的总工期13。确定所有活动的最早开始时间后再依次检查是否满足所有搭接时距。Step3：在此算法下求出的最早开始时间均满足时间窗的下界，而上界则需要判断。对于不满足时间窗上边界的最早开始时间，进行以下调整，且调整必须在已求出的最早时间的范围内进行。Case若前后两项活动间搭接关系为FS关系，将前一项活动的最早结束时间推后，即EFi=ESj-，ESi=EFi-di。Case若前后两项活动间搭接关系为FF关系，将前一项活动的最早结束时间推后，即EFi=EFj-，ESi=EFi-di。Case若前后两项活动间搭接关系为SS关系，将前一项活动的最早开始时间推后，即ESi=ESj-，EFi=ESi+di。Case若前后两项活动间搭接关系为SF关系，将前一项活动的最早开始时间推后，即ESi=EFj-，EFi=ESi+di。Step4：由于被调整的活动的最早时间推后，会引起其紧前活动和紧后活动的最早时间变化。当检查其紧前活动时，只要两者之间满足的逻辑关系值小于等于时间窗约束值的上界减去调整时推后的时间，则不需要对其紧前活动进行调整（当被调整活动与其紧前活动之间的搭接时距无上界时，也无需调整其紧前活动）；当检查其紧后活动时，只要两者之间满足的逻辑关系值大于等于时间窗的下界加上活动推后的值，则不需要调整其紧后活动。检查时若非以上两种情况，对于其紧前活动，则按照Step3继续调整；若满足，继续进行。对于其紧后活动，若满足，则继续进行；若不满足，进行以下调整。Case若活动与其紧后活动关系为FS关系，调整其紧后活动为ESi=EFj+，则EFj=ESj+dj。Case若活动与其紧后活动关系为FF关系，调整其紧后活动为EFj=EFi+，则ESj=EFj-dj。Case若活动与其紧后活动关系为SS关系，调整其紧后活动为ESj=ESi+，则EFj=ESj+dj。Case若活动与其紧后活动关系为SF关系，调整其紧后活动为EFj=ESi+，则ESj=EFj-dj。Step5：对调整过后的活动再判断其与紧前紧后活动间的关系是否满足，不满足按照Step3和Step4进行调整，经过多次检查完所有活动后如果得出一组最早开始时间全部满足搭接时距，即表示已求出每个活动的最早开始时间，继续计算最迟时间。如果在调整的过程中出现循环，即从某项活动开始调整，调整一圈后又转到此活动，则不能求出最早时间，表示网络不可行，计算结束。Step6：对于已求出的最早时间，令LFn=EFn，则LSn=ESn。自右至左求各活动的最迟时间。Case若活动与其紧后活动关系为FS关系，则LFi=LSj-，LSi=LFi-di。Case若活动与其紧后活动关系为FF关系，则LFi=LFj-，LSi=LFi-di。Case若活动与其紧后活动关系为SS关系，则LSi=LSj-，LFi=LSi+di。Case若活动与其紧后活动关系为SF关系，则LSi=LFj-，LFi=LSi+di。如果活动有两个及以上的紧后活动，计算其最迟时间时，分别计算后取最小的作为最终的最迟时间。然后从左至右依次检查是否满足所有的搭接关系。Step7：对于不满足时间窗上边界的最迟时间，进行以下调整。Case若活动间搭接关系为FS关系，将后一项活动的最迟开始时间提前，即LSj=LFi+，LFj=LSj+dj。Case若活动间搭接关系为FF关系，将后一项活动的最迟结束时间提前，即LFj=LFi+，LSj=LFj-dj。Case若活动间搭接关系为SS关系，将后一项活动的最迟开始时间提前，即LSj=LSi+，LFj=LSj+dj。Case若活动间搭接关系为SF关系，将后一项活动的最迟结束时间提前，即LFj=LSi+，LSj=LFj-dj。Step8：由于被调整的活动的最迟时间提前，会引起其紧前活动和紧后活动的最迟时间的变化。当被调整活动与其紧后活动之间满足的逻辑关系值小于等于它们间时间窗的上界减去活动调整时提前的值，则满足时间窗约束，不再需要调整（如果两活动间的搭接时距是无上界的，也不需要再次调整）。如果与其紧前活动之间满足的逻辑关系值大于等于它们之间时间窗的下界加上活动调整时提前的值，则无需再次调整。如果被调整的活动的最迟时间提前的值，不满足以上所述两种情况。引起其紧前活动和紧后活动的最迟时间不满足活动间的搭接时距，则需要进一步调整。对于其紧前活动，两者间搭接时距值小于时间窗的下界，作如下调整：Case若活动与其紧前活动关系为FS关系，调整其紧前活动为LFi=LSj-，则LSi=LFi-di。Case若活动与其紧前活动关系为FF关系，调整其紧前活动为LFi=LFj-，则LSi=LFi-di。Case若活动与其紧前活动关系为SS关系，调整其紧前活动为LSi=LSj-，则LFi=LSi+di。Case若活动与其紧前活动关系为SF关系，调整其紧前活动为LSi=LFj-，则LFi=LSi+di。对于其紧后活动，提前后两者间的逻辑关系超过上边界，则按照step7进行调整。按照以上方法进行调整，最终将会求出一组最迟时间。Step9：求出每个活动的最早最迟时间后，最后可以根据传统的方法求出总时差和自由时差，进而确定关键线路。5计算实例图2表示了一个实际中的带有时间窗的搭接网络，为了说明以上介绍的时间参数的计算方法，现以图2为例说明。 Figure 2. The spliced network with time windows and time lags图2带时间窗的搭接网络及活动间的时距表1中给出了实际中的带时间窗的搭接网络中各活动的工期。当网络不可行时，需要调整工期使网络可行，下表同样给出了调整后的活动工期。表1搭接网络中各活动的工期活动12345678910工期861310899874修改后的工期861310859874(1)最早时间的计算Act.1：根据Step1可知s1=0，f1= s1+d1=0+8=8。Act.2：由图2可知，SS(1, 2)=3, 7，s2=s1+SS(1, 2)，所以3s27，9f213。Act.3：由图2可知，FS(2, 3)0，s3=f2+FS(2, 3)，所以s39，f322。Act.4：由图2可知，FS(2, 4)3，s4=f2+FS(2, 4)，所以s412，f322。Act.5：由图2可知，FS(2, 5)=2, 3，s5=f2+FS(2, 5)，所以11s516，19f524。Act.6：由图2可知，FF(5, 6)=6, 8，f6=f5+FF(5, 6)，所以25f632，16s623。Act.7：在图2中，由SF(3, 7)4，f7=s3+SF(3, 7)，知f713，s74；由SS(4, 7)=3, 7，知s7=s4+SS(4, 7)从而s715，f724。取分别由活动3和活动4求得的最早时间的交集，所以s715，f724。Act.8：由图2可知，FF(3, 8)5, f8=f3+FF(3, 8)，所以f827，s819。Act.9：由图2可知，SS(8, 9)=2, 5，s9=s8+SS(8, 9)，所以s921，f928。Act.10：由图2可知，由SS6, 10=3, 7，s10=s6+SS6, 10，知s10=19, 30，f10=23, 34；由SF9, 10=7, 9，f10=s9+SF9, 10，知f1028，s1024；由FF(7, 10)7，f10=f7+FF(7, 10)，知f1031，s1027。取由活动6，活动7及活动9分别求出的最早时间的交集作为活动10的最早时间，所以27s1030，31f634。以上求出了各活动的最早时间的范围，然后取各活动最早时间区间中的最小值暂时作为各活动的最早时间，即ES1=0，EF1=8；ES2=3，EF2=9；ES3=9，EF3=22；ES4=12，EF4=22；ES5=11，EF5=19；ES6=16，EF6=25；ES7=15，EF7=24；ES8=19，EF8=27；ES9=21，EF9=28；ES10=27，EF10=31。依次检查所求的最早时间是不是满足搭接网络中所有的搭接时距，例如，EF2=9，ES5=11满足FS(2, 5)=2, 3。经检查发现ES6=16，ES10=27不满足SS(6, 10)=3, 7，ES9=21，EF10=31不满足SF(9, 10)=7, 9，因此需要根据Step3调整活动的最早时间。本例中由于活动6与活动10之间满足的逻辑关系超过其时距的上限，且活动10的最早时间不能再提前，只能将活动6的最早时间推后，从而满足时距的要求，活动6推迟后会影响其紧前紧后活动，被影响的紧前紧后活动又会继续影响其自身的紧前紧后活动，所以必须对所有涉及到的活动一一调整。对于不满足时距的活动，调整过程如下：由于ES6=16，ES10=27且SS(6, 10)=3, 7，从而调整ES6=ES10-=27-7=20，EF6=29；由于EF6=29，EF5=19且FF(5, 6)=6, 8，从而调整EF5=EF6-=29-8=21，ES5=13；由于ES5=13，EF2=9且FS(2, 5)= 2, 3，从而调整EF2=ES5-=13-3=10，ES2=4；由于EF2=10，ES3=9且FS(2, 3)0，从而调整紧后活动ES3=EF2+=10+0=10，EF3=23；由于EF2=10，ES4=12且FS(2, 4)3，从而调整紧后活动ES4=EF2+=10+3=13，EF4=23；由于EF3=23，EF8=27且FF(3, 8)5,从而调整紧后活动EF8=EF3+=23+5=28，ES8=20；由于ES4=13，ES7=15且SS(4, 7)=3, 7，从而调整紧后活动ES7=ES4+=13+3=16，EF7=25；由于ES8=20，ES9=21且SS(8, 9)=2, 5，从而调整紧后活动ES9=ES8+=20+2=22,EF9=29；由于EF7=25，EF10=31且FF(7, 10)7，从而调整紧后活动EF10=EF7+=25+7=32，ES10=28。又由于调整过后的ES6，引起一系列变动，ES10也被调整，但调整后的ES10=28，ES6=20，仍不满足SS(6, 10)=3, 7，并且调整陷入循环，因此网络不可行，找不到一组合适的最早时间可以满足所以时距。在实际中工期或者时距在改变费用的情况下都可以稍作调整，因此，为了使网络可行，需要将个别活动的工期或者时距调整，从而使网络可行，调整的方法有多种，在调整后，假设的所有最早时间将可行，从而根据最早时间进一步求出所有的时间参数。在不引起其他活动的变动的情况下，将活动6的工期缩短4天，则当EF6=25时，ES6=20，且ES10=27将满足SS(6, 10)=3, 7。将SF(9, 10)=7，9区间放宽，即SF(9, 10)=7, 10，则ES9=21，EF10=31满足。(2)最迟时间的计算经过调整，所有最早时间区间的最小值即为网络的最早时间，再根据Step6自右至左求各活动的最迟时间。可知，LF10=EF10=31，LS10=ES10=27，并依次求得各活动的最迟时间。Act.10：可知LF10=EF10=31，LS10=ES10=27。Act.9：由SF(9, 10)=7, 10知LS9=LF10- =31-7=24，LF9=LS9+d9=31。Act.8：由SS(8, 9)=2, 5，知LS8=LS9- =24-2=22，LF8=LS8+d8=30。Act.7：由FF(7, 10)7，知LF7=LF10-= 3-7=24，LS7=LF7-d7=24-9=15。Act.6：由SS(6, 10)=3, 7，知LS6=LS10-= 27-3=24，LF6=LS6+d6=24+5=29。Act.5：由FF(5, 6)=6, 8，知LF5=LF6- =29-6=23，LS5=LF5-d5=23-8=15。Act.4：由SS(4, 7)=3, 7，知LS4=LS7- =15-3=12，LF4=LS4+d4=22。Act.3：由SF(3, 7)4，知LS3=LF7-=24- 4=20，LF3=LS3+d3=33；且由FF(3, 8)5, 知LF3 =LF8-=30-5=25，LS3=LF3-d3=25-13=12；分别求出后取小，得LS3=12，LF3=25。Act.2：由FS(2, 3)0知LF2=LS3-=12-0 =12，LS2=LF2-d2=12-6=6；由FS(2, 4)3知LF2=LS4 - =12-3=9，LS2=LF2-d2=9-6=3；由FS(2, 5)=2,3知LF2=LS5-=15-2=13，LS2=LF2-d2 =13-6 =7；分别求出后取小，得LS2=3，LF2=9。Act.1：由SS(1, 2)=3, 7知，LS1=LS2-= 3-3=0，LF1=LS1+d1=0+8=8。以上求出了各活动的最迟时间，依次检查所求的最迟时间是否满足搭接网络中所有的搭接时距，经过检查发现，只有LF2=9，LS5=15，不满足FS(2, 5)=2, 3，其他活动的最迟时间均满足。调整LS5=LF2+=9+3=12，LF5=20，影响其紧后活动6，LF6=29，不满足FF(5, 6)=6, 8，再次调整活动6的最迟结束时间为LF6=28，则LS6=23，与其紧后活动10满足SS(6, 10)=3, 7。调整结束，得到网络中各活动的最迟时间，即LS1=0,LF1=8；LS2=3，LF2=9；LS3=12，LF3=25；LS4=12，LF4=22；LS5=12，LF5=20；LS6=23，LF6=28；LS7=15，LF7=24；LS8=22，LF8=30；LS9=24，LF9=31；LS10=27，LF10=31。求出每个活动的最早最迟时间后，最后可以根据求关键路径时所用的方法求得网络的总时差和自由时差，最后确定关键路径，在此不再赘述。6结论带时间窗的搭接网络计划的推广应用在实践中的很多方面都有其重要的意义，本文提出的分析带时间窗的搭接网络时的两种不可行情形，将可行性判断分两个层次进行，可以提高判断可行性的效率。在实际中，网络的工期