a minmax regret approach to the critical path method with task interval times -凯发官网入口

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