https://hal.inria.fr/inria-00073098Chauvet, FabriceFabriceChauvetSAGEP - Simulation, analyse et gestion des systÃ¨mes de production - INRIA Lorraine - Inria - Institut National de Recherche en Informatique et en AutomatiqueLevner, EugeneEugeneLevnerProth, Jean-MarieJean-MarieProthSAGEP - Simulation, analyse et gestion des systÃ¨mes de production - INRIA Lorraine - Inria - Institut National de Recherche en Informatique et en AutomatiqueOn PERT Networks with AlternativesHAL CCSD1998PERT networkshortest pathalternative activitiesMakespan optimization[INFO.INFO-OH] Computer Science [cs]/Other [cs.OH]Inria, Rapport De Recherche2006-05-24 11:51:362023-02-07 03:39:442006-05-31 14:24:27enReportsapplication/pdf1Management of projects often requires decisions concerning the choice of alternative activities. Then, the completion time of the whole project (i.e. the makerpan) is computed. In this paper, we aim at selecting the required activities simultaneously with the computation of the makespan. This problem is referred to as PERT Problem with Alternatives (PPA). The corresponding model is similar to a conventional PERT graph, except that two types of nodes are involved to represent either the choice between activities, or the fact that a set of activities should be completed before starting another set of activities. A formalization of the problem and some important properties concerning the optimal solution are given. Several well- solvable cases of the problem and a powerful decomposition algorithm running in polynomial time are presented. This decomposition is applicable for solving many real-life problems.