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.     

On the latest starting times and criticality of activities in a network with imprecise durations

This paper deals with problems of computing possible values of latest starting times and determining types of criticality for all activities in a network with interval or fuzzy activity durations. Although the problem of computing the latest starting times has been solved, a novel polynomial algorithm which is easy to understand and improves complexity is proposed.     

Analysis of critical paths in a project network with fuzzy activity times

This paper proposes an approach to critical path analysis for a project network with activity times being fuzzy numbers, in that the membership function of the fuzzy total duration time is constructed. The basic idea is based on the extension principle and linear programming formulation. A pair of linear programs parameterized by possibility level α is formulated to calculate the lower and upper bounds of the fuzzy total duration time at α. By enumerating different values of α, the membership function of the fuzzy total duration time is constructed, and the fuzzy critical paths are identified at the same time. Moreover, by applying the Yager ranking method, definitions of the most critical path and the relative degree of criticality of paths are developed; and these definitions are theoretically sound and easy to use in practice. Two examples with activity times being fuzzy numbers of L-R and L-L types discussed in previous studies are solved successfully to demonstrate the validity of the proposed approach. Since the total duration time is completely expressed by a membership function rather than by a crisp value, the fuzziness of activity times is conserved completely, and more information is provided for critical path analysis.     

Project Scheduling under Time Dependent Costs – A Branch and Bound Algorithm

In a given project network, execution of each activity in normal duration requires utilization of certain resources. If faster execution of an activity is desired then additional resources at extra cost would be required. Given a project network, the cost structure for each activity and a planning horizon, the project compression problem is concerned with the determination of optimal schedule (duration) of performing each activity while satisfying given restrictions and minimizing the total cost of project execution. This paper considers the project compression problem with time dependent cost structure for each activity. The planning horizon is divided into several regular time intervals over which the cost structure of an activity may vary. But the cost structure of the activities remains the same (constant) within a time interval. Key events of the project attract penalty for finishing earlier or later than the corresponding target times. The objective is to find an optimal project schedule minimizing the total project cost. We present a mathematical model for this problem, develop some heuristics and an exact branch and bound algorithm. Using simulated problems we provide an insight into the computational performances of heuristics and the branch and bound algorithm.     

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.     

On the hardness of evaluating criticality of activities in a planar network with duration intervals

Complexity results for problems of evaluating the criticality of activities in planar networks with duration time intervals are presented. We show that the problems of asserting whether an activity is possibly critical, and of computing bounds on the float of an activity in these networks are NP-complete and NP-hard, respectively.     

Efficient sensitivity analysis of PERT network performance measures to significant changes in activity time parameters

Using a Program Evaluation and Review Technique network model of a project schedule, a method is presented to estimate the effects of changes to the probability distribution for any activity time on several project schedule measures. Computational results show this method to be significantly faster and more accurate than a previously published approach, which estimated the effects of changes to the means of normally distributed activity times on expected project completion time and activity criticality. In addition, the new method allows more flexibility to model changes to activity times, including independent changes to parameters and even changes in the distributional form. Finally, the new method estimates the effects of these changes on several additional performance measures, including the probability of meeting a specified due date and a project (penalty) cost function. All desired estimates are obtained from a single set of simulation runs.     

Network Criticality with Multiple Work-Patterns

When multiple work-patterns (also called calendars) are present in a network, it is quite common that there is no critical path spanning the network. This paper explains why this is so. To address the problem, the normal definition of criticality in project networks is split into two-delay criticality, and compress criticality.     

Cantorian Fractal Spacetime and Information in Neural Network of the Human Brain

The neural networks of the human brain act as very efficient parallel processing computers co-ordinating memory related responses to a multitude of input signals from sensory organs. Information storage, update and appropriate retrieval are controlled at the molecular level by the neuronal cytoskeleton which serves as the internal communication network within neurons. Information flow in the highly ordered parallel networks of the filamentous protein polymers which make up the cytoskeleton may be compared to atmospheric flows which exhibit long-range spatiotemporal correlations, i.e. long-term memory. Such long-range spatiotemporal correlations are ubiquitous to real world dynamical systems and is recently identified as signature of self-organized criticality or chaos. The signatures of self-organized criticality i.e. long-range temporal correlations have recently been identified in the electrical activity of the brain. The physics of self-organized criticality or chaos is not yet identified. A recently developed non-deterministic cell dynamical system model for atmospheric flows predicts the observed long-range spatiotemporal correlations as intrinsic to quantum-like mechanics governing flow dynamics. The model visualises large scale circulations to form as the result of spatial integration of enclosed small scale perturbations with intrinsic two-way ordered energy flow between the scales. Such a concept maybe applied for the collection and integration of a multitude of signals at the cytoskeletal level and manifested in activation of neurons in the macroscale. The cytoskeleton networks inside neurons may be the elementary units of a unified dynamic memory circulation network with intrinsic global response to local stimuli. A cell dynamical system model for human memory circulation network analogous to atmospheric circulations network is presented in this paper. The model like the analysis of Koruga et al. make use of certain connections to the concept of Cantorian-Fractal spacetime.     

A heuristic method for RCPSP with fuzzy activity times

In this paper, we propose a heuristic method for resource constrained project scheduling problem with fuzzy activity times. This method is based on priority rule for parallel schedule generation scheme. Calculation of critical path in this case requires comparison of fuzzy numbers. Distance based ranking of fuzzy number is used for finding the critical path length and concept of shifting criticality is proposed for some of the special cases. We also propose a measure for finding the non-integer power of a fuzzy number. We discuss some properties of the proposed method. We use an example to illustrate the method.     

A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations

We present an optimal solution procedure for the resource-constrained project scheduling problem (RCPSP) with generalized precedence relations (RCPSP-GPR) with the objective of minimizing the project makespan. The RCPSPGPR extends the RCPSP to arbitrary minimal and maximal time lags between the starting and completion times of activities. The proposed procedure is suited for solving a general class of project scheduling problems and allows for arbitrary precedence constraints, activity ready times and deadlines, multiple renewable resource constraints with time-varying resource requirements and availabilities, several types of permissible and mandatory activity overlaps and multiple projects. It can be extended to other regular and non-regular measures of performance. Essentially, the procedure is a depth-first branch-and-bound algorithm in which the nodes in the search tree represent the original project network extended with extra precedence relations to resolve a number of resource conflicts. These conflicts are resolved using the concept of minimal delaying modes, which is an extension of the notion of minimal delaying alternatives for the RCPSP. Several bounds and dominance rules are used to fathom large portions of the search tree. Extensive computational experience is reported.     

Developing activity duration specification limits for effective project control

We propose a new structure for guiding project control decisions to ensure that a project is completed on schedule when activity durations are uncertain and modeled by random variables. This structure consists of specifying a specification limit for each activity duration. During the project, if the time to complete an activity is going to exceed its specification limit, actions are taken, at some cost, to bring the time down to that limit. We present an algorithm that selects specification limits to achieve targeted on-time probabilities at minimum cost. The method involves estimating the effect of small changes in specification limits on the probability of completing a project on time and on the cost of control actions. The required simulation-based estimates for all activities are obtained in a single set of simulation runs. Computational results show the algorithm to be efficient to apply and, when compared to a more ad hoc approach of using activity importance measures (specifically, activity criticality), the use of the resulting specification limits to be of significant benefit in guiding project control decisions.     

Tools for resource-constrained project scheduling and control: forward and backward slack analysis

Project managers generally consider slack as a measure of the scheduling flexibility associated with the activities in the project network. Nevertheless, when resource constraints appear, this information must be calculated and analysed carefully. In this context, to handle project feasible schedules is very hard work for project managers. In order to develop useful tools for decision making, the authors extend the concepts of activity slack and define a new activity criticality index based on them that permits us to classify the activities in the resource-constrained project scheduling and control context. Additionally, these new concepts have been integrated into standard project management software as new commands. Hence the capabilities of project management software are improved. Finally, an example that illustrates the use and application of the new activity classification is also included.     

Finding long and similar parts of trajectories

A natural time-dependent similarity measure for two trajectories is their average distance at corresponding times. We give algorithms for computing the most similar subtrajectories under this measure, assuming the two trajectories are given as two polygonal, possibly self-intersecting lines with time stamps. For the case when a minimum duration of the subtrajectories is specified and the subtrajectories must start at corresponding times, we give a linear-time algorithm. The algorithm is based on a result of independent interest: We present a linear-time algorithm to find, for a piece-wise monotone function, an interval of at least a given length that has minimum average value. In the case that the subtrajectories may start at non-corresponding times, it appears difficult to give exact algorithms, even if the duration of the subtrajectories is fixed. For this case, we give (1+ε)-approximation algorithms, for both fixed duration and when only a minimum duration is specified.     

Criticality in Stochastic Networks

The common definition of ‘criticality’ in stochastic networks is insufficiently general, and often counter-intuitive. An alternative metric, ‘cruciality’ has been proposed. The combination of the common criticality metric and cruciality is shown to provide information about the ‘uncertainty impact’ and ‘controllable benefit’ in the network.     

Determining the Optimal Flows in Zero-Time Dynamic Networks

Here we are dealing with minimum cost flow problem on dynamic network flows with zero transit times and a new arc capacity, horizon capacity, which denotes an upper bound on the total flow traversing through on an arc during a pre-specified time horizon T. We develop a simple approach based on mathematical modelling attributes to solve the min-cost dynamic network flow problem where arc capacities and costs are time varying, and horizon capacities are considered. The basis of the method is simple and relies on the appropriate defining of polyhedrons, and in contrast to the other usual algorithms that use the notion of time expanded network, this method runs directly on the original network.     

基于完工隶属度的网络计划优化

针对网络计划模型中工序作业时间的不确定性,引入工序完工隶属函数,以及完工隶属函数的运算。在此基础上,提出并探讨了在缩短总工期时的最优分配缩短作业时间问题,同时,利用完工隶属度建立了相应的模型及求解方法,最后举例说明了该模型与方法的实用性。     

Evaluating Project Completion Times When Activity Times are Erlang Distributed

One aspect of project planning risk assessment is to do with the uncertainty of the project duration. This uncertainty can be quantified by determining the project completion time distribution. A brief review of the existing literature on project duration risk assessment methodologies is given and their advantages and disadvantages evaluated. A development of the moments method based on Erlang distribution of activity times provides an accurate estimate of a project completion time distribution for a large range of practical situations and also is the basis upon which multi-modal input distributions of activity times can be handled. The method is assessed by a number of illustrative examples.     

The use of fuzzy variables in pert

In this paper we present a method—called Fpert—for estimating a project completion time in the situation when activity duration times in the project network model are given in the form of fuzzy variables—fuzzy sets on time space. Theoretical foundations of the method as well as results of calculations derived from a simple example are included.     

Finding the critical path in an activity network with time-switch constraints

An activity network is an acyclic graph with non-negative weights and with a unique source and destination. A project consisting of a set of activities and precedence relationships can be represented by an activity network and the mathematical analysis of the network provides useful information for managing the project. In a traditional activity network, it is assumed that an activity always begins after all of its preceding activities have been completed. This assumption may not be adequate enough to describe some practical applications where some forms of time constraints are attached to an activity. In this paper, we investigate one type of time constraint called time-switch constraint which assumes that an activity begins only in a specified time interval of a cycle with some pairs of exclusive components. Polynomial time algorithms are developed to find the critical path (or longest path) and analyze the float of each arc in this time-constrained activity network. The analysis shows that the critical path and float in this context differ from those of a traditional activity network in some management perspectives and thus, consideration of the time-switch constraint leads to enhanced project management through more effective use of budgets and resource allocation.