5th International/11th Construction Specialty Conference 5e International/11e Conférence spécialisée sur la construction Vancouver, British Columbia June 8 to June 10, 2015 / 8 juin au 10 juin 2015 ONE RELATION TO RULE THEM ALL: THE POINT-TO-POINT PRECEDENCE RELATION THAT SUBSTITUTES THE EXISTING ONES Miklos Hajdu1,2,3 1 Ybl Miklos Faculty of Architecture and Civil Engineering, Szent István University, Hungary 2 Faculty of Architecture, Budapest University of Technology and Economics, Hungary 3 miklos.hajdu63@gmail.com Abstract: Precedence Diagram Method (PDM) has gained the widest acceptance in the scheduling practice in the last decades due to its modeling flexibility over other existing techniques, and to the relative simplicity of its mathematical background. The four basic precedence relationships have been serving planners for more than half a century. However, even this model is not flexible enough; proper modeling of overlapped activities seems to be a never-ending debate. Different practical and theoretical solutions have been proposed during the years for better modeling overlapped activities. The most promising among them is the development of a new type of relation that can connect any two arbitrary points of the related activities. These relations can be called point-to-point relations. Different authors in various ways have proposed similar solutions. To the best of our knowledge, the literature on the mathematical model of PDM using this new relation is lacking. Main results of the paper are: 1) standardized discussion of the different approaches to point-to-point relations; 2) proper mathematical model of PDM with point-to-point relations; 3) introduction of the algorithm that can handle point-to-point relations with both minimal and maximal lag to define the earliest and latest feasible time policy. 1 INTRODUCTION AND LITERATURE REVIEW Widely used network techniques are more than half a century old. The results of Fondahl, (Fondahl 1961), Roy (Roy 1959), (Roy 1960), IBM (IBM 1964) and many others have led to the present form of the Precedence Diagram Method, the prevailing network technique of our times. PDM has hardly changed during the decades in spite of the critiques it has received about its modeling capabilities. Proper modeling of overlapping activities seems to be a never-ending debate when traditional precedence relations are used, (Douglas et al. 2006) because traditional endpoint relations are simply not suitable for describing this kind of logic. Different solutions have been proposed using the traditional precedence relations; but fragmentation of activities and developments based on this idea (Tarek & Menesi 2010) seem to be the best theoretical solution despite the arising practical problems, namely the multiplication of the number of activities and precedence relations. Probably the fragmentation technique has given the idea of connecting the inner points of the activities, which will be discussed in this paper. These point-to-point relations connecting the internal points of the activities seem to be theoretically more suitable for modeling overlapping activities – especially if continuous activities are assumed - as multiple relations are allowed between the activities. To the best of our knowledge four partly parallel works regarding point-to-point relations can be found: Kim (Kim 2010, 2012) calls his new relations bee-line relations and the graphical representation Bee-line Diagram (BDM), while Francis and Miresco (Francis & Mireco 2000, 2002) call their new relations temporal functions and they call their graphical representation method 340-1 chronographic approach. Plotnick (Plotnick 2004) calls his method Relationship Diagramming method (RDM) using the term of ‘event’ for the internal points. Ponce de Leon (Ponce de Leon 2010) uses the term Graphical Diagramming Method (GDM) and connected internal points are called embedded nodes. Despite the differences in terminology and definitions, e.g. bee-line and RDM relation does not allow a lag between the connected inner points, maximal lags are defined only in the work of Francis and Miresco, the concept behind all these works is the same. All these improvements regarding the relationships can be seen as a new type of precedence relation that can substitute all traditional precedence relations, as it will be shown later. The goal of this paper is twofold: firstly, to remedy a common shortcoming of these works (authors have failed to present the mathematical model); secondly, to show that traditional precedence relationships can be derived from the general point-to-point relations discussed in this paper. A proper mathematical model and the algorithm will be introduced using standardized technical terminology. The new point-to-point relation can be seen as a generalization of traditional precedence relations. It will be shown that the existing traditional precedence relations are special cases of the point-to-point relations; they connect the endpoints of the activities instead of the internal points. 2 THE MATHEMATICAL MODEL 2.1 Notations Let a directed acyclic graph be given with one start (s) and one finish node (f). Let N = {1,2,…i…j…n} stand for the set of nodes also called activities. A will define the set of arcs, also called precedence relations. The ‘super’ relation defined later can have minimal or maximal lags, therefore Amin and Amax subsets are introduced for differentiating relations with minimal and maximal lags. In the algorithm, relations with maximal lags will be transformed into relations with minimal lags. In this case A* denotes the set of relations . An activity i is defined by its start and finish points Pis, PiF, shortly Si or Fi, or by any of the two aforementioned points and its duration di. Additional points of the activities can also be defined. Pik stands for the kth point of activity i. The relative place of the kth point of activity i is defined by the time span (ti k) from the start point of activity i (PiS). A relation can be defined between any lth internal point of activity j and any kth internal point of activity i by defining the time that must elapse between the two points (zi kjl). Therefore this ‘super’ precedence relation can be defined either by the points and the lag as (Pik;Pjl, zikjl) or by the relative positions of the points and the lag (ti k; tjl , zikjl). Explanation can be seen in Fig. 1. Lags can be defined using production volumes as well. Figure 1: Explanation of notations and the the ‘super’ precedence relation. (t ik ; t jl ; zikjl) 340-2 Let the time when a point is accomplished be called point or event time and denoted by Tik. This way TiS stands for the start, and TiF stands for the finish of activity i. Table 1 shows how the traditional relations and bee-line relations can be derived from the new ‘super’ relation. Transformation of temporal functions (Francis & Miresco 2002) and RDM relations is obvious so this is not presented here. If instead of time, the names of the points of the activities are used for describing the relation, then even the same notation can be used. (e.g. instead of SS100 days (S; S; 100 days) can be used.) Based on the above notations the following model can be defined. Table 1: ‘Super’ relation can be used instead of traditional and bee-line precedence relations Known precedence relations Equivalent point-to-point relation PDM Start-to-Start zi j ( 0 ; 0; ziSjS ) or ( S; S; ziSjS) Finish-to-Start zi j ( d i ; 0; ziFjS ) or ( F; S; ziFjS) Finish-to-Finish zi j ( d i ; d j; ziFjS ) or ( F; F; ziFjF) Start-to-Finish zi j ( 0 ; d j; ziSjS ) or ( S; F; ziSjF) BDM (t ik, t jl) (t ik; t jl ; 0) 2.2 The model The first two conditions tell that all precedence relations must be satisfied. [1] describes the precedence relations with minimal lags, while [2] describes the precedence relations with maximal lags. [1] Tjl –Tik ≥ zikjl ∀ (Pik;Pjl) ∈ Amin [2] Tjl –Tik ≤ zikjl ∀ (Pik;Pjl) ∈ Amax By definition Tik = TiS+tik and Tjl = TjS+tjl therefore [1] and [2] can be modified as: [1*] TjS – TiS ≥ zikjl – tjl + tik ∀ (Pik;Pjl) ∈ Amin [2*] TjS – TiS ≤ zikjl – tjl +tik ∀ (Pik;Pjl) ∈ Amax The finish of the activities can be calculated according to [3]. Activities are assumed to be continuous [4]. Let’s set the start of the project to zero. [5] [3] TiS +di = TiF ∀ i ∈ N [4] Tik - tik = TiS ∀ i ∈ N and ∃ Pik (Pik exist) [5] TsS = 0 The T policy that satisfies [1*], [2*], [3], [4], and [5] is called a feasible time policy. An infinite number of feasible time policies exist, but the objective of the model is to find that/those time policy/policies where the project duration is the minimum, that is [6] TfF − TsS → min that is TfF − 0 → min that is TfF → min This model is an LP model, so any LP solver can be used for solving it, furthermore, based on the simplistic structure of this LP problem different efficient primal dual algorithms can be developed. The solution shown below is based on the modification of the simplistic and widely used CPM/PDM time analysis. This approach is probably the easiest to digest for planning engineers. 340-3 3 ALGORITHMS 3.1 Point-to-point relations with minimal lag The goal of the algorithm is to find the optimal time policy, the earliest and the latest out of the existing – sometimes millions of – optimal time policies. The earliest optimal time policy is denoted by EiS and EiF. The latest optimal policy is denoted by LiS and LiF. The applied algorithm has two phases. The result of the first phase is the earliest optimal time policy, while the result of the second phase is the latest optimal time policy. Let’s suppose for the sake of simplicity that only relations with minimal lags are allowed in the network. In this case, the earliest start and finish of an activity j can only be calculated, if the earliest start dates for all its predecessors are known. As all precedence relations must be satisfied, the early start of a given j can be defined by the maximum of the shifts caused by the preceding relations of activity j, that is: [7] EjS = max { EiS + t ik + zikjl – t jl ∀ (Pik;Pjl) ∈ Amin } To start, an activity with known predecessors has to be found. In the beginning, only the start activity satisfies this condition: all of its predecessors are known because it does not have any. After these introductory thoughts, the steps of the first phase, that is the steps aiming to find the earliest time policy, can be summarized as follows: Step 1 Let EiS= -∞ and EiF=-∞ ∀ i ∈ N; Let ESS=0 Let g:=1 Step 2 REPEAT g:=g+1 Choose an activity j from the unknowns (EiS=-∞) with known predecessors only. IF there is no such activity then GO TO Step 3 EjS = max { EiS + t ik + zikjl – t jl ∀ (Pik;Pjl) ∈ Amin }; EjF=EjS+d j UNTIL g=n Step 3 IF g<n THEN STOP (There is a loop in the network.) ELSE p=EfF (Project duration is the same as the early finish of the finish activity.) During the backward pass, the latest optimal time policy will be defined. It is completed by working from the terminal activity to the initial activity in reverse direction of the arrows. It is based on the observation that the late activity times of an activity can only be calculated, if these dates are known for all of its successors. As all successor relations must be satisfied, the late start of a given i can be defined by the maximum of the shifts caused by the succeeding relations of activity i, that is: [8] LiS = min { LjS + t jk - zikjl – t il ∀ (Pik;Pjl) ∈ Amin } The rules of the backward pass can be summarized as follows: Step 1 Let LiS= ∞ and LiF= ∞ ∀ i ∈ N; Let Li=FS=p- df ; Let g:=1 Step 2 REPEAT g:=g+1 Choose an activity i from the unknowns (LiS=∞) with known successors only. LiS = min { LjS + t jk - zikjl – t il ∀ (Pik;Pjl) ∈ Amin } ; LiF=LiS+d i UNTIL g=n (Note: Loop detection is not necessary during the backward pass.) 340-4 3.2 Point-to-point relations with mixed lags Calculations with mixed lags require more computational steps. Maximal relations have to be transformed into minimal relations first. Comparing conditions [1] and [2], it can be seen that the difference between a relation with minimal or maximal lags lies in the direction of the operand. Transforming a relation with maximal lag into a relation with minimal lag requires a simple multiplication by -1. [2] Tjl –Tik ≤ zikjl ∀ (Pik;Pjl) ∈ Amax / *(-1) [9] Tik –Tjl ≤ - zjlik ∀ (Pik;Pjl) ∈ Amax This is nothing else but a relation from j to i with a negative minimal lag (see Fig. 2). Figure 2: Point-to-point relation with maximal lag a) and its minimal equivalent b) Traditional precedence relations with maximal lags, and their transformed equivalent minimal lags can be found in Table 2. Table 2: Traditional precedence relations and their equivalent minimal versions. Traditional precedence relations with maximal lag Equivalent point-to-point relation with maximal lag Transformed equivalent precedence relations with minimal lag* Transformed equivalent point-to-point relation with minimal lag* maxSSz max(0; 0; z) SS-z (0; 0; -z) maxFSz max(di; 0; z) SF-z (0, dj; -z) maxFFz max(di; dj; z) FF-z (di; dj; -z) maxSFz max(0, dj; z) FS-z (di; 0; -z) * Transformed equivalents go in the opposite direction However, converting relations with maximal lags into their equivalent minimal relations can result in so-called transformation loops. In Fig. 3 it can be seen that there is a loop between B and C. The simple time analysis presented in 3.1 cannot be used in case of loops. One can easily check it by selecting the activities. E.g. during the forward pass activity A has to be chosen first. After that none of the activities can be selected, B has two predecessors but only A is known and C is not; C has two predecessors but only A is known and B is not, so the algorithm will stop here. In case of loops, different algorithms exist to find the longest path. We will use the modified version of the algorithm developed by Bellman (Bellman, 1958) and Ford (1956) for finding the shortest path between any two points of a cyclic graph. The algorithm is based on the idea that during the forward pass all activities are calculated using the dates of their predecessors even if those have not taken their final dates yet. When all activities have been calculated this way, it has to be checked whether there have been changes in activity dates or not. If the answer is yes, then the entire calculation must be repeated again and again, until we come to the results we had in the previous iteration. In every iteration, at least 340-5 one activity takes its final value, so after maximum n iterations we get the results. Usually much fewer iterations are necessary. If the nth iteration still brings changes, then the network cannot be solved due to the maximal relations that probably impose logic on the network, which contradicts the minimal or other maximal lags. E.g. imagine that B can start minimum five days after the finish of A (F;S; 5) point-to-point relation but another relation describes that B should start maximum 4 days after the finish of A (F;S;max4). Figure 3: Transformation of relations with maximal lag into their minimal equivalent can result in loops. This definite contradiction cannot be solved. In this case, the value of the transformation loop will be positive, and the result for the project duration will increase by at least this value in every iteration even after the nth iteration. The steps below summarize the forward pass: Step 1 Let EiS= -∞ and OLD_EiS= -∞ ∀ i ∈ N; Let Ej=SS=0 and OLD_Ej=SS=0; Let h=0; Let No_of_Iter=0 Step 2 REPEAT There_were_changes:=FALSE; No_of_Iter:= No_of_Iter+1 REPEAT h:=h+1 Select any j activity that has not been selected in this iteration yet EjS = max { OLD_Ejs; (EiS + t ik + zikjl – t jl ∀ (Pik;Pjl) ∈ A*) }; EjF=EjS+d j IF EjS> OLD_EjS THEN There_were_changes:=TRUE UNTIL h=n Let OLD_EiS=Eis ∀ i ∈ N UNTIL No_of_iter>n or There_were_changes:=FALSE Step 3 IF No_of_Iter>n THEN There is no solution. (There is a loop with positive value.) IF There_were_changes:=FALSE THEN we arrived to a feasible optimal time policy (All activity dates remained unchanged after two iterations.) The rules of backward pass can be summarized as follows: Step 1 Let LiS= -∞ and OLD_LiS= -∞ ∀ i ∈ N; Let Lj=SS=Ej=sS and OLD_Lj=SS= Lj=SS; Let h=n; Step 2 REPEAT There_were_changes:=FALSE; REPEAT 340-6 Select any i activity that has not been selected in this iteration yet LiS = min { OLD_LiS; (LjS + t jk - zikjl – t il ∀ (Pik;Pjl) ∈ A*) }; LiF=LiS+d i IF LiS> OLD_LiS THEN There_were_changes:=TRUE h:=h-1 UNTIL h=0 Let OLD_LiS=Lis ∀ i ∈ N UNTIL There_were_changes:=FALSE Notes to the algorithm: • Loop detection was done during the forward pass, so there is no need for that during the backward pass. • Any order of activities can be used during the algorithm, which can largely modify the number of iterations. Here we used the ascending order of activities during the forward pass and the descending order during the backward pass. In the optimal case, the first iteration presents the results and the second iteration will validate this, in the pessimistic case, n+1 iterations are necessary. • Following the optimal order of the forward pass will be the worst during the backward pass, and vice versa. 4 SAMPLE PROJECT 4.1 Sample project: only minimal lags are allowed A small sample project is shown in Fig. 4 a) consisting only of relations with minimal lags. Results can be seen in Figure 4b), calculations can be tracked below. Forward pass: Only activity A can be selected. EAS=0; EAF=EAS+dA=0+6=6 Only activity B can be selected. EBS = {(EAS +t Ak + zA3B0 – t B0) }={(0+3+0-0)}=3; EBF=EBS+dB=3+6=9 Only activity C can be selected. ECS=max{(EAS+tA6+zA6C0–tC0);(EBS+tB2+zB2C0–tC0)}={(0+6+4-0);(3+2+2-0)}= 10; ECF=ECS+dC=15 Only activity D can be selected. EDS=max{(EBS+tB6+zB6D0–tD0);(ECS+tC3+zC3D0–tD0);(ECS+tC4+zC4D1–tD1); (ECS+tC5+zC5D2–tD2)}={(3+6+3-0);(10+3+0–0);(10+4+0–1);(10+5+0–2)}={12;13;13;13}=13; EDF=EDS+dD=17 Early dates for all activities have been calculated, the forward pass is finished. (See Fig. 4) 340-7 Figure 4a) Sample project with minimal lags. Figure 4b) Results of the calculations. Backward pass: Only activity D can be selected. LDF=17; LDS=LDF-dD=17-4=13 Only activity C can be selected. LCS =min{(LDS+tD2 –zC5D2 –tC5); (LDS+tD1 –zC4D1 –tC4); (LDS+tD0 –zC3D0 –tC3)}= min{(13+2-0-5);(13+1-0-4);(13+0-0-3)}=min{(10;10;10)}=10 LCF=LCS+dc=10+5=15 Only activity B can be selected. LBS =min{(LDS+tD0 –zC6D0 –tC6);(LCS+tC0 –zB2C0 –tB2)= min{(13+0-3-6);(10+0-2-2)}=min{(4;6)}=4 LBF=LBS+dB=4+6=10 Only activity A can be selected. LAS=min{(LBS+tB0–zA3B0 –tA3);(LCS+tC0 –zA6C0-tA6)=min{(4+0-0-3);(10+0-4-6)} =min{(1;0)}=0 LAF=LAS+dA=0+6=6 Late dates for all activities have been calculated, the backward pass is finished. (See Fig. 4) 4.2 Sample project: both minimal and maximal lags are allowed A small sample project is shown on Fig. 5a) consisting of relations with minimal and maximal lags. The network with the transformed maximal relation and with the results is shown in Fig. 5b). Due to the transformation loop, the iterative algorithm has to be used. Any order of the activities can be used. Here we use the A;B;D;C order for the forward pass. The calculations can be followed in Figure 6. Boxes of those activities that have been changed during the iteration are filled with grey. Iteration #1 EAS= max { OLD_EAs }=0; EAF=EAS+dA=0+6=6 EBS=max{OLD_EBS;(EAS+tA3+zA3B0-tB0);(ECS+tC0+zC0B2-tB2)}={-∞;(0+3+0-0};(-∞+0-2-2)}=3 EBF=EBS+dB=9 EDS=max{OLD_EDS;(EBS+tB6+zB6D0-tD0);(ECS+tC3+zC3D0-tD0);(ECS+tC4+zC4D1-tD1)(ECS+tC5+zC5D2-tD2)}={-∞; (3+6+3-0}; (-∞+3+0-0); (-∞+4+0-1); (-∞+5+0-2)}=12 EDF=EDS+dD=16 ECS=max{OLD_ECS;(EBS+tB2+zB2C0-tC0);(EAS+tA6+zA6C0-tC0)={-∞;(3+2+2-0};(0+6+4-0)}=10 ECF=ECS+dC=15 Figure 5a) Sample project with mixed lags. Figure 5b) Transformed network with the results 340-8 Iteration #2 EAS= max { OLD_EAs }=0; EAF=EAS+dA=0+6=6 EBS=max{OLD_EBS;(EAS+tA3+zA3B0-tB0);(ECS+tC0+zC0B2-tB2)}={3;(0+3+0-0};(10+0-2-2)}=6 EBF=EBS+dB=12 EDS=max{OLD_EDS;(EBS+tB6+zB6D0-tD0);(ECS+tC3+zC3D0-tD0);(ECS+tC4+zC4D1-tD1)(ECS+tC5+zC5D2-tD2)}={12; (6+6+3-0}; (10+3+0-0); (10+4+0-1); (10+5+0-2)}=15 EDF=EDS+dD=19 ECS=max{OLD_ECS;(EBS+tB2+zB2C0-tC0);(EAS+tA6+zA6C0-tC0)={10;(6+2+2-0};(0+6+4-0)}=10 ECF=ECS+dC=15 Iteration #3 EAS= max { OLD_EAs }=0; EAF=EAS+dA=0+6=6 EBS=max{OLD_EBS;(EAS+tA3+zA3B0-tB0);(ECS+tC0+zC0B2-tB2)}={3;(0+3+0-0};(10+0-2-2)}=6 EBF=EBS+dB=12 EDS=max{OLD_EDS;(EBS+tB6+zB6D0-tD0);(ECS+tC3+zC3D0-tD0);(ECS+tC4+zC4D1-tD1)(ECS+tC5+zC5D2-tD2)}={12; (6+6+3-0}; (10+3+0-0); (10+4+0-1); (10+5+0-2)}=15 EDF=EDS+dD=19 ECS=max{OLD_ECS;(EBS+tB2+zB2C0-tC0);(EAS+tA6+zA6C0-tC0)={10;(6+2+2-0};(0+6+4-0)}=10 ECF=ECS+dC=15 Figure 6: Forward pass computation. No activity dates have changed in the course of iteration #3; therefore the forward pass is finished. For the backward pass the D; B; C; A sequence is selected. Calculations can be followed below. Iteration #1 LDS= min{OLD_LDS; (nil) }=15; LDF=LDS+dD=19 LBS=min{OLD_LBS;(LDS+tD0-zB6D0-tB6);(LCS+tC0-zB2C0-tB2)}=min{∞;(15+0-3-6);( ∞+0-2-2)}=6 LBF=LBS+tB=12 LCS=min{OLD_LCS;(LBS+tB2-zC0B2-tC0);(LDS+tD0-zB3D0-tB3); (LDS+tD1-zB4D2-tB4) (LDS+tD2-zB5D2-tB5)}=min{∞;(6+2-(-2)-0);(15+0-0-3);(15+1-0-4);(15+2-0-5)}=10 LCF=LCS+tC=15 LAS=min{OLD_LAS;(LCS+tC0-zA6C0-tA6);(LBS+tB0-zA3B0-tA3)}=min{∞;(10+0-4-6);(6+0-0-3)}=0 LAF=LAS+tA=6 Iteration #2 340-9 LDS= min{OLD_LDS; (nil) }=15; LDF=LDS+dD=19 LBS=min{OLD_LBS;(LDS+tD0-zB6D0-tB6);(LCS+tC0-zB2C0-tB2)}=min{6;(15+0-3-6);(10+0-2-2)}=6 LBF=LBS+tB=12 LCS=min{OLD_LCS;(LBS+tB2-zC0B2-tC0);(LDS+tD0-zB3D0-tB3); (LDS+tD1-zB4D2-tB4) (LDS+tD2-zB5D2-tB5)}=min{10;(6+2-(-2)-0);(15+0-0-3);(15+1-0-4);(15+2-0-5)}=10 LCF=LCS+tC=15 LAS=min{OLD_LAS;(LCS+tC0-zA6C0-tA6);(LBS+tB0-zA3B0-tA3)}=min{0;(10+0-4-6);(6+0-0-3)}=0 LAF=LAS+tA=6 Activity dates have not changed during the iteration. Calculations are finished. Results of the backward pass (and the forward’s as well) can be seen in Fig. 5b. 5 DISCUSSIONS AND FURTHER RESEARCH A new ‘super’ precedence relationship based on the results of Francis & Mireco and Kim has been discussed in the paper. It has been shown that the traditional precedence relations (SS, SF, FS and FF with either minimal or maximal lags) could be derived from the new relation. It has also been shown that different results of parallel works e.g. bee-line relations can also be derived from this new ‘super’ relation; therefore claiming these results as a new technique is a wrong approach. This new relation forms a connection between two arbitrary points of two activities; therefore the name point-to-point relation fully describes the nature of this new relation. Following this logic, the traditional precedence relations, which could be called endpoint relations, form a subset of point-to-point relations as they connect the endpoints of the activities. Point-to-point relations affect the very fundaments of network techniques, therefore all definitions, generalizations, problems based on the ‘old’ precedence relations must be checked and modified accordingly, if necessary, including the definitions and calculations of floats, the definition of the critical path, the classification of critical activities (Weist 1981) (Hajdu 1996) (Walls & Lino 2001), the algorithms for resource optimization etc. To our best knowledge, this work has not been done yet. References Bellman, R.E. 1958 On a Routing Problem. Quarterly of Applied Mathematics 16 1959. 87-90 Douglas, E.E.; Calvery T. T. McDonald, D.F.; Winter, R.M. 2006. The Great Negative Lag Debate. 2006 AACE International Transactions PS 02.01.- PS 02.07 Fondahl, J.W 1961. A non-computer approach to the critical path method for the construction industry. Technical Report #9 The Construction Institute, Department of Civil Engineering, Stanford University, Stanford California Ford, L.R. 1956. Network Flow Theory. The Rand Corporation 1956. Francis, A., Miresco, E.T. 2000. Decision Support for Project Management Using a Chronographic Approach. Proceedings of the 2nd International Conference on Decision Making in Urban and Civil Engineering, 2000 Lyon, France, 845-856. Francis, A., Miresco, E.T. 2002. Decision Support for Project Management Using a Chronographic Approach. Journal of Decision Systems, Special issue JDS-DM in UCE: Decision Making in Urban and Civil Engineering, 11(3-4): 383-404. Hajdu, M. 1996. Network Scheduling Techniques For Construction Project Management. Kluwer Academic Publishers, ISBN 0-7923-4309-3 Hegazy, T & Menesi, W. 2010 Critical Path Segments Scheduling Technique. Journal of Construction Engineering and Management, 136(10): 1078-1085 IBM 1964. Users Manual for IBM 1440 Project Control System (PCS). 1964 Kim, S. 2010. Advanced Networking Technique Kimoondang, South Korea 2010 Kim, S. 2012. CPM Schedule Summarizing Function of the Beeline Diagramming Method. Journal of Asian Architecture and Building Engineering, 11(2) November 2012; 367-374 Plotnick FL, 2004 Introduction to Modified Sequence Logic, Conference Proceedings, PMICOS (first annual) Conference, April 25, 2004, Montreal, Canada Ponce de Leon, G. 2008 Graphical Planning method. PMICOS Annual Conference, Chicago, IL, 2008 340-10 Roy, G.B., 1959 Théorie des Graphes: Contribution de la théorie des graphes á l1 étude de certains problémes linéaries, Comptes rendus des Séances de l1 Acedémie des Sciences. séence du Avril 1959, s2437-2449, 1959 Roy, G.B. 1960. Contribution de la théorie des graphes à l’étude de certains problems d’ordonnancement", Comptes rendus de la 2ème conférence internationale sur la recherché opérationnelle, Aix-en-Provence, English Universities Press, Londres 171-185. Valls, V and Lino, 2001. Criticality Analysis in Activity-on-Node Networks with Minimal Time Lags. Annals of Operations Research, 102(1-4) 17-37 Wiest, J.D. 1981 Precedence diagramming method: Some unusual characteristics and their implications for project managers, Journal of Operations management, Volume 1/3 Feb. 1981. 121-130 340-11 5th International/11th Construction Specialty Conference 5e International/11e Conférence spécialisée sur la construction Vancouver, British Columbia June 8 to June 10, 2015 / 8 juin au 10 juin 2015 ONE RELATION TO RULE THEM ALL: THE POINT-TO-POINT PRECEDENCE RELATION THAT SUBSTITUTES THE EXISTING ONES Miklos Hajdu1,2,3 1 Ybl Miklos Faculty of Architecture and Civil Engineering, Szent István University, Hungary 2 Faculty of Architecture, Budapest University of Technology and Economics, Hungary 3 miklos.hajdu63@gmail.com Abstract: Precedence Diagram Method (PDM) has gained the widest acceptance in the scheduling practice in the last decades due to its modeling flexibility over other existing techniques, and to the relative simplicity of its mathematical background. The four basic precedence relationships have been serving planners for more than half a century. However, even this model is not flexible enough; proper modeling of overlapped activities seems to be a never-ending debate. Different practical and theoretical solutions have been proposed during the years for better modeling overlapped activities. The most promising among them is the development of a new type of relation that can connect any two arbitrary points of the related activities. These relations can be called point-to-point relations. Different authors in various ways have proposed similar solutions. To the best of our knowledge, the literature on the mathematical model of PDM using this new relation is lacking. Main results of the paper are: 1) standardized discussion of the different approaches to point-to-point relations; 2) proper mathematical model of PDM with point-to-point relations; 3) introduction of the algorithm that can handle point-to-point relations with both minimal and maximal lag to define the earliest and latest feasible time policy. 1 INTRODUCTION AND LITERATURE REVIEW Widely used network techniques are more than half a century old. The results of Fondahl, (Fondahl 1961), Roy (Roy 1959), (Roy 1960), IBM (IBM 1964) and many others have led to the present form of the Precedence Diagram Method, the prevailing network technique of our times. PDM has hardly changed during the decades in spite of the critiques it has received about its modeling capabilities. Proper modeling of overlapping activities seems to be a never-ending debate when traditional precedence relations are used, (Douglas et al. 2006) because traditional endpoint relations are simply not suitable for describing this kind of logic. Different solutions have been proposed using the traditional precedence relations; but fragmentation of activities and developments based on this idea (Tarek & Menesi 2010) seem to be the best theoretical solution despite the arising practical problems, namely the multiplication of the number of activities and precedence relations. Probably the fragmentation technique has given the idea of connecting the inner points of the activities, which will be discussed in this paper. These point-to-point relations connecting the internal points of the activities seem to be theoretically more suitable for modeling overlapping activities – especially if continuous activities are assumed - as multiple relations are allowed between the activities. To the best of our knowledge four partly parallel works regarding point-to-point relations can be found: Kim (Kim 2010, 2012) calls his new relations bee-line relations and the graphical representation Bee-line Diagram (BDM), while Francis and Miresco (Francis & Mireco 2000, 2002) call their new relations temporal functions and they call their graphical representation method 340-1 chronographic approach. Plotnick (Plotnick 2004) calls his method Relationship Diagramming method (RDM) using the term of ‘event’ for the internal points. Ponce de Leon (Ponce de Leon 2010) uses the term Graphical Diagramming Method (GDM) and connected internal points are called embedded nodes. Despite the differences in terminology and definitions, e.g. bee-line and RDM relation does not allow a lag between the connected inner points, maximal lags are defined only in the work of Francis and Miresco, the concept behind all these works is the same. All these improvements regarding the relationships can be seen as a new type of precedence relation that can substitute all traditional precedence relations, as it will be shown later. The goal of this paper is twofold: firstly, to remedy a common shortcoming of these works (authors have failed to present the mathematical model); secondly, to show that traditional precedence relationships can be derived from the general point-to-point relations discussed in this paper. A proper mathematical model and the algorithm will be introduced using standardized technical terminology. The new point-to-point relation can be seen as a generalization of traditional precedence relations. It will be shown that the existing traditional precedence relations are special cases of the point-to-point relations; they connect the endpoints of the activities instead of the internal points. 2 THE MATHEMATICAL MODEL 2.1 Notations Let a directed acyclic graph be given with one start (s) and one finish node (f). Let N = {1,2,…i…j…n} stand for the set of nodes also called activities. A will define the set of arcs, also called precedence relations. The ‘super’ relation defined later can have minimal or maximal lags, therefore Amin and Amax subsets are introduced for differentiating relations with minimal and maximal lags. In the algorithm, relations with maximal lags will be transformed into relations with minimal lags. In this case A* denotes the set of relations . An activity i is defined by its start and finish points Pis, PiF, shortly Si or Fi, or by any of the two aforementioned points and its duration di. Additional points of the activities can also be defined. Pik stands for the kth point of activity i. The relative place of the kth point of activity i is defined by the time span (ti k) from the start point of activity i (PiS). A relation can be defined between any lth internal point of activity j and any kth internal point of activity i by defining the time that must elapse between the two points (zi kjl). Therefore this ‘super’ precedence relation can be defined either by the points and the lag as (Pik;Pjl, zikjl) or by the relative positions of the points and the lag (ti k; tjl , zikjl). Explanation can be seen in Fig. 1. Lags can be defined using production volumes as well. Figure 1: Explanation of notations and the the ‘super’ precedence relation. (t ik ; t jl ; zikjl) 340-2 Let the time when a point is accomplished be called point or event time and denoted by Tik. This way TiS stands for the start, and TiF stands for the finish of activity i. Table 1 shows how the traditional relations and bee-line relations can be derived from the new ‘super’ relation. Transformation of temporal functions (Francis & Miresco 2002) and RDM relations is obvious so this is not presented here. If instead of time, the names of the points of the activities are used for describing the relation, then even the same notation can be used. (e.g. instead of SS100 days (S; S; 100 days) can be used.) Based on the above notations the following model can be defined. Table 1: ‘Super’ relation can be used instead of traditional and bee-line precedence relations Known precedence relations Equivalent point-to-point relation PDM Start-to-Start zi j ( 0 ; 0; ziSjS ) or ( S; S; ziSjS) Finish-to-Start zi j ( d i ; 0; ziFjS ) or ( F; S; ziFjS) Finish-to-Finish zi j ( d i ; d j; ziFjS ) or ( F; F; ziFjF) Start-to-Finish zi j ( 0 ; d j; ziSjS ) or ( S; F; ziSjF) BDM (t ik, t jl) (t ik; t jl ; 0) 2.2 The model The first two conditions tell that all precedence relations must be satisfied. [1] describes the precedence relations with minimal lags, while [2] describes the precedence relations with maximal lags. [1] Tjl –Tik ≥ zikjl ∀ (Pik;Pjl) ∈ Amin [2] Tjl –Tik ≤ zikjl ∀ (Pik;Pjl) ∈ Amax By definition Tik = TiS+tik and Tjl = TjS+tjl therefore [1] and [2] can be modified as: [1*] TjS – TiS ≥ zikjl – tjl + tik ∀ (Pik;Pjl) ∈ Amin [2*] TjS – TiS ≤ zikjl – tjl +tik ∀ (Pik;Pjl) ∈ Amax The finish of the activities can be calculated according to [3]. Activities are assumed to be continuous [4]. Let’s set the start of the project to zero. [5] [3] TiS +di = TiF ∀ i ∈ N [4] Tik - tik = TiS ∀ i ∈ N and ∃ Pik (Pik exist) [5] TsS = 0 The T policy that satisfies [1*], [2*], [3], [4], and [5] is called a feasible time policy. An infinite number of feasible time policies exist, but the objective of the model is to find that/those time policy/policies where the project duration is the minimum, that is [6] TfF − TsS → min that is TfF − 0 → min that is TfF → min This model is an LP model, so any LP solver can be used for solving it, furthermore, based on the simplistic structure of this LP problem different efficient primal dual algorithms can be developed. The solution shown below is based on the modification of the simplistic and widely used CPM/PDM time analysis. This approach is probably the easiest to digest for planning engineers. 340-3 3 ALGORITHMS 3.1 Point-to-point relations with minimal lag The goal of the algorithm is to find the optimal time policy, the earliest and the latest out of the existing – sometimes millions of – optimal time policies. The earliest optimal time policy is denoted by EiS and EiF. The latest optimal policy is denoted by LiS and LiF. The applied algorithm has two phases. The result of the first phase is the earliest optimal time policy, while the result of the second phase is the latest optimal time policy. Let’s suppose for the sake of simplicity that only relations with minimal lags are allowed in the network. In this case, the earliest start and finish of an activity j can only be calculated, if the earliest start dates for all its predecessors are known. As all precedence relations must be satisfied, the early start of a given j can be defined by the maximum of the shifts caused by the preceding relations of activity j, that is: [7] EjS = max { EiS + t ik + zikjl – t jl ∀ (Pik;Pjl) ∈ Amin } To start, an activity with known predecessors has to be found. In the beginning, only the start activity satisfies this condition: all of its predecessors are known because it does not have any. After these introductory thoughts, the steps of the first phase, that is the steps aiming to find the earliest time policy, can be summarized as follows: Step 1 Let EiS= -∞ and EiF=-∞ ∀ i ∈ N; Let ESS=0 Let g:=1 Step 2 REPEAT g:=g+1 Choose an activity j from the unknowns (EiS=-∞) with known predecessors only. IF there is no such activity then GO TO Step 3 EjS = max { EiS + t ik + zikjl – t jl ∀ (Pik;Pjl) ∈ Amin }; EjF=EjS+d j UNTIL g=n Step 3 IF g<n THEN STOP (There is a loop in the network.) ELSE p=EfF (Project duration is the same as the early finish of the finish activity.) During the backward pass, the latest optimal time policy will be defined. It is completed by working from the terminal activity to the initial activity in reverse direction of the arrows. It is based on the observation that the late activity times of an activity can only be calculated, if these dates are known for all of its successors. As all successor relations must be satisfied, the late start of a given i can be defined by the maximum of the shifts caused by the succeeding relations of activity i, that is: [8] LiS = min { LjS + t jk - zikjl – t il ∀ (Pik;Pjl) ∈ Amin } The rules of the backward pass can be summarized as follows: Step 1 Let LiS= ∞ and LiF= ∞ ∀ i ∈ N; Let Li=FS=p- df ; Let g:=1 Step 2 REPEAT g:=g+1 Choose an activity i from the unknowns (LiS=∞) with known successors only. LiS = min { LjS + t jk - zikjl – t il ∀ (Pik;Pjl) ∈ Amin } ; LiF=LiS+d i UNTIL g=n (Note: Loop detection is not necessary during the backward pass.) 340-4 3.2 Point-to-point relations with mixed lags Calculations with mixed lags require more computational steps. Maximal relations have to be transformed into minimal relations first. Comparing conditions [1] and [2], it can be seen that the difference between a relation with minimal or maximal lags lies in the direction of the operand. Transforming a relation with maximal lag into a relation with minimal lag requires a simple multiplication by -1. [2] Tjl –Tik ≤ zikjl ∀ (Pik;Pjl) ∈ Amax / *(-1) [9] Tik –Tjl ≤ - zjlik ∀ (Pik;Pjl) ∈ Amax This is nothing else but a relation from j to i with a negative minimal lag (see Fig. 2). Figure 2: Point-to-point relation with maximal lag a) and its minimal equivalent b) Traditional precedence relations with maximal lags, and their transformed equivalent minimal lags can be found in Table 2. Table 2: Traditional precedence relations and their equivalent minimal versions. Traditional precedence relations with maximal lag Equivalent point-to-point relation with maximal lag Transformed equivalent precedence relations with minimal lag* Transformed equivalent point-to-point relation with minimal lag* maxSSz max(0; 0; z) SS-z (0; 0; -z) maxFSz max(di; 0; z) SF-z (0, dj; -z) maxFFz max(di; dj; z) FF-z (di; dj; -z) maxSFz max(0, dj; z) FS-z (di; 0; -z) * Transformed equivalents go in the opposite direction However, converting relations with maximal lags into their equivalent minimal relations can result in so-called transformation loops. In Fig. 3 it can be seen that there is a loop between B and C. The simple time analysis presented in 3.1 cannot be used in case of loops. One can easily check it by selecting the activities. E.g. during the forward pass activity A has to be chosen first. After that none of the activities can be selected, B has two predecessors but only A is known and C is not; C has two predecessors but only A is known and B is not, so the algorithm will stop here. In case of loops, different algorithms exist to find the longest path. We will use the modified version of the algorithm developed by Bellman (Bellman, 1958) and Ford (1956) for finding the shortest path between any two points of a cyclic graph. The algorithm is based on the idea that during the forward pass all activities are calculated using the dates of their predecessors even if those have not taken their final dates yet. When all activities have been calculated this way, it has to be checked whether there have been changes in activity dates or not. If the answer is yes, then the entire calculation must be repeated again and again, until we come to the results we had in the previous iteration. In every iteration, at least 340-5 one activity takes its final value, so after maximum n iterations we get the results. Usually much fewer iterations are necessary. If the nth iteration still brings changes, then the network cannot be solved due to the maximal relations that probably impose logic on the network, which contradicts the minimal or other maximal lags. E.g. imagine that B can start minimum five days after the finish of A (F;S; 5) point-to-point relation but another relation describes that B should start maximum 4 days after the finish of A (F;S;max4). Figure 3: Transformation of relations with maximal lag into their minimal equivalent can result in loops. This definite contradiction cannot be solved. In this case, the value of the transformation loop will be positive, and the result for the project duration will increase by at least this value in every iteration even after the nth iteration. The steps below summarize the forward pass: Step 1 Let EiS= -∞ and OLD_EiS= -∞ ∀ i ∈ N; Let Ej=SS=0 and OLD_Ej=SS=0; Let h=0; Let No_of_Iter=0 Step 2 REPEAT There_were_changes:=FALSE; No_of_Iter:= No_of_Iter+1 REPEAT h:=h+1 Select any j activity that has not been selected in this iteration yet EjS = max { OLD_Ejs; (EiS + t ik + zikjl – t jl ∀ (Pik;Pjl) ∈ A*) }; EjF=EjS+d j IF EjS> OLD_EjS THEN There_were_changes:=TRUE UNTIL h=n Let OLD_EiS=Eis ∀ i ∈ N UNTIL No_of_iter>n or There_were_changes:=FALSE Step 3 IF No_of_Iter>n THEN There is no solution. (There is a loop with positive value.) IF There_were_changes:=FALSE THEN we arrived to a feasible optimal time policy (All activity dates remained unchanged after two iterations.) The rules of backward pass can be summarized as follows: Step 1 Let LiS= -∞ and OLD_LiS= -∞ ∀ i ∈ N; Let Lj=SS=Ej=sS and OLD_Lj=SS= Lj=SS; Let h=n; Step 2 REPEAT There_were_changes:=FALSE; REPEAT 340-6 Select any i activity that has not been selected in this iteration yet LiS = min { OLD_LiS; (LjS + t jk - zikjl – t il ∀ (Pik;Pjl) ∈ A*) }; LiF=LiS+d i IF LiS> OLD_LiS THEN There_were_changes:=TRUE h:=h-1 UNTIL h=0 Let OLD_LiS=Lis ∀ i ∈ N UNTIL There_were_changes:=FALSE Notes to the algorithm: • Loop detection was done during the forward pass, so there is no need for that during the backward pass. • Any order of activities can be used during the algorithm, which can largely modify the number of iterations. Here we used the ascending order of activities during the forward pass and the descending order during the backward pass. In the optimal case, the first iteration presents the results and the second iteration will validate this, in the pessimistic case, n+1 iterations are necessary. • Following the optimal order of the forward pass will be the worst during the backward pass, and vice versa. 4 SAMPLE PROJECT 4.1 Sample project: only minimal lags are allowed A small sample project is shown in Fig. 4 a) consisting only of relations with minimal lags. Results can be seen in Figure 4b), calculations can be tracked below. Forward pass: Only activity A can be selected. EAS=0; EAF=EAS+dA=0+6=6 Only activity B can be selected. EBS = {(EAS +t Ak + zA3B0 – t B0) }={(0+3+0-0)}=3; EBF=EBS+dB=3+6=9 Only activity C can be selected. ECS=max{(EAS+tA6+zA6C0–tC0);(EBS+tB2+zB2C0–tC0)}={(0+6+4-0);(3+2+2-0)}= 10; ECF=ECS+dC=15 Only activity D can be selected. EDS=max{(EBS+tB6+zB6D0–tD0);(ECS+tC3+zC3D0–tD0);(ECS+tC4+zC4D1–tD1); (ECS+tC5+zC5D2–tD2)}={(3+6+3-0);(10+3+0–0);(10+4+0–1);(10+5+0–2)}={12;13;13;13}=13; EDF=EDS+dD=17 Early dates for all activities have been calculated, the forward pass is finished. (See Fig. 4) 340-7 Figure 4a) Sample project with minimal lags. Figure 4b) Results of the calculations. Backward pass: Only activity D can be selected. LDF=17; LDS=LDF-dD=17-4=13 Only activity C can be selected. LCS =min{(LDS+tD2 –zC5D2 –tC5); (LDS+tD1 –zC4D1 –tC4); (LDS+tD0 –zC3D0 –tC3)}= min{(13+2-0-5);(13+1-0-4);(13+0-0-3)}=min{(10;10;10)}=10 LCF=LCS+dc=10+5=15 Only activity B can be selected. LBS =min{(LDS+tD0 –zC6D0 –tC6);(LCS+tC0 –zB2C0 –tB2)= min{(13+0-3-6);(10+0-2-2)}=min{(4;6)}=4 LBF=LBS+dB=4+6=10 Only activity A can be selected. LAS=min{(LBS+tB0–zA3B0 –tA3);(LCS+tC0 –zA6C0-tA6)=min{(4+0-0-3);(10+0-4-6)} =min{(1;0)}=0 LAF=LAS+dA=0+6=6 Late dates for all activities have been calculated, the backward pass is finished. (See Fig. 4) 4.2 Sample project: both minimal and maximal lags are allowed A small sample project is shown on Fig. 5a) consisting of relations with minimal and maximal lags. The network with the transformed maximal relation and with the results is shown in Fig. 5b). Due to the transformation loop, the iterative algorithm has to be used. Any order of the activities can be used. Here we use the A;B;D;C order for the forward pass. The calculations can be followed in Figure 6. Boxes of those activities that have been changed during the iteration are filled with grey. Iteration #1 EAS= max { OLD_EAs }=0; EAF=EAS+dA=0+6=6 EBS=max{OLD_EBS;(EAS+tA3+zA3B0-tB0);(ECS+tC0+zC0B2-tB2)}={-∞;(0+3+0-0};(-∞+0-2-2)}=3 EBF=EBS+dB=9 EDS=max{OLD_EDS;(EBS+tB6+zB6D0-tD0);(ECS+tC3+zC3D0-tD0);(ECS+tC4+zC4D1-tD1)(ECS+tC5+zC5D2-tD2)}={-∞; (3+6+3-0}; (-∞+3+0-0); (-∞+4+0-1); (-∞+5+0-2)}=12 EDF=EDS+dD=16 ECS=max{OLD_ECS;(EBS+tB2+zB2C0-tC0);(EAS+tA6+zA6C0-tC0)={-∞;(3+2+2-0};(0+6+4-0)}=10 ECF=ECS+dC=15 Figure 5a) Sample project with mixed lags. Figure 5b) Transformed network with the results 340-8 Iteration #2 EAS= max { OLD_EAs }=0; EAF=EAS+dA=0+6=6 EBS=max{OLD_EBS;(EAS+tA3+zA3B0-tB0);(ECS+tC0+zC0B2-tB2)}={3;(0+3+0-0};(10+0-2-2)}=6 EBF=EBS+dB=12 EDS=max{OLD_EDS;(EBS+tB6+zB6D0-tD0);(ECS+tC3+zC3D0-tD0);(ECS+tC4+zC4D1-tD1)(ECS+tC5+zC5D2-tD2)}={12; (6+6+3-0}; (10+3+0-0); (10+4+0-1); (10+5+0-2)}=15 EDF=EDS+dD=19 ECS=max{OLD_ECS;(EBS+tB2+zB2C0-tC0);(EAS+tA6+zA6C0-tC0)={10;(6+2+2-0};(0+6+4-0)}=10 ECF=ECS+dC=15 Iteration #3 EAS= max { OLD_EAs }=0; EAF=EAS+dA=0+6=6 EBS=max{OLD_EBS;(EAS+tA3+zA3B0-tB0);(ECS+tC0+zC0B2-tB2)}={3;(0+3+0-0};(10+0-2-2)}=6 EBF=EBS+dB=12 EDS=max{OLD_EDS;(EBS+tB6+zB6D0-tD0);(ECS+tC3+zC3D0-tD0);(ECS+tC4+zC4D1-tD1)(ECS+tC5+zC5D2-tD2)}={12; (6+6+3-0}; (10+3+0-0); (10+4+0-1); (10+5+0-2)}=15 EDF=EDS+dD=19 ECS=max{OLD_ECS;(EBS+tB2+zB2C0-tC0);(EAS+tA6+zA6C0-tC0)={10;(6+2+2-0};(0+6+4-0)}=10 ECF=ECS+dC=15 Figure 6: Forward pass computation. No activity dates have changed in the course of iteration #3; therefore the forward pass is finished. For the backward pass the D; B; C; A sequence is selected. Calculations can be followed below. Iteration #1 LDS= min{OLD_LDS; (nil) }=15; LDF=LDS+dD=19 LBS=min{OLD_LBS;(LDS+tD0-zB6D0-tB6);(LCS+tC0-zB2C0-tB2)}=min{∞;(15+0-3-6);( ∞+0-2-2)}=6 LBF=LBS+tB=12 LCS=min{OLD_LCS;(LBS+tB2-zC0B2-tC0);(LDS+tD0-zB3D0-tB3); (LDS+tD1-zB4D2-tB4) (LDS+tD2-zB5D2-tB5)}=min{∞;(6+2-(-2)-0);(15+0-0-3);(15+1-0-4);(15+2-0-5)}=10 LCF=LCS+tC=15 LAS=min{OLD_LAS;(LCS+tC0-zA6C0-tA6);(LBS+tB0-zA3B0-tA3)}=min{∞;(10+0-4-6);(6+0-0-3)}=0 LAF=LAS+tA=6 Iteration #2 340-9 LDS= min{OLD_LDS; (nil) }=15; LDF=LDS+dD=19 LBS=min{OLD_LBS;(LDS+tD0-zB6D0-tB6);(LCS+tC0-zB2C0-tB2)}=min{6;(15+0-3-6);(10+0-2-2)}=6 LBF=LBS+tB=12 LCS=min{OLD_LCS;(LBS+tB2-zC0B2-tC0);(LDS+tD0-zB3D0-tB3); (LDS+tD1-zB4D2-tB4) (LDS+tD2-zB5D2-tB5)}=min{10;(6+2-(-2)-0);(15+0-0-3);(15+1-0-4);(15+2-0-5)}=10 LCF=LCS+tC=15 LAS=min{OLD_LAS;(LCS+tC0-zA6C0-tA6);(LBS+tB0-zA3B0-tA3)}=min{0;(10+0-4-6);(6+0-0-3)}=0 LAF=LAS+tA=6 Activity dates have not changed during the iteration. Calculations are finished. Results of the backward pass (and the forward’s as well) can be seen in Fig. 5b. 5 DISCUSSIONS AND FURTHER RESEARCH A new ‘super’ precedence relationship based on the results of Francis & Mireco and Kim has been discussed in the paper. It has been shown that the traditional precedence relations (SS, SF, FS and FF with either minimal or maximal lags) could be derived from the new relation. It has also been shown that different results of parallel works e.g. bee-line relations can also be derived from this new ‘super’ relation; therefore claiming these results as a new technique is a wrong approach. This new relation forms a connection between two arbitrary points of two activities; therefore the name point-to-point relation fully describes the nature of this new relation. Following this logic, the traditional precedence relations, which could be called endpoint relations, form a subset of point-to-point relations as they connect the endpoints of the activities. Point-to-point relations affect the very fundaments of network techniques, therefore all definitions, generalizations, problems based on the ‘old’ precedence relations must be checked and modified accordingly, if necessary, including the definitions and calculations of floats, the definition of the critical path, the classification of critical activities (Weist 1981) (Hajdu 1996) (Walls & Lino 2001), the algorithms for resource optimization etc. To our best knowledge, this work has not been done yet. References Bellman, R.E. 1958 On a Routing Problem. Quarterly of Applied Mathematics 16 1959. 87-90 Douglas, E.E.; Calvery T. T. McDonald, D.F.; Winter, R.M. 2006. The Great Negative Lag Debate. 2006 AACE International Transactions PS 02.01.- PS 02.07 Fondahl, J.W 1961. A non-computer approach to the critical path method for the construction industry. Technical Report #9 The Construction Institute, Department of Civil Engineering, Stanford University, Stanford California Ford, L.R. 1956. Network Flow Theory. The Rand Corporation 1956. Francis, A., Miresco, E.T. 2000. Decision Support for Project Management Using a Chronographic Approach. Proceedings of the 2nd International Conference on Decision Making in Urban and Civil Engineering, 2000 Lyon, France, 845-856. Francis, A., Miresco, E.T. 2002. Decision Support for Project Management Using a Chronographic Approach. Journal of Decision Systems, Special issue JDS-DM in UCE: Decision Making in Urban and Civil Engineering, 11(3-4): 383-404. Hajdu, M. 1996. Network Scheduling Techniques For Construction Project Management. Kluwer Academic Publishers, ISBN 0-7923-4309-3 Hegazy, T & Menesi, W. 2010 Critical Path Segments Scheduling Technique. Journal of Construction Engineering and Management, 136(10): 1078-1085 IBM 1964. Users Manual for IBM 1440 Project Control System (PCS). 1964 Kim, S. 2010. Advanced Networking Technique Kimoondang, South Korea 2010 Kim, S. 2012. CPM Schedule Summarizing Function of the Beeline Diagramming Method. Journal of Asian Architecture and Building Engineering, 11(2) November 2012; 367-374 Plotnick FL, 2004 Introduction to Modified Sequence Logic, Conference Proceedings, PMICOS (first annual) Conference, April 25, 2004, Montreal, Canada Ponce de Leon, G. 2008 Graphical Planning method. PMICOS Annual Conference, Chicago, IL, 2008 340-10 Roy, G.B., 1959 Théorie des Graphes: Contribution de la théorie des graphes á l1 étude de certains problémes linéaries, Comptes rendus des Séances de l1 Acedémie des Sciences. séence du Avril 1959, s2437-2449, 1959 Roy, G.B. 1960. Contribution de la théorie des graphes à l’étude de certains problems d’ordonnancement", Comptes rendus de la 2ème conférence internationale sur la recherché opérationnelle, Aix-en-Provence, English Universities Press, Londres 171-185. Valls, V and Lino, 2001. Criticality Analysis in Activity-on-Node Networks with Minimal Time Lags. Annals of Operations Research, 102(1-4) 17-37 Wiest, J.D. 1981 Precedence diagramming method: Some unusual characteristics and their implications for project managers, Journal of Operations management, Volume 1/3 Feb. 1981. 121-130 340-11 ONE RELATION TO RULE THEM ALL Miklós Hajdu Budapest University of Technology The point-‐to-‐point relaDon that subsDtute the exisDng ones AND OTHER INTERESTING ISSUES Such as the characterisDcs of criDcal acDviDes when point-‐to-‐point relaDons are in use or conDnious relaDons or relaDons without direcDon. 2015-‐07-‐23 2:57 PM Miklós Hajdu ICSC2015 Vancouver, Canada 2 SS0 SS0 START SS0 SS3 A1 3d FS 0 B1 3d FS 0 C1 5d SS3 SS0 F1 7d FS0 G1 4d H1 4d FS-‐2 FS 0 max FS2 50m,0m, 0d 100 m, 50 m,0d 150 m, 100m,0d F S 3 FS5 FS3 SS 3 A2 5d FS2 B2 2d SS 5 E2 4d 50m F2 5d FS0 G2 5d FF 3 SS2 FF2 50 m 50m,0m,0d 100 m,50m,0d FS-‐3 FS-‐3 A3 6d FS 0 B3 5d SS3 FF3 C3 5d D3 4d FS0 E3 4d 10d F3 4d 50m max50 G3 6d FS0 H3 4d FS0 50 ,m 50 m 50 m 10 d 10 d FS 0 max FS0 A5 4d FS 0 B4 7d FS0 C4 6d FS0 maxFS0 D4 3d 50m E4 5d FS0 G4 4d H4 5d FS0 50m,0m, 0d 100m,50m,0d 150m,100m,0d 50 m 50 m 50 m 50 m 10 d 50m A5 7d C5 4d FS0 D5 7d F,S,0 E5 5d F,S,0 F5 5d FS0 G5 5d FS0 H5 3d F,S, 0 50 m 50m 50m 50m 50m A6 5d FS 0 maxFS 0 B6 6d FS0 C6 8d FS3 D6 2d FS0 E6 4d FS0 F6 4d H6 5d FF0 FF0 FF0 FF0 FF0 FF0 FF0 FF0 END Things we do not like in this network... 2015-‐07-‐23 2:57 PM Miklós Hajdu ICSC2015 Vancouver, Canada 3 A1 3d A2 5d FS -‐2d NegaDve lag Why we do not like this? 2d Dme locaDon Only one point is under control….. and we can control it only in the future … 2015-‐07-‐23 2:57 PM Miklós Hajdu ICSC2015 Vancouver, Canada 4 SS0 SS0 START SS0 SS3 A1 3d FS 0 B1 3d FS 0 C1 5d SS3 SS0 F1 7d FS0 G1 4d H1 4d FS-‐2 FS 0 max FS2 50m,0m, 0d 100 m, 50 m,0d 150 m, 100m,0d F S 3 FS5 FS3 SS 3 A2 5d FS2 B2 2d SS 5 E2 4d 50m F2 5d FS0 G2 5d FF 3 SS2 FF2 50 m 50m,0m,0d 100 m,50m,0d FS-‐3 FS-‐3 A3 6d FS 0 B3 5d SS3 FF3 C3 5d D3 4d FS0 E3 4d 10d F3 4d 50m max50 G3 6d FS0 H3 4d FS0 50 ,m 50 m 50 m 10 d 10 d FS 0 max FS0 A5 4d FS 0 B4 7d FS0 C4 6d FS0 maxFS0 D4 3d 50m E4 5d FS0 G4 4d H4 5d FS0 50m,0m, 0d 100m,50m,0d 150m,100m,0d 50 m 50 m 50 m 50 m 10 d 50m A5 7d C5 4d FS0 D5 7d F,S,0 E5 5d F,S,0 F5 5d FS0 G5 5d FS0 H5 3d F,S, 0 50 m 50m 50m 50m 50m A6 5d FS 0 maxFS 0 B6 6d FS0 C6 8d FS3 D6 2d FS0 E6 4d FS0 F6 4d H6 5d FF0 FF0 FF0 FF0 FF0 FF0 FF0 FF0 END Things we do not like in this network... 2015-‐07-‐23 2:57 PM Miklós Hajdu ICSC2015 Vancouver, Canada 5 A2 5d A3 6d FF 2d SS 2d CombinaDon of SS and FF ... Only two points are under control….. anything can happen between them 2d 2d Dme locaDon Why we do not like this? 2015-‐07-‐23 2:57 PM Miklós Hajdu ICSC2015 Vancouver, Canada 6 SS0 SS0 START SS0 SS3 A1 3d FS 0 B1 3d FS 0 C1 5d SS3 SS0 F1 7d FS0 G1 4d H1 4d FS-‐2 FS 0 max FS2 50m,0m, 0d 100 m, 50 m,0d 150 m, 100m,0d F S 3 FS5 FS3 SS 3 A2 5d FS2 B2 2d SS 5 E2 4d 50m F2 5d FS0 G2 5d FF 3 SS2 FF2 50 m 50m,0m,0d 100 m,50m,0d FS-‐3 FS-‐3 A3 6d FS 0 B3 5d SS3 FF3 C3 5d D3 4d FS0 E3 4d 10d F3 4d 50m max50 G3 6d FS0 H3 4d FS0 50 ,m 50 m 50 m 10 d 10 d FS 0 max FS0 A5 4d FS 0 B4 7d FS0 C4 6d FS0 maxFS0 D4 3d 50m E4 5d FS0 G4 4d H4 5d FS0 50m,0m, 0d 100m,50m,0d 150m,100m,0d 50 m 50 m 50 m 50 m 10 d 50m A5 7d C5 4d FS0 D5 7d F,S,0 E5 5d F,S,0 F5 5d FS0 G5 5d FS0 H5 3d F,S, 0 50 m 50m 50m 50m 50m A6 5d FS 0 maxFS 0 B6 6d FS0 C6 8d FS3 D6 2d FS0 E6 4d FS0 F6 4d H6 5d FF0 FF0 FF0 FF0 FF0 FF0 FF0 FF0 END Things we do not like in this network… unders and yet… maxFS2 2015-‐07-‐23 2:57 PM Miklós Hajdu ICSC2015 Vancouver, Canada 7 A2 5d B1 3d FS 2d FS0 Maximal relaDons... B2 2d Dme acDviDes B1 B2 A2 maxFS2 B1 -‐ excavaDon for basements B2 -‐ retaining wall 2015-‐07-‐23 2:57 PM Miklós Hajdu ICSC2015 Vancouver, Canada 8 SS0 SS0 START SS0 SS3 A1 3d FS 0 B1 3d FS 0 C1 5d SS3 SS0 F1 7d FS0 G1 4d H1 4d FS-‐2 FS 0 max FS2 50m,0m, 0d 100 m, 50 m,0d 150 m, 100m,0d F S 3 FS5 FS3 SS 3 A2 5d FS2 B2 2d SS 5 E2 4d 50m F2 5d FS0 G2 5d FF 3 SS2 FF2 50 m 50m,0m,0d 100 m,50m,0d FS-‐3 FS-‐3 A3 6d FS 0 B3 5d SS3 FF3 C3 5d D3 4d FS0 E3 4d 10d F3 4d 50m max50 G3 6d FS0 H3 4d FS0 50 ,m 50 m 50 m 10 d 10 d FS 0 max FS2 A5 4d FS 0 B4 7d FS0 C4 6d FS0 maxFS0 D4 3d 50m E4 5d FS0 G4 4d H4 5d FS0 50m,0m, 0d 100m,50m,0d 150m,100m,0d 50 m 50 m 50 m 50 m 10 d 50m A5 7d C5 4d FS0 D5 7d F,S,0 E5 5d F,S,0 F5 5d FS0 G5 5d FS0 H5 3d F,S, 0 50 m 50m 50m 50m 50m A6 5d FS 0 maxFS 0 B6 6d FS0 C6 8d FS3 D6 2d FS0 E6 4d FS0 F6 4d H6 5d FF0 FF0 FF0 FF0 FF0 FF0 FF0 FF0 END Things we do not understand yet… 2015-‐07-‐23 2:57 PM Miklós Hajdu ICSC2015 Vancouver, Canada 9 C1 5d C3 5d 50m,0m,0d Point-‐to-‐point relaDons... 100m,50m,0d 150m,100m,0d C1 5d C3 5d Points can be defined using Dme or volume data Instead of 0day, or 0m S can be used to idenDfy the Start point Instead of 5day, or 150m F can be used to idenDfy the Finish point Conclusion: Point-‐to-‐point relaDons can replace the tradiDonal four precedence relaDonships 2015-‐07-‐23 2:57 PM Miklós Hajdu ICSC2015 Vancouver, Canada 10 C1 5d C3 5d 50m,0m,0d Point-‐to-‐point relaDons... 100m,50m,0d 150m,100m,0d Francis and Miresko 2000 Plotnick 2004 Ponce de Leon 2008 Kim 2010 Hegazy 2010 Liberzon (Spider Project) 2010 The mathemaDcal model, that handle both minimal and maximal relaDons and the algorithm is in the paper. 2015-‐07-‐23 2:57 PM Miklós Hajdu ICSC2015 Vancouver, Canada 11 SS0 SS0 START SS0 SS3 A1 3d FS 0 B1 3d FS 0 C1 5d SS3 SS0 F1 7d FS0 G1 4d H1 4d FS-‐2 FS 0 max FS2 50m,0m, 0d 100 m, 50 m,0d 150 m, 100m,0d F S 3 FS5 FS3 SS 3 A2 5d FS2 B2 2d SS 5 E2 4d 50m F2 5d G2 5d FF 3 SS2 FF2 50 m 50m,0m,0d 100 m,50m,0d FS-‐3 FS-‐3 A3 6d FS 0 B3 5d SS3 FF3 C3 5d D3 4d FS0 E3 4d 10d F3 4d 50m max50 G3 6d FS0 H3 4d FS0 50 ,m 50 m 50 m 10 d 10 d FS 0 max FS2 A5 4d FS 0 B4 7d FS0 C4 6d FS0 maxFS0 D4 3d 50m E4 5d FS0 G4 4d H4 5d FS0 50m,0m, 0d 100m,50m,0d 150m,100m,0d 50 m 50 m 50 m 50 m 10 d 50m A5 7d C5 4d FS0 D5 7d F,S,0 E5 5d F,S,0 F5 5d FS0 G5 5d FS0 H5 3d F,S, 0 50 m 50m 50m 50m 50m A6 5d FS 0 maxFS 0 B6 6d FS0 C6 8d FS3 D6 2d FS0 E6 4d FS0 F6 4d H6 5d FF0 FF0 FF0 FF0 FF0 FF0 FF0 FF0 END Things we do not understand yet… 2015-‐07-‐23 2:57 PM Miklós Hajdu ICSC2015 Vancouver, Canada 12 ConDnuous relaDons…. C3 5d C4 6d 50m C3 50m C4 Control all the points that belong to the same Dme (volume/locaDon lag) 2015-‐07-‐23 2:57 PM Miklós Hajdu ICSC2015 Vancouver, Canada 13 ConDnuous relaDons…… C3 5d C4 6d 1 day C3 1 day C4 …or belong to the same locaDon (Dme lag) 2015-‐07-‐23 2:57 PM Miklós Hajdu ICSC2015 Vancouver, Canada 14 ConDnuous relaDons…… C3 5d C4 6d 1 day Model, algorithm with minimal and maximal Dme and volume lags can bee seen at 2015-‐07-‐23 2:57 PM Miklós Hajdu ICSC2015 Vancouver, Canada 15 SS0 SS0 START SS0 SS3 A1 3d FS 0 B1 3d FS 0 C1 5d SS3 SS0 F1 7d FS0 G1 4d H1 4d FS-‐2 FS 0 max FS2 50m,0m, 0d 100 m, 50 m,0d 150 m, 100m,0d F S 3 FS5 FS3 SS 3 A2 5d FS2 B2 2d SS 5 E2 4d 50m F2 5d G2 5d FF 3 SS2 FF2 50 m 50m,0m,0d 100 m,50m,0d FS-‐3 FS-‐3 A3 6d FS 0 B3 5d SS3 FF3 C3 5d D3 4d FS0 E3 4d 10d F3 4d 50m max50 G3 6d FS0 H3 4d FS0 50 ,m 50 m 50 m 10 d 10 d FS 0 max FS2 A5 4d FS 0 B4 7d FS0 C4 6d FS0 maxFS0 D4 3d 50m E4 5d FS0 G4 4d H4 5d FS0 50m,0m, 0d 100m,50m,0d 150m,100m,0d 50 m 50 m 50 m 50 m 10 d 50m A5 7d C5 4d FS0 D5 7d F,S,0 E5 5d F,S,0 F5 5d FS0 G5 5d FS0 H5 3d F,S, 0 50 m 50m 50m 50m 50m A6 5d FS 0 maxFS 0 B6 6d FS0 C6 8d FS3 D6 2d FS0 E6 4d FS0 F6 4d H6 5d FF0 FF0 FF0 FF0 FF0 FF0 FF0 FF0 END Things we do not understand yet… 2015-‐07-‐23 2:57 PM Miklós Hajdu ICSC2015 Vancouver, Canada 16 A1 3d B1 3d FS 0 RelaDonships without direcDon… A1 3d B1 3d FS 0 A1 3d B1 3d FS 0 This can be this or this Can be seen at from 2015-‐07-‐23 2:57 PM Miklós Hajdu ICSC2015 Vancouver, Canada 17 Conclusions • Using negaDve lag for modeling overlapping is the worst pracDce • CombinaDon of SS and FF is a bit befer, at least the start and the finish points are under control • Point-‐to-‐point relaDons are acceptable from pracDcal point oif view. The number of controlled points is upon the planner discreDon. (Minimal and maximal lags are allowed) • ConDnuous relaDons are the best for modelling acDvity overlapping. All the point are under control. (Time and volume lags, maximal and minimal lags can be used. • RelaDons without direcDons are useful for describing relaDons conencted to scrace resources. 2:57 PM Miklós Hajdu ICSC2015 Vancouver, Canada 18 Disccussions • Due the the new type of precedence relaDons such as point-‐to-‐point, conDnuous and undirected relaDonships all the former definiDons, developments, problems, algorithms that were based on the tradiDonal four relaDonships must be examined again. • Examples are could be: definiDon of floats, criDcal path, criDcal acDvity characterisDcs, Dme-‐cost trade off problems, resource leveling and allocaDon problems etc. 2:57 PM Miklós Hajdu ICSC2015 Vancouver, Canada 19 A short example Is this a • normal criDcal, or • neutral criDcal, or • reverse criDcal, or • bi criDcal, or • decreasing neutral increasing normal criDcal, or • decreasing reverse incresing neutral criDcal acDvity? this characterizaDon valid in case of poin-‐to-‐point relaDons? Or in case of conDnuous relaDons? 2015-‐07-‐23 2:57 PM Miklós Hajdu ICSC2015 Vancouver, Canada 20 Thank you for your afenDon!
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- International Construction Specialty Conference of the Canadian Society for Civil Engineering (ICSC) (5th : 2015) /
- One relation to rule them all : the point-to-point...
Open Collections
International Construction Specialty Conference of the Canadian Society for Civil Engineering (ICSC) (5th : 2015)
One relation to rule them all : the point-to-point precedence relation that substitutes the existing… Hajdu, Miklos Jun 30, 2015
Page Metadata
Item Metadata
Title | One relation to rule them all : the point-to-point precedence relation that substitutes the existing ones |
Creator |
Hajdu, Miklos |
Contributor | International Construction Specialty Conference (5th : 2015 : Vancouver, B.C.) Canadian Society for Civil Engineering |
Date Issued | 2015-06 |
Description | Precedence Diagram Method (PDM) has gained the widest acceptance in the scheduling practice in the last decades due to its modeling flexibility over other existing techniques, and to the relative simplicity of its mathematical background. The four basic precedence relationships have been serving planners for more than half a century. However, even this model is not flexible enough; proper modeling of overlapped activities seems to be a never-ending debate. Different practical and theoretical solutions have been proposed during the years for better modeling overlapped activities. The most promising among them is the development of a new type of relation that can connect any two arbitrary points of the related activities. These relations can be called point-to-point relations. Different authors in various ways have proposed similar solutions. To the best of our knowledge, the literature on the mathematical model of PDM using this new relation is lacking. Main results of the paper are: 1) standardized discussion of the different approaches to point-to-point relations; 2) proper mathematical model of PDM with point-to-point relations; 3) introduction of the algorithm that can handle point-to-point relations with both minimal and maximal lag to define the earliest and latest feasible time policy. |
Genre |
Conference Paper |
Type |
Text |
Language | eng |
Date Available | 2015-11-26 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivs 2.5 Canada |
DOI | 10.14288/1.0076408 |
URI | http://hdl.handle.net/2429/53601 |
Affiliation |
Non UBC |
Citation | Froese, T. M., Newton, L., Sadeghpour, F. & Vanier, D. J. (EDs.) (2015). Proceedings of ICSC15: The Canadian Society for Civil Engineering 5th International/11th Construction Specialty Conference, University of British Columbia, Vancouver, Canada. June 7-10. |
Peer Review Status | Unreviewed |
Scholarly Level | Faculty Other |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/2.5/ca/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 52660-Hajdu_M_et_al_ICSC15_340_One_Relation_To.pdf [ 958.83kB ]
- 52660-Hajdu_M_et_al_ICSC15_340_One_Relation_To_slides.pdf [ 965.24kB ]
- Metadata
- JSON: 52660-1.0076408.json
- JSON-LD: 52660-1.0076408-ld.json
- RDF/XML (Pretty): 52660-1.0076408-rdf.xml
- RDF/JSON: 52660-1.0076408-rdf.json
- Turtle: 52660-1.0076408-turtle.txt
- N-Triples: 52660-1.0076408-rdf-ntriples.txt
- Original Record: 52660-1.0076408-source.json
- Full Text
- 52660-1.0076408-fulltext.txt
- Citation
- 52660-1.0076408.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.52660.1-0076408/manifest