# A minmax regret approach to the critical path method with task interval times

下载积分：3000

内容提示： Decision SupportA minmax regret approach to the critical path method with task interval timesEduardo CondeDepartamento de Estadística e Investigación Operativa, Facultad de Matemáticas, Universidad de Sevilla, Campus Universitario de Reina Mercedes, Tarfia S/N, 41012 Sevilla, Spaina r t i c l e i n f oArticle history:Received 28 January 2008Accepted 16 June 2008Available online 28 June 2008Keywords:Robust optimizationProject managementa b s t r a c tThe execution of a given project, with a number of int...

文档格式：PDF|
浏览次数：1582|
上传日期：2015-12-28 07:17:34|
文档星级：

**********
Decision SupportA minmax regret approach to the critical path method with task interval timesEduardo CondeDepartamento de Estadística e Investigación Operativa, Facultad de Matemáticas, Universidad de Sevilla, Campus Universitario de Reina Mercedes, Tarfia S/N, 41012 Sevilla, Spaina r t i c l e i n f oArticle history:Received 28 January 2008Accepted 16 June 2008Available online 28 June 2008Keywords:Robust optimizationProject managementa b s t r a c tThe execution of a given project, with a number of interrelated tasks due to precedence constraints, rep-resents a challenge when one must to control the available resources and the compromised due dates. Inthis paper, we analyse this problem under uncertain individual task completing times, specifically, wewill assume that a given range, for the admissible values of each individual completing time, is available.Taking into account that the precedence relations between tasks must be preserved, each realization ofthe admissible execution times for the set of tasks will define a new scenario determining the endingtime for the project and the subset of critical tasks.The minmax regret criterion will be used in order to obtain a robust approximation to the critical set oftasks determining the overall execution time for the project.? 2008 Elsevier B.V. All rights reserved.1. IntroductionThe critical path method or CPM started to be used in projectmanagement at the end of the decade of the years 50 and thebeginning of the 1960s, [7]. The original method considered a setof precedence relations between the tasks of the project, that is,some jobs must be finished before other tasks can be started. Theserelations can be represented by means of a digraph in which thetasks are associated to arcs and the nodes represent the endingor the beginning of a subset of tasks.The CPM identifies a subset of critical tasks, associated to a pathover the digraph that joins two specific nodes (the start and theend of the project) whose overall completion time gives the mini-mal completion time for the project. Any delay in the execution ofone of the critical jobs will provoke a delay in the project comple-tion time, this is the sense in which the activities are considered ascritical.One of the basic hypotheses used in the CPM is to consider thatthe individual task completing times are deterministic and knownwith certainty. However, in practise, this hypothesis is sometimesunfulfilled which has given rise to the development of differentmethodologies as PERT (Program Evaluation and Review Technique,see e.g. [8]).The PERT assumes beta distributions for the individual taskcompleting times. Under this assumption and some other condi-tions, which are not exempt of criticism [1,10], one can establishthe statistical distribution of the overall completing time for theproject and take usual indicators as the mean of the ending timefor the project or its standard deviation.There exist other ways to approach the problem by using fuzzysets to model the uncertainties (see e.g. [4] and references therein)or simply by assuming that the completion time of a job can be anyof the values of a given set, like an interval, [2]. In this paper, weassume this last approach.Hence, the digraph representing the project has an interval ofadmissible completing times for the job associated to each arc.The choice of a given value from each interval determines a spe-cific scenario under which our project must be developed. Any ofthe largest (it is possible the existence of more than one) pathsfrom node 1, the beginning of the project, to the node n, theend of the project, determines a subset of critical tasks under thisscenario. In order to approach this changing subset of criticaltasks and its overall execution time we will use an optimal solu-tion for the minmax regret optimization problem correspond-ing to the determination of the largest path on the digraphbetween nodes 1 and n with interval arc lengths. An optimal solu-tion for this problem represents a robust subset of tasks whoseoverall execution time is an ? -approximation to the project end-ing time under each feasible scenario, where ? is so small aspossible.In the following section, the needed notation for the formula-tion of the robust optimization problem will be introduced. Afterthat, we will analyse a mixed-integer programming formulationwhich is equivalent to the original problem. We also give a heuris-tic solution in the last part of the paper that can help us when thenumber of tasks and/or precedence relations becomes large en-ough as to be handled by means of exact integer programmingtechniques.0377-2217/$ - see front matter ? 2008 Elsevier B.V. All rights reserved.doi:10.1016/j.ejor.2008.06.022E-mail address: educon@us.esEuropean Journal of Operational Research 197 (2009) 235–242Contents lists available at ScienceDirectEuropean Journal of Operational Researchjournal homepage: www.elsevier.com/locate/ejor
2. Notation and basic propertiesLet us consider a directed acyclic graph, or DAG, G ¼ ðN;AÞ,where N is the node set, jNj ¼ n, and A is the arc set, jAj ¼ m.The DAG G represents the whole of the projet; its nodes are iden-tified with the beginning or the ending of a subset of tasks, and itsarcs represent the individual activities or tasks of the project (AOA,activity on arc, see e.g. [6]).For all ði;jÞ 2 A let w sij 2 ½w?ij ;wþij ? be the execution time of theactivity associated to the arc ði;jÞ under the scenario s. It is as-sumed unknown the real scenario that will take place, that is,one has uncertain execution times for the activities. We will as-sume that w ?ijP 0, for each ði;jÞ 2 A. The set of admissible scenar-ios, given by the cartesian product of the set of intervals ½w ?ij ;wþij ?,will be denoted by S.The nodes can be labeled so that, for each arc ði;jÞ 2 A, one hasthat i < j (topological order), this is always possible taking into ac-count that G is a DAG.We denote by P the set of directed path in G with the node 1 asits beginning and the node n as its ending. In this context, given anarbitrary scenario s 2 S, the length of the largest path in P, accord-ing to the set of individual arc lengths w sij , represents the minimumrequired time for the execution of the whole of the project G. Thisminimum can be obtained in Oðn þ mÞ time (see e.g. [5]) by solvingthe optimization problemmaxx2PXði;jÞ2Aw sij x ij ;ð1Þwhere the path x has been identified by the matrix with binary en-tries x ij (x ij ¼ 1, if the arc ði;jÞ is used in the path and x ij ¼ 0,otherwise).However, when one has uncertain execution times for the activ-ities, there exists, at least, one critical path under each admissiblescenario, but an estimation for the best ending execution time ofthe project and an approach to the set of critical activities that mustbe closely controlled, still is necessary in order to manage re-sources and due dates. In order to approach the changing subsetof critical tasks we propose in this paper to minimize the maxi-mum regret, over the whole of the scenario set, obtained for a givenpath by comparing it with the critical path under each scenario.This approach, will give us, in particular, an ? -approximation tothe minimum ending execution time with ? as small as possible.In order to have a mathematical formulation for the optimiza-tion problem we define the maximum regret for a given path asfollows:Definition 2.1. Given a path x 2 P, the maximum regret for xcorresponding to the scenario set S is the valueRðxÞ ¼ maxs2Sfmaxy2PRðy;w s Þ ? Rðx;w s Þg;where Rðx;w s Þ ¼Pði;jÞ2A wsij x ij .Hence, the optimization problem that we must solve can bewritten asR ? ¼ minx2PRðxÞ ¼ minx2Pmaxs2Smaxy2PRðy;w s Þ ? Rðx;w s Þ? ?: ðPÞThere exists a negative result about the complexity of this optimiza-tion problem.Theorem 2.1 (Zielin´ski [11]). Problem ðPÞ is NP-hard.In [11] the author shows that the given complexity for the prob-lem ðPÞ remains NP-hard even for planar DAG’s with node de-grees lower or equal to 3 and integer values for the extremes w ?ij(Theorem 2 of [11]).In the next section, we analyse a mixed-integer programmingformulation for ðPÞ proposed by Karasan et al. [9]. In this formula-tion, we use the following notation:? R s ¼ max x2P Rðx;w s Þ,? R s ðxÞ ¼ R s ? Rðx;w s Þ,? RðxÞ ¼ max s2S R s ðxÞ.We also need to introduce a specific notation for the worst sce-nario that may happen once a given candidate, to be a critical path,has been chosen.Definition 2.2. For an arbitrary path x 2 P we define the scenariosðxÞ 2 S as follows:w sðxÞij¼w ?ijif ði;jÞ 2 x;w þijotherwise:(The scenario sðxÞ will play an important role in the mixed-inte-ger formulation of the minmax regret problem, in fact, under thatscenario the maximum regret for x is reached.Proposition 2.1 (Karasan et al. [9]). For every x 2 P it is true thatRðxÞ ¼ R sðxÞ ðxÞ ¼ R sðxÞ ? Rðx;w sðxÞ Þ:3. The MIP formulationIn this section, the mixed-integer programming (or MIP) formula-tion proposed by Karasan et al. [9] is rewritten in terms of the nota-tion introduced in the above section. First, the value R sðxÞ can beobtained as the optimal objective value of a flow problem of a unitof product from the node 1 to the node n in the DAG G, with arclengths determined by the scenario sðxÞ.R sðxÞ ¼ maxXði;jÞ2A½w þij? ðw þij? w ?ij Þx ij ?y ijstXj:ði;jÞ2Ay ij ?Xk:ðk;iÞ2Ay ki ¼1 if i ¼ 1;?1 if i ¼ n;0 if i–1;n;8><>:y ij P 0; ði;jÞ 2 A:ð2ÞObservation 3.1. Let us observe that it is not necessary toconstraint the variables y ij to be binary (y ij 2 f0;1g) since theabove problem has unimodular constraints, that is, every extremepoint for the feasible set has integer (binary) components. Hence,once that the vector x has been fixed, the resulting linearprogramming problem has, at least, an optimal solution withbinary components y ij 2 f0;1g.Property 3.1. R sðxÞ is a convex function.Proof. Taking into account thatXði;jÞ2A½w þij? ðw þij? w ?ij Þðkx ij þ ð1 ? kÞx0ij Þ?y ij¼ kXði;jÞ2A½w þij? ðw þij? w ?ij Þx ij ?y ijþ ð1 ? kÞXði;jÞ2A½w þij? ðw þij? w ?ij Þx0ij ?y ijfor all k 2 ½0;1? and that R sðkxþð1?kÞx0 Þis given by the maximum of theabove expression, one has the result. h236 E. Conde/European Journal of Operational Research 197 (2009) 235–242
On the other hand, (2) identifies the function R sðxÞ as the optimalobjective value of a feasible linear optimization problem which isbounded by above, hence one can write this optimal value in termsof its dual optimization problem as follows:R sðxÞ ¼ min a 1 ? a nst a i ? a j P w þij? ðw þij? w ?ij Þx ij ;8 ði;jÞ 2 A:ð3ÞOne has that, if ð a 1 ;...; a n Þ is a feasible solution of (3) then also thesolution ð a 1 þ k;...; a n þ kÞ will be feasible for (3) and it reaches thesame objective value whatever the value of k is. Hence, we can addthe new constraint a n ¼ 0 to the above formulation in order to ob-tain the equivalent oneR sðxÞ ¼ min a 1st a i ? a j P w þij? ðw þij? w ?ij Þx ij ;8 ði;jÞ 2 A;a n ¼ 0:ð4ÞObservation 3.2. In the formulation (4) the variables a i ’s of anyfeasible solution are nonnegative values. In fact, taking intoaccount that the constraint a n ¼ 0 has been added and thatx ij 2 ½0;1?, one has that a i P a j P 0 for all ði;jÞ 2 A.Using the Proposition 2.1, and the formulation (2), we can writethe problem ðPÞ as the equivalent formulationR ? ¼ min R sðxÞ ?Xði;jÞ2Aw ?ij x ijstXj:ði;jÞ2Ax ij ?Xk:ðk;iÞ2Ax ki ¼1 if i ¼ 1;?1 if i ¼ n;0 if i–1;n;8><>:x ij 2 f0;1g; ði;jÞ 2 A;where we have used thatRðx;w sðxÞ Þ ¼Xði;jÞ2Aw ?ij x ij ;according to the Definition 2.2.Now, it is not possible to delete the binary constraints on thevariables of the problem since that, according to the Proposition3.1, the objective function of the above problem is a general piece-wise-convex function, hence, it can reach its minimum out of theextreme point set of the feasible polyhedron.On the other hand, from the expression (4) we obtain a mixed-integer linear formulation of the problem ðPÞ given byR ? ¼ min a 1 ?Xði;jÞ2Aw ?ij x ijstXj:ði;jÞ2Ax ij ?Xk:ðk;iÞ2Ax ki ¼1 if i ¼ 1;?1 if i ¼ n;0 if i–1;n;8><>:a i ? a j þ ðw þij? w ?ij Þx ij P wþij ; ði;jÞ 2 A;x ij 2 f0;1g; ði;jÞ 2 A;a n ¼ 0:ðMIPÞIn order to understand the meaning of the MIP-variables in thecontext of the execution of a given project we will now consider anumerical example.Let us suppose that we have to execute nine individual tasks,which are interrelated by a set of precedence relationships as itis shown in the Fig. 1 (the arcs represent the set of individual tasks,AOA representation).In this network, the node 1 represents the beginning of theproject and the node 5, its ending. The rest of the nodes can beidentified with events such that the beginning or the ending ofone or more activities. The interval associated to each arc is therange for the time execution of the corresponding task.Following the formulation ðMIPÞ, the problem of determiningthe critical task path under the minmax regret approach can bewritten asmin a 1 ? 9x 12 ? 3x 13 ? 8x 14 ? 6x 15 ? 4x 23 ? 10x 24? x 25 ? 10x 34 ? 2x 45st x 12 þ x 13 þ x 14 þ x 15 ¼ 1;x 23 þ x 24 þ x 25 ? x 12 ¼ 0;x 34 ? x 13 ? x 23 ¼ 0;x 45 ? x 14 ? x 24 ? x 34 ¼ 0;? x 15 ? x 25 ? x 45 ¼ ?1;a 1 ? a 2 þ x 12 P 10;a 1 ? a 3 þ 12x 13 P 15;a 1 ? a 4 þ x 14 P 9;a 1 ? a 5 þ 3x 15 P 9;a 2 ? a 3 þ x 23 P 5;a 2 ? a 4 þ 5x 24 P 15;a 2 ? a 5 þ x 25 P 2;a 3 ? a 4 þ x 34 P 11;a 4 ? a 5 þ x 45 P 3;x ij 2 f0;1g;a 5 ¼ 0:We obtain the optimal solution given by x ?12 ¼ x?23 ¼ x?34 ¼x ?45 ¼ 1 and x?ij ¼ 0, for the rest of variables. Hence, the critical activ-ities are fð1;2Þ;ð2;3Þ;ð3;4Þ;ð4;5Þg. On the other hand, a ? ¼ ð27;18;12;2;0Þ which establishes as 2 time units the optimal objectivevalue (maximum regret) corresponding to x ? .Thinking that, the critical activity set must be under our control,in order to not to delay the project and hence, we may expect thatthey are executed in their shortest completion times, the worstscenario that may occur is that the remaining tasks would be com-pleted in their worst individual execution times, in other words,the scenario sðx ? Þ has occurred. Under the scenario sðx ? Þ, the execu-tion time of the activity ði;jÞ 2 fð1;2Þ;ð2;3Þ;ð3;4Þ;ð4;5Þg is w ?ijwhile the rest of the activities are executed in w þijtime units. In thissituation the project will be completed in a ?1 ¼ 27 time units, sucha value is reached by the sequence of activities fð1;3Þ;ð3;4Þ;ð4;5Þgwhere w sðx? Þ13¼ w þ13 ¼ 15 is the execution time of the only activitythat escaped to our control (centered in the critical activity set).This supposes a regret of 2 time units. Under any other time sce-nario the overall completion time for the project will be reachedby the critical sequence of activities given by x ? or will differfrom its corresponding execution time in, at most, 2 time units.Fig. 1. Activity network for the numerical example.E. Conde/European Journal of Operational Research 197 (2009) 235–242 237
Moreover, any other critical activity path that we control willdetermine a set of uncontrolled activities that will provoke, underthe worst time scenario, a delay respect to the completion time ofthat critical activity set of at least 2 time units.Hence, the overall completion time for the project shown in theFig. 1 is given by the completion time of the critical pathfð1;2Þ;ð2;3Þ;ð3;4Þ;ð4;5Þg plus, at most, an extra amount of 2 timeunits under any time scenario. For this reason, which is verified in ageneral context, the critical path determined by the formulationðMIPÞ is called a robust solution.Finally, if we reduce the degree of the project uncertainty wecan reduce the maximum regret to zero. In this case, the robustcritical path obtained by solving the ðMIPÞ formulation, determinesby itself the overall completion time of the project. For instance, ifwe reduce the upper bounds of the individual execution times ofthe activities ð1;3Þ and ð2;4Þ in 2 time units, that is, the newbounds become w 0þ13 ¼ w0þ24 ¼ 13, the maximum regret for the newminmax problem will be zero, in fact, the length of the pathfð1;2Þ;ð2;3Þ;ð3;4Þ;ð4;5Þg will determine the ending completiontime, whatever the time scenario is.4. Properties of the MIP formulationIn this section, we will analyse some properties that allow us torewrite the ðMIPÞ formulation as the minimization of a non-linearfunction over a set of constraints representing the paths of P.We introduce the following notation for each i 2 N n fng:a þi¼ maxf a þjþ w þij: ði;jÞ 2 Ag;a ?i¼ minj: ði;jÞ2Amaxf a ?jþ w ?ij ; a?kþ w þik : ði;kÞ 2 A;k–jg:For the sake of completeness we define a ?n¼ 0, then we have thefollowing:Property 4.1. At least one of the optimal solutions ð a ;xÞ of the ðMIPÞformulation verifies that a i 2 ½ a ?i; a þi? for all i 2 N n fng.Proof. The property is satisfied for i ¼ n, let us assume it is true forthe set of indexes j ¼ i þ 1;...;n then, from the constraint set ofðMIPÞ, given a feasible solution ð a ;xÞ, one hasa i P a j þ w þij? ðw þij? w ?ij Þx ij ;8 ði;jÞ 2 A:If the node i is used in the path determined by x thena i P maxf a j þ w ?ij ; a k þ wþik ;k : ði;kÞ 2 A; k–jg;for some j such that ði;jÞ 2 A. On the other hand, if the node i is notused in that path, then the above inequality remains true given that,in this casea i P maxf a j þ w þij ; j : ði;jÞ 2 Ag:ð5ÞHencea i P minj: ði;jÞ2Amaxf a j þ w ?ij ; a k þ wþik ; k : ði;kÞ 2 A; k–jg:Taking into account that G is an acyclic network, following the topo-logical order of the node set N, one has that ði;qÞ 2 A implies thati < q then, we can use the induction hypothesis in order to havea i P a ?i .Hence, if the inequality (5) is verified then, also will be verifiedthe constraint blocka i ? a j þ ðw þij? w ?ij Þx ij P wþij ; ði;jÞ 2 Að6Þof the ðMIPÞ formulation, independently from the value of x ij 2 ½0;1?.Moreover, given a feasible solution ð a ;xÞ in which i 0 is thelargest index for whicha i 0 > maxf a j þ w þi 0 j ; j : ði 0 ;jÞ 2 Ag;if the value of a i 0 is diminished until the value of the right hand sideof this inequality is reached, the new solution remains feasible,since the constraint block (6) remains verified for i ¼ i 0 ; for the in-dexes i > i 0 the variable a i 0 does not appear and for i < i 0 the corre-sponding constraints will be relaxed since the value of a i 0 has beendiminished. Moreover, the objective value for this new solutiondoes not increase, then one can assume the following for the opti-mal solutiona i 6 maxf a j þ w þij ; j : ði;jÞ 2 Agð7Þfor every i.Finally, taking into account that a n ¼ 0 ¼ a þn , using (7) one hasa n?1 6 a þn?1and by recurrence, given the topological order of thenode set, it will be true that a i 6 a þifor each i 2 N. hCorollary 4.1. Every feasible solution ðb;xÞ of the problem ðMIPÞ hasan objective value greater than, or equal to, ð a ðxÞ;xÞ (ðb;xÞ is domi-nated by ð a ðxÞ;xÞ) witha i ðxÞ ¼ maxf a j ðxÞ þ w þij? ðw þij? w ?ij Þx ij ; j : ði;jÞ 2 Ag;where a n ðxÞ ¼ 0.Proof. Follows from the proof of the Property 4.1. hThis corollary allows us to rewrite the formulation of the prob-lem ðMIPÞ using the following:Corollary 4.2. Every feasible solution x of ðMIPÞ verifies R sðxÞ ¼ a 1 ðxÞ.Proof. The proof is a direct consequence of the fact that ð a ðxÞ;xÞ isa feasible solution for the formulation ðMIPÞ and the Corollary 4.1is also verified. hThe problem ðPÞ can be equivalently formulated asR ? ¼ min a 1 ðxÞ ?Xði;jÞ2Aw ?ij x ijstXj:ði;jÞ2Ax ij ?Xk:ðk;iÞ2Ax ki ¼1 if i ¼ 1;?1 if i ¼ n;0 if i–1;n;8><>:x ij 2 f0;1g; ði;jÞ 2 A:ðMIHÞThe feasible solutions of the formulation (MIH) are the set of pathsx 2 P, each one of these paths is evaluated by means of the twocomponents of the cost function, a 1 ðxÞ and ? P ði;jÞ2A w ?ij x ij . Obvi-ously, what makes difficult to solve the problem (MIH) is thata 1 ðxÞ appears in its objective function. This suggests that this’hard’component of the objective function must receive a different treat-ment from the component costPði;jÞ2A w?ij x ij . For this reason, in thenext section the problem (MIH) will be analysed from a biobjectiveviewpoint in which the following property will be used.Property 4.2. The optimal solutions of the problem ðBPÞ are efficientor Pareto optimal solutions of the biobjective problemvector min a 1 ðxÞ;?Xði;jÞ2Aw ?ij x ij !st x 2 P:ðBPÞ5. An algorithm from the biobjective formulationAs we will see in what follows, the biobjective formulation ðBPÞallows us to propose feasible solutions that approach the optimalsolution of ðMIPÞ with an upper bound on its error specified a238 E. Conde/European Journal of Operational Research 197 (2009) 235–242
priori. In fact, the iteration of the procedure that finds these ap-proaches is, by itself, a resolution algorithm for the problem ðMIPÞ.Let x a 2 P be a path of G that minimizes a 1 ðxÞ and let x r 2 P apath maximizingPði;jÞ2A w?ij x ij . Both paths are weakly efficient solu-tions of the biobjective problem ðBPÞ. In particular, x r defines theminimal execution time of the project, in the deterministic casewhere all the uncertainty intervals are degenerated.Letd 0 ¼ min a 1 ðx r Þ ? a ?1 ;Xði;jÞ2Aw ?ij x r ij ?Xði;jÞ2Aw ?ij x a ij( )andx 0 ¼ argmin fRðx a Þ;Rðx r Þg:It is verified the following:Property 5.1. The path x 0 2 P is a d 0 -approximation of the problemðPÞ.Proof. For every x 2 P it is verifieda 1 ðxÞ ?Xði;jÞ2Aw ?ij x ij P a 1 ðxÞ ?Xði;jÞ2Aw ?ij x r ij¼ a 1 ðx r Þ ?Xði;jÞ2Aw ?ij x r ij þ a 1 ðxÞ ? a 1 ðx r ÞP a 1 ðx r Þ ?Xði;jÞ2Aw ?ij x r ij þ a?1? a 1 ðx r ÞP a 1 ðx 0 Þ ?Xði;jÞ2Aw ?ij x0ij þ a?1? a 1 ðx r Þ:On the other handa 1 ðxÞ ?Xði;jÞ2Aw ?ij x ij P a 1 ðx a Þ ?Xði;jÞ2Aw ?ij x ij¼ a 1 ðx a Þ ?Xði;jÞ2Aw ?ij x a ij þXði;jÞ2Aw ?ij x a ij ?Xði;jÞ2Aw ?ij x ijP a 1 ðx 0 Þ ?Xði;jÞ2Aw ?ij x0ij þXði;jÞ2Aw ?ij x a ij ?Xði;jÞ2Aw ?ij x r ij :Hence, one has thatRðxÞ P Rðx 0 Þ ? d 0 : ?Observation 5.1. Let us observe that if we havePði;jÞ2A w?ij x a ij ¼Pði;jÞ2A w?ij x r ijthen d 0 ¼ 0 and hence x a is an optimal solution ofthe problem (MIH). In this situation, the path x a is an efficient solu-tion for the biobjective problem ðBPÞ. Moreover, since it is an opti-mum for both objective functions it is called an ideal point (see e.g.[3]) for the problem ðBPÞ.If d 0 is a positive value, the d 0 -approximation can be improvedby means of the optimal solution of an auxiliary optimization prob-lem. LetK ¼Xði;jÞ2Aw ?ij x a ij ;we will solve the optimization problemmin a 1 ðxÞst x 2 PXði;jÞ2Aw ?ij x ij > K:ðAPðKÞÞIn order to solve the problem APðKÞ a Dynamic Programming proce-dure can be used. Once this problem has been solved, a better (moreaccurate) approach can be obtained for the problem ðPÞ.Let x K be an optimal solution of the problem APðKÞ and take x 1given by the solution reaching the minimal objective valueamongst the set fx a ;x r ;x K g, that isx 1 ¼ argmin fRðx a Þ;Rðx r Þ;Rðx K Þg:Finally, letd 1 ¼ min a 1 ðx r Þ ? a ?1 ;Xði;jÞ2Aw ?ij x r ij ?Xði;jÞ2Aw ?ij xKij( ):Let us observe that, since x K is a feasible solution of the problemAPðKÞ, one has thatXði;jÞ2Aw ?ij xKij> K ¼Xði;jÞ2Aw ?ij x a ij ;which implies that d 1 6 d 0 .The following result is verified:Property 5.2. The path x 1 2 P is a d 1 -approximation to the optimumof the problem ðPÞ.Proof. First of all, if x 2 P verifiesPði;jÞ2A w?ij x ij 6Pði;jÞ2A w?ij x a ij then,one hasRðxÞ ¼ a 1 ðxÞ ?Xði;jÞ2Aw ?ij x ij P a 1 ðx a Þ ?Xði;jÞ2Aw ?ij x a ij ¼ Rðx a Þ P Rðx1 Þ:Otherwise,Pði;jÞ2A w?ij x ij > K, hence a 1 ðxÞ P a 1 ðxK Þ, which give usa 1 ðxÞ ?Xði;jÞ2Aw ?ij x ij P a 1 ðxK Þ ?Xði;jÞ2Aw ?ij xKij þXði;jÞ2Aw ?ij xKij ?Xði;jÞ2Aw ?ij x ijP Rðx K Þ þXði;jÞ2Aw ?ij xKij ?Xði;jÞ2Aw ?ij x r ijP Rðx 1 Þ þXði;jÞ2Aw ?ij xKij ?Xði;jÞ2Aw ?ij x r ij :In conclusion, x 1 is a d 1 -approximation. hThe above process can be reiterated until a given upper boundon the error can be guaranteed. In this sense, after the solutionx K has been obtained, we takeK 0 ¼Xði;jÞ2Aw ?ij xKij ;then K 0 > K.Given x 2 P, ifPði;jÞ2A w?ij x ij 6 K, following the proof of the Prop-erty 5.2, this solution is dominated by x a . On the other hand, ifK <Xði;jÞ2Aw ?ij x ij 6 K0¼Xði;jÞ2Aw ?ij xKij ;in particular, x is a feasible solution of the problem APðKÞ which im-plies a 1 ðxÞ P a 1 ðx K Þ. HenceRðxÞ ¼ a 1 ðxÞ ?Xði;jÞ2Aw ?ij x ij P a 1 ðxK Þ ?Xði;jÞ2Aw ?ij xKij¼ Rðx K Þ:Finally, ifK 0 \Xði;jÞ2Aw ?ij x ij ;then, by the same operations that those used in the proof of theProperty 5.2, we have that, given x K0 , an arbitrary optimal solutionof the problem APðK 0 Þ the solution x 2 defined by means ofx 2 ¼ argmin fRðx a Þ;Rðx r Þ;Rðx K Þ;Rðx K0 Þgis a d 2 -approximation, whered 2 ¼ min a 1 ðx r Þ ? a ?1 ;Xði;jÞ2Aw ?ij x r ij ?Xði;jÞ2Aw ?ij xK 0ij( ):E. Conde/European Journal of Operational Research 197 (2009) 235–242 239
This allows us to propose an iterative algorithm in order to solve theproblem ðPÞ.Algorithm 5.10: Input: D ¼ ðN;AÞ, w ?ijfor each ði;jÞ 2 A.1: Initialization: Find x a and x r . Letd 0 ¼ min a 1 ðx r Þ ? a ?1 ;Xði;jÞ2Aw ?ij x r ij ?Xði;jÞ2Aw ?ij x a ij( )andx 0 ¼ argminfRðx a Þ;Rðx r Þg:If d 0 ¼ 0, x 0 is an optimal solution of ðPÞ, otherwise, goto the Iteration 1.2: Iteration n ¼ 1;2;...: TakeK 0 ¼Xði;jÞ2Aw ?ij xKij ;(if n ¼ 1, x K ¼ x a ). Let x K0be an optimal solution of theproblem APðK 0 Þ. Takex n ¼ argmin fRðx n?1 Þ;Rðx K0 Þgandd n ¼ min a 1 ðx r Þ ? a ?1 ;Xði;jÞ2Aw ?ij x r ij ?Xði;jÞ2Aw ?ij xK 0ij( ):If d n ¼ 0, x n is an optimal solution of the problem ðPÞ,otherwise, take K ¼ K 0 and go to the Iteration n þ 1.Let us observe that, in each iteration, the valueXði;jÞ2Aw ?ij x r ij ?Xði;jÞ2Aw ?ij xK 0ij ;decrease strictly respect toXði;jÞ2Aw ?ij x r ij ?Xði;jÞ2Aw ?ij xKij ;at least in a fixed quantity d > 0 because the set of coefficients w ?ijisfinite. Hence, after a finite number of iterations, the solution ob-tained by means of this algorithm is an optimum of the problemðPÞ, that is, we have the following:Theorem 5.1. The Algorithm 5.1 ends after a finite number ofiterations with an optimum of the problem ðPÞ.5.1. Initialization of the algorithmIn order to find x a the problem min x2P a 1 ðxÞ must be solved. Todo that, we can use the following recurrence relationsf i ¼ minj:ði;jÞ2Amax w ?ijþ f j ; maxk:ði;kÞ2Anði;jÞ fwþik þ a k ðxj Þg? ?f n ¼ 0;ð9Þwhere x j represents a path minimizing a j ðxÞ amongst those pathsjoining the node j to the node n. We assume that x n ¼ ;. The optimalpaths x j with j ¼ i þ 1;...;n ? 1, have been previously obtainedwhen their corresponding minimal costs, f j , were calculated, start-ing from j ¼ n ? 1 and applying backward recurrence until the in-dex i is reached.5.2. The iteration step by means of dynamic programmingIn order to solve the auxiliary problem APðKÞ we will use thefollowing recurrence relationsf i ðK i Þ ¼ minj:ði;jÞ2Amax w ?ijþ f j ðK i ? w ?ij Þ;maxk:ði;kÞ2Anði;jÞ fwþik þ a k ðxj ðK i? w ?ij ÞÞg? ?;f n ðK n Þ ¼þ1 if K n P 0;0 if K n < 0:?ð10ÞIn the above equations x j ðK i ? w ?ij Þ represents an optimal path fromthe node j to the node n defining the value f j ðK i ? w ?ij Þ. Hence, whenwe are determining the value of the function f j ðK i ? w ?ij Þ the corre-sponding optimal path must be stored in order to be used for thesubsequent calculations.In order to solve the problem APðKÞ it is necessary to find thevaluef 1 ðKÞthrough the above recurrence relations.6. A heuristic algorithmThe calculation of successive approximations to the optimum ofthe problem ðPÞ, according to the recurrence relations, explained inthe above section, is based in the application of Dynamic Program-ming techniques in (9) and (10) in order to obtain de solutions x aand x K . However, if the project involves a large number of activitiesthis approach is not viable since it implies solving the Eq. (10) foran exponential number of states or arguments of the functionals. Inthese situations one can apply a heuristic algorithm derived bysimplifying the recurrence relations (10). It is stated below.Algorithm 6.10: Input: D ¼ ðN;AÞ, w ?ijfor each ði;jÞ 2 A.1: Initialization: Make c n ¼ b n ¼ 0.2: Calculation of the parameters b and c : For eachi ¼ n ? 1 : ?1 : 1:2:1: For each j 2 N such that ði;jÞ 2 A, calculateD ij ¼ maxfw ?ijþ c j ;w þik þ c k : k : ði;kÞ 2 A; k–jg:2:2: Let jðiÞ be the smallest index for which it isreached the minimum,D ijðiÞ ? ðw ?ijðiÞ þ b jðiÞ Þ ¼ minf D ij ? ðw?ijþ b j Þ : j : ði;jÞ 2 Ag:2:3 Let c i ¼ D ijðiÞ and b i ¼ w ?ijðiÞ þ b jðiÞ .3: Finding the path of critical tasks: Take i ¼ 1 andexecute the following operations while i–n:3:1: Let x HijðiÞ ¼ 1.3:2: Let i ¼ jðiÞ.4: Finding the vector a (x): Let a n ðxÞ ¼ 0 and fori ¼ n ? 1 : ?1 : 1 takea i ðxÞ ¼ maxf½w þij? ðw þij? w ?ij Þx ij ? þ a j ðxÞ : j : ði;jÞ 2 Ag:Let R H ¼ a 1 ðxÞ ? b 1 .Let us observe that b 1 is the addition of the lower bounds w ?ij ,whose arcs ði;jÞ belong to the path of P defined by the solutionx H proposed by the Algorithm 6.1. Hence, in virtue of the Corollary4.2, the value R H ¼ a 1 ðx ? Þ ? b 1 equals the maximum regret of x Hand it is, in fact, a upper bound of the optimal objective value ofthe problem ðPÞ. From now on, we will show some indicators ofthe quality of the approximated solution, x H , and some statisticsof the CPU times spent in solving the set of random problems gen-erated in a numerical experiment.The size of the set of nodes, n, will be in the set f50;100;250;500g. Given an ordered pair of nodes, i;j (i < j) the240 E. Conde/European Journal of Operational Research 197 (2009) 235–242
corresponding arc ði;jÞ, is generated with probability p ¼ 0 0 25,p ¼ 0 0 50 and p ¼ 0 0 75 (see the Tables 1–3).The necessary interval of uncertainty, ½w ?ij ;wþij ?, for each gener-ated arc, is randomly obtained according to a beforehand specifiedlevel of uncertainty d. Specifically, for each arc ði;jÞ the lowerbound of the interval of uncertainty, w ?ij , is randomly generatedfrom a uniform distribution on the interval ½0;200?. Afterwards,the upper bound for this interval is generated according to theequationw þij¼ w ?ij ð1 þ UdÞ;where U follows an independent uniform distribution on ½0;1?.Hence, the factor d represents, in some way, the admissible levelof uncertainty in the cost coefficients of the problem.The results listed in the Tables 1–3 were obtained for threedegrees of uncertainty d ¼ 10%;25%; and 50% on a personalcomputer with Intel ? Pentium? M processor, 1.60 GHz with0 0 99 GB RAM. The code of the heuristic algorithm (Algorithm 6.1)was written as a Matlab ? v.6.5 program and the integer programðMIPÞ was solved with the ILOG CPLEX ? 8.1 MIP solver. For eachcombination of d and n, fifty instances of the problem ðPÞ weregenerated according to the process described before. The gapcolumn contains the average (as a percentage) and the standarddeviation of the sample of values fðR Hi? R ?i Þ= R?: i ¼ 1;...;50gwhere R Hiand R ?iare, respectively, the heuristic and the exactobjective value for each of the fifty solved instances and R ? is theaverage of the optimal values R ?i .Analysing the Tables 1–3 one can see how the CPU time spentby the heuristic algorithm (H-CPU-T) as well as the CPU time spentby the exact MIP solver (E-CPU-T) increase with the number ofnodes and with the density of the project networks (controlledby the parameter p). This is the type of behavior one may expectbut, perhaps, what is more surprising is the fast increasing in com-putational times when the uncertainty degree, d, grows.The results shown in the tables can be summarized in the Fig. 2where the continuous line represents the average of the proportionof time spent by the heuristic algorithm in relation to the timespent by the exact algorithm. The broken line represents the gapbetween the approximated solution and the optimal one as a per-centage of the optimal value. As one can see, in the set of generatedproblem, the CPU time spent by the heuristic is around the 4% ofthe CPU time spent by the solver in or...