Researches On The Theory And Application Of Stochastic Activity Networks

Network analysis is a widely used technique for planning and scheduling of complex projects. In practice activity durations are subject to randomness due to uncertain factors such as material availability, weather conditions, cash flows and others. Therefore activity duration is better represented by random variable, and stochastic activity networks can be used to schedule projects by describing precedence relationship among the activities. A stochastic activity network is a directed acyclic network, where the nodes and arcs of the network represent the events and activities of a project, respectively. The arc lengths (i.e., the activity durations) are random variables.It is well known that the estimation of the project completion time is one of the most important problems in the management of projects. The project completion time is equal to the length of the longest path, also called network realization time. In the case of deterministic activity durations, the project completion time can be easily computed by using many longest path algorithms. However, when the activity durations are stochastic, the path lengths are random variables, so is the project completion time. Therefore, the analysis of the project completion time becomes a computationally intractable task. This thesis deals with project completion time problem and shortest path problem in stochastic activity networks. The thesis is organized as follows.In Chapter1, we present the background of stochastic activity networks, and review the history and current status of the problem of determining the longest and shortest paths in stochastic activity networks.Chapter2introduces the basic concepts of activity networks, PERT model and stochastic activity networks. The definitions and basic properties of continuous-time Markov chains and Markov skeleton processes are presented. In Chapter3we firstly give the following two analytical algorithms for obtaining the distribution function of the project completion time: series-parallel reduction method for simple networks and Markov chain approach for networks with exponentially distributed activity durations. Then a Markov skeleton processes approach was developed for computing the distribution of the project completion time in general activity networks, where the activity durations are independent random variables. We construct a Markov process by supplementary variable technique and show that the time until absorption into the absorbing state starting from the initial state is equal to the project completion time. Then an algorithm utilizing the backward equations of Markov skeleton processes is presented for calculating the probability distribution of the project completion time.Chapter4provides Monte Carlo simulation procedures and bounding or approximation approaches. Owing to the computational difficulties arising from the exact analysis, some researchers have focused attention on Monte Carlo simulation methods for estimating the distribution or mean of the project completion time. The straightforward simulation and conditional sampling are presented. The approaches to bound or approximate the distribution function and mean of the project completion time are also discussed. Then we give the kth moments of the longest path, and describe the activity network models by partial differential integral equations using supplementary variable techniques. Finally, the estimation of the distribution function of arcs in stochastic activity networks is presented. The evolving process of every activity can be represented as a stochastic process. In other words, the progress process of every activity can be treated as a Brown motion with drift. The distribution functions of arcs are obtained by estimating the drift parameters and diffusion parameters of the Brown motion.Chapter5considers the shortest path problem. The Markov chain method for networks with exponentially distributed activity durations is described, and then a new algorithm based on Markov skeleton processes is proposed for obtaining the distribution of the shortest path length in general networks. Finally, the path optimality indices are analyzed.