Hybrid algorithm for scheduling and risk assessment of projects

Copyright Q IF AC Analysis and Design of Hybrid Systems, Brittany, France, 2003 IFAC c 0 (> Publications www.clsevicr.comIlocatclilac HYBRID ALGORITHM FOR SCHEDULING AND RISK ASSESSMENT OF PROJECTS. Ascension Zafra-Cabeza, Miguel A. Ridao, Eduardo F. Camacho Departamento de Ingenieria de Sistemas y Automatica, Universidad de Sevilla. Camino de ios Descubrimientos sin. 41092, Seville, SPAIN Tei. +34954487360 Fax +34954487340 {asun, ridao, eduardo/@cartu;a.us.es Abstract: This work presents a technique for optimal scheduling of projects in terms of time and cost, taking into account risk assessment. Tasks are characterized by p-timed Petri nets, where places have assigned an execution time. The proposed technique minimizes the time execution and the cost of the whole project taking into account the Petri nets describing the tasks and the project risk assessment plan. The risk mitigation is carried on through actions where variables that model them may be discrete or continuous. Copyright t© 2003 IFAC Keywords: Risk, Integer Programming, Multiple-criterion optimization, Petri-nets, Project Management. I. INTRODUCTION At the beginning of a project, the project team has to schedule the time and cost of the tasks that comprise the project. At that moment, the available information uses to be linked to uncertainties and the data are in a very low detail. Companies give great importance to this point due to its importance on the viability of the project. Previous to the starting of the project and after the definition of the tasks, a forecast about the possible risks that could appear during the progress of the project is, nowadays, a very common and satisfactory practice in project management. Poorly written specifications can result in wrong functionality and cause delays during implementation and testing. In the same way, risks can be caused by market payoffs, project budgets, product performance, market * This research was partially supported by the MCYT under contract DPI200 1-2380-C02-0 I. 147 requirements or project schedules. The assumption that risks are inherent during the project life cycle (PLC) has given rise to a new range in project management. Thus, Risk Management is considered as an integrated task into the PLC (Jaafari, 2001). Several studies have been developed as attempt to carry out formalization of models and algorithms to manage risks in the project framework (Grabowski et aI., 2000; Chapman and Ward, 2000; Crouhy et aI., 2000). Hence, risk management can be summarized as the identification, ranking and priorization of risks, resolution of those deemed significant, and monitoring risks through their applicable life (Hyatt and Rosenberg, 1997). At the beginning, risk assessment and risk mitigation basically were applied to natural disasters (Schuster et aI., 1986; Litan et aI., 1992). In the last years, the application has been extended to project management and financial policies fields, where risk mitigation is raising an increasing interest (Jaafari, 2001 ;Doherty, I 997;Kleindorfer, 1999b). The lack of interest in risk mitigation and therefore, the lack of investing in loss prevention measures, is motivated by several factors: the underestimation of risk probability, long term horizons to retrieve investments, aversion to extra costs or in public disasters situations, expectation of disaster assistance. It has been shown that accomplishments such as cost reductions, improvement in product's quality and a better understanding of the project can be obtained by using these techniques. In this work, risks are introduced according to the risk-approach developed in previous works related to the project PRIMA I (Alquier et aI., 2000; ZafraCabeza et aI., 2001; Zafra-Cabeza et aI., 2002a; Zafra-Cabeza et aI., 2002b; Zafra-Cabeza et aI., 2003). Under this structure, information about risks just as impacts or mitigation actions, are considered. Petri Nets is a formal and graphical technique, which is appropriate for modelling systems in a easy way, where concurrency and synchronisation have a relevant place (Silva, 1985; David and Alia, 1994). Besides, they facilitate the practice approach. A special kind of Petri net, called p-timed Petri net, is used in this work in order to support the modelling of the ta sks of the project. Here, places have assigned an execution time (Gu and Bahn, 1999; L10yd and Salleh, 1991). This work aims at optimal scheduling, in time and cost, of project tasks. The proposed technique minimizes, starting from the Petri net and the adopted risk-approach, the execution time and the cost of the whole project. Hence, thi s study becomes a multiobjective problem, where user may select the weights of the criteria. The risk mitigation is carried on through actions where variables that model them may be discrete or continuous. Therefore, a mixed optimization problem is stated. The paper is organized as follows: section 2 presents how the tasks are modelled under Petri nets. The framework of risks and its connection to the tasks is described in section 3. The optimization problem is defined in section 4. Section 5 illustrates an original example and the results obtained. Some concluding remarks are made in section 6. 2. PROJECT LIFE AND TIMED PETRI NETS. Petri l\ets has been under development since the beginning of the 60'ies, where Carl Adam Petri defined the language. It was the first time a general theory for discretc parallel systems was formulated. The language is a generalisation of automata theory I pRIMA (IST-1999-IOI93) is a research and tt:chnological development project partially supportcd by th e Information Society Technologies (1ST) Programme of the European Lnion 's Fifth Framew or k progra mme . ( http://w\vw. esi2.us.es ipri mal). 148 such that the concept of concurrently occurring events can be expressed. A timed place Petri net, or p-timed Petri net (Gu and Bahn, 1999) has been adopted in this study to support the modelling of the PLC . Time constants are associated with places; places are the steps or tasks that the project comprises. A token deposited in a place becomes available after that period of time (time execution of the task). A p-timed Petri net is formally a bipartite directed graph represented by a six-tupla: TPN == (P .T,f .O, mo,y) (I) where P={PI, P2, ···, Pr} (r;?:O) is a finite set of places; T= {/J, 1 2, ... , I,} (s;?:O) is a finite set of transitions (PuhO, Pn T =0 ); I: (PxT) -+N an input function; 0: (PxT) -+N an output function (N is a set of nonnegative integers); m o: P -+N the initial marking; y: P -+R" is the plaee time function (R < is a set of non-negative real numbers). Figure I illustrates a p-timed Petri net, where there are eight places and six transitions. The places represent project tasks. The time associated to each place is the task completion time. The p-timed Petri nets that have been considered, satisfy the constraints of being binary, live, without conflicts and without cycles. 3. RISK MODELING. As it was mentioned before, a risk-based approach is used in this paper. Risks are linked to the different tasks of the project. 50 P 3' I .. .. 90 ( . ) P 1 'T' 15 A-I 1 P2 , .. . / • ~, .-- -- 12 Y ,_ Y. . ) P 32 3( P4 .. t2' _ -.Y _ _ - 12" ? ~ - . .Y -., ) ",- -- . ---- .Y13 "... Y , 1 0 . PS -- - Y- -- 14 > .Y ~. 90 P6 P4' Fig. I. p-timed Petri nct describing a PLC. I prole ~ ;! . I ~ j ~- < Task 1 ,~ ' -- - -----1 , ~ Pm rl Pl I \ .. ,.. , R1 ,"" ~ ~ L' _ _ L; J .. , rJ ~--- , ~G8 111(u1) !12(u1 ) ,-Y- . , l lis ~ _JL, QI ~' --*-- fp1(up) fp2(upl Fig. 2. Risks structure of the project. Task n The structure that models risks is described in figure 2. Thus. every task may have associated a different risk-structure with some risks (R;) as outcomes of the risk assessment. Risks are characterized by a probability of occurrence (Pi) and some initial impacts (11;), Initial impacts are the consequences on the project if risks become facts and if no mitigation or preventive actions are taken. This study is focused on impacts affecting the "cos," and the "time" of the project. Risks can be controlled by executing corrective actions, A ,. Four types of actions can be considered as is shown in table I. Preventive actions are not treated in this paper, The following conditions are assumed: • A mitigation action (Ai) will reduce the initial impact of a risk. • Several mitigation actions can reduce the same initial impact. • One mitigation action can mitigate more than one initial impact (l n. • Different tasks may own the same risk. The assumption of dependency between risks. initial impacts and mitigation action is allowed. Table I. Action types. Tvpe of actions Description Miligule Modify the impact of a source of risk Prevent Ch~nge the probability of ;/l'()id Accept occurrence . Plan to avoid specitied sources of risk Accept risk exposure. hut do nothing abollt it. ) M itigation actions are described by functions f and g. . j;, is the reduction of initial impact) when action i is applied. Il, is the manipulated variable. Notice that a mitigation action may affcct two decision criteria. 149 "COS(" and "time ". Therefore. given the action i, there are two functionsf" and f,!, where)=1 is referred to the criterion "cost" and )=2 is referred to the criterion "time" . f" (u,) = 0 :::::> Ai does not affect criterion) f, (Ui) :F0 :::::> Ai affects criterion) (2) The cost of mitigation actions is denoted by functions g. Thus, every mitigation action. Ai owns ag , function that describes its cost, also as a function of U, lI i can be an integer or real variable. Examples of discrete mitigation actions are the contract of new workers or the purchasing of new machinery. In the first case, the control variable, (Ui). is the number of new workers andf ij (u,). is the impact reduction that is reached with the contracting. Insurance is an example of continuous mitigation action. perhaps, the most common practice to mitigate risks. In fact, insurance companies have an increasing interest in improving risk estimates to encourage mitigation through scientific modelling (Kleindorfeer and Kunreuther, 1999; Kunreuther, 200 I ). There is considerable scientific work undertaken in the areas of natural, technological and environmental hazards to provide estimates of the probabilities and consequences of events of different magnitudes (Schuster et aI., 1986; Caulkin et ai, 1996; Litan et aI., 1992). After the risks affecting the project have been identified and assessed, the decision about how these risks are going to be managed, has to be taken. This subject is treated in the following section. 4. ANALYSIS VIA MIXED PROGRAMMING The objective of the proposed technique is finding the possible mitigation actions that minimize the cost and the time of the whole project. These criteria are not treated impartially but according to their priorities. considering the main aspects for the team project. Let 1I a manipulated variable. IV, and IVc . denote the concrete forms of the expressions that models the "cosl" and ",ime". respectively. of the whole project. Next. consider a vector of weights of criteria. ~. with si7.e 2. Given a project. the objective function used in this work is the following: min 11 , J = 2: ~k *'f'k k=1 0 < [3k S I and I = I: ~k k=1 (3) Notice that criteria arc variables of very different nature. To use them in the same expression. a normalization procedure is needed. n p '1'1 L 'I'li + L gj i = 1 j = 1 (4) \f'1 i evaluates the cost of every task. n is the number of tasks that the project comprises and p the number of mitigation actions. Lgj is the sum of the mitigation actions cost. \f'2 evaluates the time of the whole project. Its value depends on the morphology of the Petri net that represents the project since parallel tasks have a different treatment from the serial tasks. Additionally. \f' 2 contains terms \f'2i as the expression 5 shows. Section 5 contains an example where is possible to observe a specific format of \f' 2. Let It a vector of dimension p. FVI and FV 2, vectors of dimension n, then: m '1'1/ = Fv,(i) + L GE, . (R . ) with ,= 1.2 j=1 I J (5) where FV I (i) is the value of the rh criterion for the i'h task. if risks are not taken into account. If a risk occurs, this value will be increased by the con'esponding impact of the risk. But. as a risk will occurs or not with a given probability. the mean value of the impact will be used. This value is named "Glo.bal Exposure" and it is computed by multiplying the fisk probability and its impact. As mentioned before. the initial impact of a risk (If) can be reduced with mitigation actions. These values are obtained in the algorithm with f functions described in section 3. The sum of the exposure of each one of the m risks (it is assumed that the task is linked to m risks) gives the 'Total Global Exposure". The "Global Exposure" for task i, risk} and criteria I , GEli (RI )' can be expressed as: P G E,/(R . ) = P(lJ ., - L r ,(11 » J J / ' m m . m = 1 (6) Equation 6 depends on the risk occurrence probability. P" thc initial impact of risk! related to I'h criterion and their impact reduction achieved with the mitigation actions. / ", is the impact reduction of rh criterion when action m is executed. The total impact reduction is computed by adding the results of all the adopted mitigation actions. This optimization prohlem allows constraints III the manipulated variable, 11: (7) 150 where h are general functions. The user can introduce information about the morphology of the risk structure as well as requirements of the functions j ; into the optimisation problem. Thereby, and in accordance with example of figure 2, a constraint could be: "the sum of the impact reductions of actions A I and A J can not be higher than the initial impact Ill" (8) After the optimization problem had been solved, the manipulated variable u, will give rise to the total cost of the project \f' 1, the total time \f' 2 and the actions to undertake. Note that only two parameters have been considered. However the generalisation of this work to a number of criteria higher than two is immediate. All the criteria are treated in the same way. 5. EXAMPLE The p-timed Petri net showed in section 2 (figure I) has been considered as example. Note that transitions t2' and t2" and places P3' and P4' have been introduced in order to model the wait time needed for the completion of the corresponding parallel tasks. Figure 3 depicts the risk-structure that has been identified. Only thc places (tasks) PI, P3 and P5 can suffer impacts due to risks. R, states the "possibility that the implemented system has adverse environmental troubles beyond its permitted limits and increased liabilities". This risk provokes two different impacts, and their values are III and 11 2, affecting to criteria "cost" and "time" respectively. K, is a legal risk. It has an initial impact affecting to the time. Fixed Values (Fv) (value of criteria if no risk are considered) of the tasks and initial impacts are presented: • I 113 I '-( fig . 3. Illustrative example. Risk structure for the tasks of the project. FVI = [4500025691000034567500010000] FV 2 =[ 90 15 50 23 10 90] 111 = 90000 (cos t) 11 2 = 90 (time) (9) 1/3 = 60 (time) Mitigation actions, theirs parameters and functions are described in table 2 and table 3. Table 2. Mitigation actions description. Action Description Type AI Contract Insurance I Real A1 Auxiliary System purchasing Boolean A , Contract Insurance 2 Real A. Contracting new workers Boolean Table 3. Expressions of mitigation actions. Cost Actions IR Cost IR Time Function A I / 11 = ]OOOU I / 12 = -O.lll l gl= II I A] fj l =50001l] /12=80u] g ]= 7 00011] A, /l/= JOII ; / ,] =0 g,= // 3 A, ( " = 5 ()IJIJu I i;] = 6IJu , g ,= Y20()1I ., Notice that the minus sign in mItIgation actions functions (-) means the negative contribution to the specitied criterion. The expression of the objective function for this example according to the figures I and 3 and the expressions (3-7) is : mill J=["\I*'l'1 +["\2*'1'2 U where: ( 10) (11) 151 5.1 Results To solve the above optImIzation problem, the following method has been adopted: the Petri net is explored for getting all the possible paths from the first task to the last one, using the depth tree exploring strategy. Every obtained path is optimized according to J expression and imposing as constrdints that each branch owns the higher time than the other alternatives. The optimal path will be the path that reaches the minimum value. There are solvers from Matlab Optimization toolbox and solvers from NAG foundation toolbox (nag_ ip _bb: function h02bbc) that can be used for the mixed integer programming. Both of them use branch and bound methods. Four experimental modules have been undeltaken taking into account several risk probabilities. The values that are shown are the manipulated variable (11) , the total "cost" of the project (\f'I) and the " tim e" (\f' ~ ) , both of them in the case of mitigation and no mitigation as well. The manipulated variables represent thc mitigation actions that should be undertaken. The higher differences in \f'1 and \f' 2 are obtained for the probabilities P/"'P1 =O.9. In the case PI »P2. mitigation actions A2 and A4 are nevcr taken. This is due to the fact that the cost functions (gl and g3) and the cost reductions if " and f; I) are better. Conversely, in the case of PI ~" P 2 ' they are chosen as consequence of their high time reduction. Obviously, with PI= p }= O the nominal values are reached (no mitigation actions are realised). Table 4. Experiments and outcomes. Risk Without Weights Prohabilimitigation ["\1 » ["\2 ["\1 <> ["\2 ties actions P, ~ p . - 0.9 U=[90 0 1000 01 u=[ 40 1 500 I) 't' ,=188 13 C=90226 c = 1 05876 Ii T=45 2. 1 T=267.6 T= 444 P, =P,= Ii .! 1/ =[90 0 1000 0) 1/= [ 401500 I] C=116136 c = 1 06226 C= 121 876 T=276 T=176.9 T=256 .4 p , P, - OIJ ! u- [IJO 0 0 0] u ~ [9 0 0 0 0] CIO R036 C=I0 72 26 C ~ 10 72 26 T=25 7. 1 T=257. 19 T=257.19 P,- P ,- O u= [O Cl Cl 0) 1/ =[ 000 0] Cl0 7136 C= 10 7 136 (' ·107 13 6 T255 T=2 55 T< 255 Figure 4 depicts an experiment where different values for the risk probabilities have been considered. The solid line (red) means the cost C, and the time. T, whercas the dotted line (green) rcpresents the constant values for these parameters. P1=0 .1 P2=0.1 1.2 r- , .. _ ..........•.•.• __ ___ . __ ._ .•.. .1 I I I 0.9 L---'-_-'----'"---'--_~----L_-'----'"---'-----' o 0.1 0.2 0.3 0.4 0.5 0.6 0.1 0.8 0.9 350 m . '" . ~ ' . . .. \ \ ! ; .................. _ ... .... ......... _ ... .. .... _\ 25O~~~~~~~~~~~~ o 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 beta2 Fig. 4. Expression of the cost and the time of the project with the probabilities P /= 0.1 and P 2=0.7. 6. CONCLUSIONS This paper describes an algorithm to help project managers to schedule tasks in order of minimizing cost and time. This method bccomes an useful tool for treating projects in the presence of uncertainties or available information in low detail. The basic framework of task s is provided in a p-timed Petri Net. The time execution of the project tasks are assigned to places. The adopted risk structure allows the storing and organizing of all the information about risks (i .e. initial impacts, mitigation actions). The link between them gives rise to an optimization problem where the objective is the minimization of the whole cost and time of the project. For that, mitigation actions an: rdated to risks. The problem has been stated as a mixed integer optimization problem as consequence of the different types of variables (real. integer or boolean) involved in the functions that modcl thc action s. A multicriteria approach has been introduced. It allows that the assessment of several candidates is based on some criteria like "cost " or "timc'·. A simple example show s how the algorithm takes the decisions (mitigation actions to undertake). REFERENCES Alquier A.M .. E. Cagno. F. Caron and M.A. Ridao,. (2001). In: Th e Frollliers o(proj ecl Manogemelll Research. Chap . 21. pp. 349-363. Prujcct Ma nagemcnt Institute. Chapman C. and S. Ward. (2000) "Project Risk A fon(1 ge ll1 f' 17I Processe s, Techniq1les al1d II/.\i f!, hls ". John Wiley & Son s. Crouhy M. , Rob ert Mark and Dan Gaiai.(2000) "Risk Management". McGr aw Hill. 152 David R .. H. Alia . (1994). "Petri nets for modelling of dynamic systems: a survey". AUlomalica, 30, pp 175-202 Doherty N. (1997). "Financial innovation for financing and hedging catastrophe risk". Proc. of the Fifth Alexander Howden Conference on Disaster Insurance, Goal Coast. Grabowski M , 1. Merrick, J. Harrald, T. Mazzuchi and J. Van Dorp. (2000). "Risk Modeling in Distributed, Large-Scale Systems". IEEE Transactiuns un Systems, Man, and Cybernetics, 30,651-660 . Gu T. and P.A. Bahri. (1999) "Timed Petri-net representation for short term scheduling of multi-product batch plants" . Proceedings of the 1999 American Control Conference, pp. 40924096 . Hyatt L. and Ro senberg, L. (2000). "Sofware metr!cs program for risk assessment ". Acta AstronaulIca 40 , NO 2-8,223-233. laafari A. (2001) "Management of risks, uncertainties and opportunities on projects: time for a fundamental shift". International J01lrnal of Project Mana ge me nt , J9,89-101. Kleindorfer P. and H. Kunreuther. (1999). "Challenges facing the insurance industry in managing catastrophic ri sks". The financing of Catastrophe Risk. University of Chicago Press. Kunreuther H. (200 I) . "Incentives for mitigation investments and more effcctive risk management :the need for public-private partnerships". Journal of Hazardous Materials, 86,171-185. Litan R., F. Khringold, K. Clark, 1. Khadhkar. (\ 992) . "Physical damage and Human Loss: The Economic Impact of Earthquake Mitigation Mesures ". New York: Insurance Information I nstitute Press. Schuster, R. (1986). "Landslide Dams : Processes. Risk and Mitigation". Am erican Sociery of Cil'iI Engineer. Silva M. (I985). "Las redes de Petri: en la AUlUmatica )' la Injhrmatic u" . AC. Zafra-Cabeza A., M.A. Ridao and E.F. Camacho . (2001) "Sistema de Ayuda a la de cision en el proccso de cIaboracion de of ertas usando tccnicas multicriterio'. Proc. IX CAEPIA-TTIA. Vol. I. pp. 479-488. Zafra -Ca beza A., M.A. Ridao and E.F. Camach o. (2 002a) . "A Decision Support System for Bidding process ", Proc. 15th IFAC World Congress on Automatic Control. 7. afraCa heza A. , M.A. Ridao and E.F. Camacho. (2002h) . "Risk Mitigation in the hidding process using mixed programming". Proc. IEEE International Conference on Sy stems. Man and Cybernetics. Zafra-C abeza A. , M.A. Ridao and E.F. Camacho. (2003). "A multicrite ri a risk-hased DSS for bidding using integer programming". Proc. If AC C AO (to appear).