Multiple schedules and measures of resource constrained float

The conventional analysis of a resource constrained network produces a single schedule. A measure of float for each activity can be defined by examining the sequences of activities, incorporating the linkages implied by the sharing of resources in this particular schedule. However, the resultant floats are specific to one schedule and the analysis ignores the flexibility inherent in many resource constrained networks. It is often possible to employ alternative resource allocations resulting in schedules with identical overall durations but different timings for individual activities; in one schedule an activity may be critical but in another it may have significant float. A systematic exploration of alternative schedules reveals the flexibility of the network and the consequent variation in activities' floats. This paper defines new parameters describing these characteristics of activities in resource constrained networks. The practical value of the parameters is demonstrated in an example in which the measures of float guide the project planner to an alternative schedule, avoiding a critical dependency on a problematic activity and reducing the risk to the project at no additional cost.     

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.     

The resource constrained project scheduling problem with multiple crashable modes: A heuristic procedure

We present a heuristic procedure for a nonpreemptive resource constrained project scheduling problem in which the duration/cost of an activity is determined by the mode selection and the duration reduction (crashing) applied within the selected mode. This problem is a natural combination of the time/cost trade-off problem and the resource constrained project scheduling problem. The objective is to determine each activity's start (finish) time, mode and duration so that the total project cost is minimized. Total project cost is the sum of all activity costs and the penalty cost for completing the project beyond its due date. We introduce a multi-pass algorithm. We report computational results with a set of 100 test problems and demonstrate the efficacy of the proposed heuristic procedure.     

An investigation into the relationship of heuristic performance with network-resource characteristics

Constrained resource project management heuristics are analyzed and their performance is assessed related to well defined project types. Such results have shown that using the overall performance measure of a given heuristic can, in some situations, be misleading.An efficient heuristic, which combines resource and criticality factors is also proposed. Computational experiments on a set of 6120 networks varying in size from 45–666 activities, 3 resources, and under different network parameters are reported. The proposed heuristic outperforms the best existing dispatching rules in certain project classes and also on problem sets appearing in the literature.     

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.     

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.     

Dynamic priority rule-based forward-backward heuristic algorithm for resource levelling problem in construction project

Resource levelling aims at minimizing the fluctuation of resource usage, which is accomplished by shifting non-critical activities within their float according to some heuristic rules. Most of these rules adopted a unidirectional scheduling based on a static priority rule. In this paper, we propose a dynamic priority rule-based forward-backward heuristic algorithm (FBHA). The FBHA optimizes resource allocation by shifting non-critical activities within their forward free float (FFF), forward total float (FTF) and backward free float (BFF), successively. A project is divided into several phases during each forward/backward scheduling module. In each phase, the shifting sequence and days of non-critical activities depend on a dynamic priority rule set. The FBHA is integrated into the Microsoft Project 2007 commercial software package to improve the performance of the software and facilitate the project planners. One example is analysed to illustrate the iteration process of the proposed FBHA. Another example with multiple precedence constraints is used to demonstrate the effectiveness of the proposed FBHA in complicated construction projects.     

求解CPM网络计划的最大网络时差

CPM网络计划的网络时差表示项目中各工序实际可使用的机动时间的总和(绝非理论上机动时间的简单加总),即CPM网络计划的总机动时间,它决定着在总工期不变的前提下,所有工序实际可以达到的最大工期的总和,与项目的成本管理和时间管理密切相关。网络时差是变量,取决于各工序的时间进度安排,说明可以通过调整工序的时间进度来决定该时差的取值,特别是其最大值,进而实现成本和时间优化。本文首先从新的角度分析了网络时差的含义;然后,在此基础上设计了求解最大网络时差的算法,其思路为,通过建立和分析最大网络时差模型,将其转化为特殊的“时间-费用权衡问题”,进而可运用Fulkerson算法等经典算法求解;最后,通过应用举例对该算法进行了演示。     

Using Schedule Risk Analysis with resource constraints for project control

Schedule Risk Analysis (SRA) has shown to provide reliable activity sensitivity information for taking corrective actions during project control. More precisely, by selecting a small subset of activities with high sensitivity values for taking corrective actions, the project outcome can be improved. In resource constrained projects, disrupted activities can affect both their successors as well as other activities when resource conflicts are induced. Since SRA focuses solely on the project network to determine the sensitivity of activities, the traditional SRA metrics do not accurately reflect the activity sensitivity for resource constrained projects. In this paper, the traditional SRA metrics are extended for resource constrained projects, and a novel resource-based sensitivity metric is introduced (RC-SRA metrics).A computational experiment is conducted to investigate the ability of the RC-SRA metrics to identify activities with higher sensitivity values. In addition, two activity selection strategies, defined as the normal strategy and sequential strategy, are designed to select activities for taking corrective actions. Further, two types of corrective actions are proposed to reduce the activity duration or resource demand in case of delays, respectively. Finally, the impact of dynamically updating the RC-SRA metrics during project execution is examined.The computational results show that the normal activity selection strategy is recommended for serial projects, while the sequential strategy is preferred for parallel projects. The results also indicate that reducing the activity durations performs better than reducing the resource demand of activities. Finally, it is shown that updating the RC-SRA metrics dynamically during project execution improves the efficiency of the corrective action taking process.     

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.     

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.     

可抢占条件下的项目调度研究综述

可抢占条件下的项目调度通过暂时中断某些活动的执行,释放资源给更重要的活动,从而优化项目的工期、成本等绩效指标。可抢占项目调度问题以其重要的理论价值和应用背景,受到了学界和业界的广泛关注。对国内外可抢占项目调度的研究成果进行了系统性总结与梳理,综述了可抢占项目调度问题的数学模型及其求解算法,总结了可抢占项目调度问题的一些扩展问题和应用情况,最后指出了未来进一步的研究方向。     

A new approach for quantitative risk analysis

Project risk management aims to provide insight into the risk profile of a project as to facilitate decision makers to mitigate the impact of risks on project objectives such as budget and time. A popular approach to determine where to focus mitigation efforts, is the use of so-called ranking indices (e.g., the criticality index, the significance index etc.). Ranking indices allow the ranking of project activities (or risks) based on the impact they have on project objectives. A distinction needs to be made between activity-based ranking indices (those that rank activities) and risk-driven ranking indices (those that rank risks). Because different ranking indices result in different rankings of activities and risks, one might wonder which ranking index is best. In this article, we provide an answer to this question. Our contribution is threefold: (1) we set up a large computational experiment to assess the efficiency of ranking indices in the mitigation of risks, (2) we develop two new ranking indices that outperform existing ranking indices and (3) we show that a risk-driven approach is more effective than an activity-based approach.     

Two Approaches to Problems of Resource Allocation Among Project Activities — A Comparative Study

The paper deals with a class of problems of resource allocation among project activities, where the resource requirements of each activity concern numbers of resource units from given finite sets for particular resource types. Three categories of constrained resources are considered in a general model: renewable (only total usage at every moment is constrained), non-renewable (only total consumption over the period of project duration is constrained) and doubly-constrained (both usage and consumption are constrained). For every feasible combination of resource amounts, the performing time of each activity is known. Time and cost criteria are considered for project performance evaluation. For solving these problems, two general approaches using linear programming in specific ways are described. These approaches are different in nature, the difference being reflected in the range of problems solved by them and in their computational properties. This is shown by an extensive comparison of both approaches. This comparison also characterizes the state-of-the-art across the problems and points out desirable directions for further research.     

Multi-mode resource constrained multi-project scheduling and resource portfolio problem

This paper introduces a multi-project problem environment which involves multiple projects with assigned due dates; activities that have alternative resource usage modes; a resource dedication policy that does not allow sharing of resources among projects throughout the planning horizon; and a total budget. Three issues arise when investigating this multi-project environment. First, the total budget should be distributed among different resource types to determine the general resource capacities, which correspond to the total amount for each renewable resource to be dedicated to the projects. With the general resource capacities at hand, the next issue is to determine the amounts of resources to be dedicated to the individual projects. The dedication of resources reduces the scheduling of the projects’ activities to a multi-mode resource constrained project scheduling problem (MRCPSP) for each individual project. Finally, the last issue is the efficient solution of the resulting MRCPSPs. In this paper, this multi-project environment is modeled in an integrated fashion and designated as the resource portfolio problem. A two-phase and a monolithic genetic algorithm are proposed as two solution approaches, each of which employs a new improvement move designated as the combinatorial auction for resource portfolio and the combinatorial auction for resource dedication. A computational study using test problems demonstrated the effectiveness of the solution approach proposed.     

Cost impact of float loss on a project with adjustable activity durations

Although delays to non-critical activities within the float do not always affect the overall completion time of a project, they commonly cause disputes over the impact cost and apportionment resulting from the complexity of resource utilization in construction projects. Therefore, considerable attention has been focused on providing an effective and reliable method for analysing the effects of float loss. Several recent studies have proposed various methods; however, most of these methods are based on the assumption of a fixed duration for each activity or activity-based cost simulation. Few studies have considered the trade-off between time and costs and the integration of project resources. Using genetic algorithms, this study introduces a critical path method (CPM)-modified resource-integrated optimization model and successfully quantifies the impact of float loss on the total cost of the project. The results provide objective quantification for accurately evaluating the impact of within-float delays and facilitate the analysis of the impact of delay claims on cost and apportionment in construction projects.     

Heuristics for multimode scheduling problems with dedicated resources

We study scheduling problems with multiple modes and dedicated resources arising in production and project management, which constitute a special class of the general multimode resource-constrained project scheduling problem. A task may require simultaneously a set of discrete, renewable resources to be processed and the processing can be performed in different modes, that is with different resource sets, processing times, or costs. Precedence constraints can exist among tasks. The total budget that can be allocated to the project can be limited. The problem consists of identifying a mode for each task and a starting time for its processing respecting precedence, resource, and budget constraints. A graph model and an iterative solution scheme are presented. Specific heuristic algorithms for the cases with and without budget constraints are given and computational results are discussed.     

A new approach to find project characteristics and multiple possible critical paths in a fuzzy project network

Graphs are widely used to represent data and relationships. Among all graphs, a particularly useful family is the family of trees. In this paper, we utilize a rooted tree to describe a fuzzy project network as it enables simplification in finding earliest starting times and trapezoidal fuzzy numbers to express the operation times for all activities in project network. As there is an increasing demand that the decision maker needs “Multiple possible critical paths” to decrease the decision risk for project management, in this paper, we introduce an effective graphical method to compute project characteristics such as total float, earliest and latest times of activities in fuzzy project network and a new ranking to find possible critical paths. Numerical example is provided to explain the proposed procedure in detail; the results have shown that the procedure is very useful and flexible in finding total floats. By comparing the critical paths obtained by this method with the previous methods, it is shown that the proposed method is effective in finding possible critical paths.     

On the complexity of project scheduling to minimize exposed time

We consider project scheduling where the project manager’s objective is to minimize the time from when an adversary discovers the project until the completion of the project. We analyze the complexity of the problem identifying both polynomially solvable and NP-hard versions of the problem. The complexity of the problem is seen to be dependent on the nature of renewable resource constraints, precedence constraints, and the ability to crash activities in the project.     

Using resource scarceness characteristics to solve the multi-mode resource-constrained project scheduling problem

In the past decades, resource parameters have been introduced in project scheduling literature to measure the scarceness of resources of a project instance. In this paper, we incorporate these resource scarceness parameters in the search process to solve the multi-mode resource constrained project scheduling problem, in which multiple execution modes are available for each activity in the project. Therefore, we propose a scatter search algorithm, which is executed with different improvement methods, each tailored to the specific characteristics of different renewable and nonrenewable resource scarceness values. Computational results prove the effectiveness of the improvement methods and reveal that the procedure is among the best performing competitive algorithms in the open literature.