A new probabilistic approach to the path criticality in stochastic PERT

The notion of critical path is a key issue in the temporal analysis of project scheduling in deterministic setting. The very essence of the CPM consists in identifying the critical path, i.e., the longest path in a project network, because this path conveys information on how long it should take to complete the project to the project manager. The problem how can a stochastic counterpart of the deterministic critical path be defined is an important question in stochastic PERT. However, in the literature of stochastic PERT this question has so far almost been ignored, and the research into the random nature of a project duration has mainly been concentrated on the completion time in stochastic PERT in which any concrete special path is not specified. In the present paper we attempt to take first steps to fill this gap. We first developed a probabilistic background theory for univariate and bivariate marginal distributions of path durations of stochastic PERT whose joint path durations are modelled by multivariate normal distribution. Then, a new probabilistic approach to the comparison of path durations is introduced, and based on this comparison we define the concept of probabilistically critical path as a stochastic counterpart of the deterministic critical path. Also, an illustrative simple example of PCP and numerical results on the established probability bounds are presented.     

The Most Critical Path in a PERT Network

The classical PERT approach uses the path with the largest expected duration as the critical path to estimate the probability of completing a project by a given deadline. However, in general, such a path is not the ‘most critical’ path and does not provide the smallest estimate for the probability of completion time. This paper studies the ‘most critical path’ problem and formulates it as an optimal path problem in a deterministic network with a two-attribute fractional objective function. An exact solution approach is presented for the optimal path problem which also gives the solution to the most critical path problem. The illustrative examples as well as our computational results demonstrate that the proposed algorithm provides estimates for the probabilities of completion time that are much more accurate than those of the classical approach.     

Path critical index and activity critical index in PERT networks

The criticality index of an activity is the probability that the activity is on the critical path of the network. The criticality index of a path is the probability that the duration of the path is greater than or equal to the duration of every other path in the network. In this paper, a new exact formula is presented to compute the path critical index (PCI) and activity critical index (ACI) for the PERT network with any structure. It is assumed that each activity duration time is a discrete random variable. Numerical examples presented in this paper prove the method is highly efficient and has excellent results compared to Dodin and Elmaghraby's approach.     

A rule for slack allocation proportional to the duration in a PERT network

In this paper, we define a new rule for the resolution of the slack allocation problem in a PERT network. This problem exists of allocating existing extra time in some paths among the activities belonging to those paths. The allocation rule that we propose assigns extra time to the activities proportionally to their durations in such a way that no path duration exceeds the completion time of the whole project. This time allocation enables us to make a schedule for the PERT project under study. We give two characterizations of the rule and we compare it with others that have been previously defined in the literature.     

A New Distribution Function for Risk Analysis

This paper presents an alternative to the beta continuous probability distribution for risk analysis. Particular attention has been given to two major applications of distributions, namely project management risk and critical path analysis (PERT). In conjunction with the beta, the triangular and normal distributions are frequently employed in order to give sufficient robustness to risk analysis. The beta distribution, as used in PERT, has a major theoretical implementation flaw. The new distribution was developed to give a possible alternative method of assessing risk. It is shown that the requirement to estimate the most pessimistic variate may be replaced by the probability to exceed the mode. Proposals for other simplifications in risk analysis are discussed. Practical means to validate the most appropriate distributions for risk analysis are outlined, and a cost-data case study is included.     

Multi-objective time–cost trade-off in dynamic PERT networks using an interactive approach

We develop a multi-objective model for the time–cost trade-off problem in a dynamic PERT network using an interactive approach. The activity durations are exponentially distributed random variables and the new projects are generated according to a renewal process and share the same facilities. Thus, these projects cannot be analyzed independently. This dynamic PERT network is represented as a network of queues, where the service times represent the durations of the corresponding activities and the arrival stream to each node follows a renewal process. At the first stage, we transform the dynamic PERT network into a proper stochastic network and then compute the project completion time distribution by constructing a continuous-time Markov chain. At the second stage, the time–cost trade-off problem is formulated as a multi-objective optimal control problem that involves four conflicting objective functions. Then, the STEM method is used to solve a discrete-time approximation of the original problem. Finally, the proposed methodology is extended to the generalized Erlang activity durations.     

一个绘制统筹图的算法

统筹图又叫计划网络图。任给一个其元素叫做工序（或作业或活动）的有限偏序集，要绘制它的一个最优统筹图，限含虚工序数目为最少者，是一个尚未从理论上解决的问题。本文讨论了虚工序产生的原因和如何减少虚工序数量的一些途径；指出了高度为二的编序集其最优统筹图含虚工序数目达到最大且等于该偏序集框图的边数的充分必要条件；本文给出了一个绘制最优统筹图的近似算法，此算法弥补了文[2]和[3]所给算法的一些不足之处。     

A linear Bayesian stochastic approximation to update project duration estimates

By relaxing the unrealistic assumption of probabilistic independence on activity durations in a project, this paper develops a hierarchical linear Bayesian estimation model. Statistical dependence is established between activity duration and the amount of resource, as well as between the amount of resource and the risk factor. Upon observation or assessment of the amount of resource required for an activity in near completion, the posterior expectation and variance of the risk factor can be directly obtained in the Bayesian scheme. Then, the expected amount of resources required for and the expected duration of upcoming activities can be predicted. We simulate an application project in which the proposed model tracks the varying critical path activities on a real time basis, and updates the expected project duration throughout the entire project. In the analysis, the proposed model improves the prediction accuracy by 38.36% compared to the basic PERT approach.     

A dependent project evaluation and review technique: A Bayesian network approach

The Program Evaluation and Review Technique (PERT) dates back to 1959. This method evaluates the uncertainty distribution of a project’s completion time given the uncertain completion times of the activities/tasks comprised within it. Each activity’s uncertainty was defined originally by a unique two parameter beta PERT distribution satisfying what is known to be the PERT mean and PERT variance. In this paper, a three-parameter PERT family of bounded distributions is introduced satisfying that same mean and variance, generalizing the beta PERT distribution. Their additional flexibility allows for the modeling of statistical dependence in a continuous Bayesian network, generalizing in turn the traditional PERT procedure where statistical independence is assumed among beta PERT activity durations. Through currently available Bayesian network software and the construction of that PERT family herein, the coherent monitoring of remaining project completion time uncertainty given partial completion of a project may become more accessible to PERT analysts. An illustrative example demonstrating the benefit of monitoring of remaining project completion time uncertainty as activities complete in that Bayesian fashion shall be presented, including expressions and algorithms for the specification of the three prior parameters for each activity in the project network to adhere to classical the PERT mean and PERT variance and a degree of statistical dependence between them.     

A new method for constructing a minimal PERT network

A project is an enterprise consisting of several activities which are to be carried out in some specific order. The activities and the order in which they need to be carried out can be represented by a PERT network. The PERT technique is a traditional, well-known approach to the expert of project management. When networks are used, it often becomes necessary to draw dummy activities. Since the computation of project completion time is proportional to the number of arcs, including dummy arcs, it is desirable to draw a network with as few dummy activities as possible.In this paper, we propose a new method for constructing, for a given project scheduling problem, a PERT network having as small as possible the number of dummy arcs by using some results on line graphs. This algorithm deals with the existence of transitive arcs. The paper contains illustrative examples, proofs of some theoretical results as well as a comparative study with a similar algorithm known in the literature. Computational results showed the superiority of our algorithm.     

马尔可夫骨架PERT网络的最长路径

本文利用马尔可夫骨架过程理论研究PERT网络模型，其中网络各弧线的长度是相互独立的随机变量。文中构造了一个马尔可夫骨架过程，利用其向后方程求解随机网络最长路径长度的分布函数。     

On path correlation and PERT bias

Most studies of project time estimation assume that (a) activity times are mutually independent random variables; many also assume that (b) path completion times are mutually independent. In this paper, we subject the impact of both these assumptions to close scrutiny. Using tools from multivariate analysis, we make a theoretical study of the direction of the error in the classical PERT method of estimating mean project completion time when correlation is ignored. We also investigate the effect of activity dependence on the normality of path length via simulation.     

Estimating a Project's Completion Time Distribution Using Intelligent Simulation Methods

Other researchers have indicated the theoretical problems of using the PERT techniques commonly described in elementary operational research and operations management texts. Monte Carlo simulation has often been suggested as an alternative means of analyzing PERT networks but simulating a network of real world proportions is often assumed to be prohibitively expensive. This paper measures the accuracy and cost of standard PERT and simulation methods for real world sized problems. In addition, several computational heuristics are described and tested that indicate that simulation is a viable alternative. The results indicate that intelligent simulation of PERT networks is considerably more accurate than standard PERT analysis and is definitely not cost prohibitive.     

Resource allocation in dynamic PERT networks with finite capacity

This article models the resource allocation problem in dynamic PERT networks with finite capacity of concurrent projects (COnstant Number of Projects In Process (CONPIP)), where activity durations are independent random variables with exponential distributions, and the new projects are generated according to a Poisson process. The system is represented as a queuing network with finite concurrent projects, where each activity of a project is performed at a devoted service station with one server located in a node of the network. For modeling dynamic PERT networks with CONPIP, we first convert the network of queues into a stochastic network. Then, by constructing a proper finite-state continuous-time Markov model, a system of differential equations is created to solve and find the completion time distribution for any particular project. Finally, we propose a multi-objective model with three conflict objectives to optimally control the resources allocated to the servers, and apply the goal attainment method to solve a discrete-time approximation of the original multi-objective problem.     

The robustness of mean and variance approximations in risk analysis

This paper examines further the problem of estimating the mean and variance of a continuous random variable from estimates of three points within the distribution, typically the median or mode and two extreme fractiles. The problem arises most commonly in PERT and risk analysis where it can usually be assumed that the distribution in question is bell-shaped and positively skewed, often typified by a Beta distribution. Over the years, a number of alternative approximations have been proposed, usually as modifications to the original PERT formulae. The accuracy of a number of these approximations is investigated based not only on a Beta distribution, but also for three other commonly used bell-shaped, positively skewed distributions, namely the Gamma, Lognormal and F distributions. It is shown that a balanced weighted average of the median and the 4% fractiles provides a consistent estimator of the distribution mean across all four distributions. Furthermore, reasonably accurate estimates of the variance can also be obtained by treating the three fractiles as defining an equivalent discrete distribution with the same probability weight as in the formula for the mean.     

Mixture densities for project management activity times: A robust approach to PERT

PERT is a widely utilized framework for project management. However, as a result of underlying assumptions about the activity times, the PERT formulas prescribe a light-tailed distribution with a constant variance conditional on the range. Given the pervasiveness of heavy-tailed phenomena in business contexts as well as inherently differing levels of uncertainty about different activities, there is a need for a more flexible distribution which allows for varying amounts of dispersion and greater likelihoods of more extreme tail-area events. In particular, we argue that the tail-area decay of an activity time distribution is a key factor which has been insufficiently considered previously. We provide a distribution which permits varying amounts of dispersion and greater likelihoods of more extreme tail-area events that is straightforward to implement with expert judgments. Moreover, the distribution can be integrated into the PERT framework such that the classic PERT results represent an important special case of the method presented here.     

A simple approach to fuzzy critical path analysis in project networks

This paper develops a simple approach to critical path analysis in a project network with activity times being fuzzy numbers. The idea is based on the linear programming (LP) formulation and fuzzy number ranking method. The fuzzy critical path problem is formulated as an LP model with fuzzy coefficients of the objective function, and then on the basis of properties of linearity and additivity, the Yager’s ranking method is adopted to transform the fuzzy LP formulation to the crisp one which can be solved by using the conventional streamlined solution methods. Consequently, the critical path and total duration time can be obtained from the derived optimal solution. Moreover, in this paper we also define the most critical path and the relative path degree of criticality, which are theoretically sound and easy to use in practice. An example discussed in some previous studies illustrates that the proposed approach is able to find the most critical path, which is proved to be the same as that derived from an exhausted comparison of all possible paths. The proposed approach is very simple to apply, and it is not require knowing the explicit form of the membership functions of the fuzzy activity times.     

An upper bound on the expected completion time of PERT networks

In this paper the problem of determining an upper bound on the expected project completion time, described by the PERT network, is considered. It is assumed that activity durations are independent random variables with given means. The exact forms of probability distributions do not have to be known; however, their cumulative distribution functions are expected to belong to the so-called NBUE class. Very simple algorithms for deriving this bound are presented. The computations can even be performed manually for more involved networks. Our approach producing a pessimistic evaluation of the expected value of the project duration, extends considerably the information obtained through the use of the classical PERT that always underestimates this value. The results are illustrated by a simple example, and errors of approximations are discussed.     

关键线路变迁分析方法及其应用

传统的关键路线法(CPM),计算工序的诸多时间参数来确定工期与关键路线,对于简单网络方便可行.但对于大型的复杂网络,必然存在时间参数多、计算量大等问题;加之,工程项目具有普遍的复杂性,时常需要进行工期优化,关键线路可能发生变迁.为了简化计算,运用0-1规划方法,在WinQSB环境下建立适应不同规模的网络计划参数计算的数学模型并快速求解,再通过目标函数的灵敏度分析,确定变量的变化范围,解决关键线路变迁问题.算例表明,提出的方法无需重新计算便可快捷地断定关键线路是否发生变迁.     

计划评审技术的改进

由于计划评审技术存在的不足,导致项目管理存在一定的偏差.对计划评审技术中的活动期望时间和方差的公式做了改进,从而提高了项目管理的精确性.还指出计划评审技术中活动期望时间和方差的计算公式,实际上是改进后公式的特殊情形.