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

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

Criticality in Resource Constrained Networks

Project managers readily adopted the concept of the critical path as an aid to identifying those activities most worthy of their attention and possible action. However, current project management packages do not offer a useful measure of criticality in resource constrained projects. A revised method of calculating resource constrained float is presented, together with a discussion of its use in project management. While resource constrained criticality appears to be a practical and useful tool in the analysis of project networks, care is needed in its interpretation as any calculation of such float is conditional on the particular resource allocation employed. A number of other measures of an activity's importance in a network are described and compared in an application to an aircraft development. A quantitative comparison of the measures is developed based on a simulation of the process of management identifying the key activities and directing their control efforts. Resource constrained float appears to be a useful single measure of an activity's importance, encapsulating several useful pieces of management information. However, there are some circumstances in which other measures might be preferred.     

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 note on activity floats in activity-on-arrow networks

In project scheduling, the free float (slack) of an activity represents the leeway for scheduling the activity without affecting any subsequent activity. In the context of activity-on-arrow (AOA) network representation, textbooks on project management, based on our survey, have for decades been using a popular formula to calculate free floats that may lead to erroneous results in the presence of dummy arcs. In this note, we present a correct version of the formula. Extensions of the proposed formula to other floats such as safety float and interference float are also discussed.     

On the measurement of complexity in activity networks

The measurement of the ‘complexity’ of activity networks seems to be needed in order to estimate the computing requirements and/or to validly compare alternative heuristic procedures. This paper critically evaluates past contributions to the problem, and explores the underlying concepts of measurement. It suggests that the objective of analysis of the network is a determining factor in the process of measurement, and discusses three different objectives; they are: to determine the critical path assuming deterministic time estimates; to determine the probability distribution function of project completion assuming random durations of the activities; and to determine the optimal schedule under limited availability of a single resource. It proposes the form of the measure of network complexity for each objective, and explicitly exhibits the form of the measure relative to the first objective based on a sample of 104 networks.     

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.     

A simulated annealing algorithm for resource constrained project scheduling problems

This paper presents a simulated annealing algorithm for resource constrained project scheduling problems with the objective of minimising makespan. In the search algorithm, a solution is represented with a priority list, a vector of numbers each of which denotes the priority of each activity. In the algorithm, a priority scheduling method is used for making a complete schedule from a given priority list (and hence a project schedule is defined by a priority list). The search algorithm is applied to find a priority list which corresponds to a good project schedule. Unlike most of priority scheduling methods, in the suggested algorithm some activities are delayed on purpose so as to extend search space. Solutions can be further improved by delaying certain activities, since non-delay schedules are not dominant in the problem (the set of non-delay schedules does not always include an optimal solution). The suggested algorithm is flexible in that it can be easily applied to problems with an objective function of a general form and/or complex constraints. The performance of the simulated annealing algorithm is compared with existing heuristics on problems prepared by Patterson and randomly generated test problems. Computational results showed that the suggested algorithm outperformed existing ones.     

基于时差分析的时标网络图探究

鉴于已有时差概念并不能充分反映CPM网络紧前和紧后工序时差的内在联系，文中引入三个新时差（前共后单时差，前单后共时差，双共时差）概念。针对目前工程项目管理中通用的时标网络图一早时标网络图和迟时标网络图，在路长定理的基础上，给出其理论依据，并在时差分析的基础上，随机绘出时标网络图，三个新时差的引入将有助于今后时标网络图的绘制，使网络技术的应用更具灵活性和实用性。     

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.     

一种求解柔性资源约束前摄性项目调度问题的启发式算法

在不确定环境中,一个具有较高鲁棒性的进度计划可以保证项目的稳定实施。考虑到现实中资源可能具有多种技能,会对制定鲁棒性较高进度计划的过程产生影响,因此本文研究了柔性资源约束下前摄性项目调度优化问题。首先界定研究问题;然后从鲁棒性最大化的视角出发,构建了研究问题的优化模型,在对模型进行分析的基础上将其分解为经典鲁棒优化和资源技能分配两个子模型;随后设计了求解问题的基于削峰算法的启发式算法;最后用一个实际案例验证了算法有效性,并分析了关键参数对进度计划鲁棒性的影响,得到如下结论:项目进度计划鲁棒性随着项目工期的延长、资源可用量的增加或资源柔性的提高而增大。     

Identification and illumination of popular misconceptions about project scheduling and time buffering in a resource-constrained environment

The lack of proper project planning is often cited as one of the main reasons why projects fail to be completed in time and within budget. In this paper, we identify and illuminate several possible misconceptions that go round in project management periodicals and in the mindset of practising project managers and that may hamper successful project planning. The misconceptions relate to the role of the critical path, the critical sequence (critical chain), active schedules, and the insertion of buffers in the baseline schedule as a protective mechanism against schedule distortions during project execution. The possible fallacies are illustrated using example schedules developed for an illustrative project.     

Production scheduling with alternative process plans

This paper deals with a scheduling problem with alternative process plans that was motivated by a production of wire harnesses where certain parts can be processed manually or automatically by different types of machines. Only a subset of all the given activities will form the solution, so the decision whether the activity will appear in the final schedule has to be made during the scheduling process. The problem considered is an extension of the resource constrained project scheduling problem (RCPSP) with unary resources, positive and negative time-lags and sequence dependent setup times. We extend classic RCPSP problem by a definition of alternative branchings, represented by the Petri nets formalism allowing one to define alternatives and parallelism within one data structure. For this representation of the problem, an integer linear programming model is formulated and the reduction of the problem, using time symmetry mapping, is shown. Finally, a heuristic algorithm based on priority schedule construction with an unscheduling step is proposed for the nested version of the problem and it is used to solve the case study of the wire harnesses production.     

A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling

We develop a heuristic procedure for solving the discrete time/resource trade-off problem in the field of project scheduling. In this problem, a project contains activities interrelated by finish-start-type precedence constraints with a time lag of zero, which require one or more constrained renewable resources. Each activity has a specified work content and can be performed in different modes, i.e. with different durations and resource requirements, as long as the required work content is met. The objective is to schedule each activity in one of its modes in order to minimize the project makespan. We use a scatter search algorithm to tackle this problem, using path relinking methodology as a solution combination method. Computational results on randomly generated problem sets are compared with the best available results indicating the efficiency of the proposed algorithm.     

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.     

柔性工期下的资源受限项目调度双目标优化研究

在项目调度过程中,活动工期应根据项目截止工期以及资源供给情况进行合理设置,而在传统的资源受限项目调度问题(RCPSP)中,活动的工期往往是已知且固定的,这在一定程度上限制了项目调度的灵活性。多模式下的项目调度方式虽然弥补了这一缺点,但其提供的工期-资源组合种类固定且有限,并不一定能保证包含最优的工期-资源组合。本文将活动工期作为项目调度问题的决策变量,允许其在一定范围内取值。这种柔性工期调度方式虽然增加了项目调度难度,但提高了项目调度灵活性,同时可以起到压缩项目完工时间的作用。为验证柔性工期调度方式对项目工期和成本的影响,本文建立了工期-成本双目标权衡优化模型,设计了两阶段嵌套算法(NSGAⅡ-RS)对其求解,实验证明,柔性工期调度策略是一种鲁棒性较好的项目完工时间压缩策略。     

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.     

On the optimal management of project risk

The uncertainty of project networks has been mainly considered as the randomness of duration of the activities. However, another major problem for project managers is the uncertainty due to the randomness of the amount of resources required by each activity which can be expressed by the randomness of its cost. Such randomness can seriously affect the discounted cost of the project and it may be strongly correlated with the duration of the activity.In this paper, a model considering the randomness of both the cost and the duration of each activity is introduced and the problem of project scheduling is studied in terms of the project's discounted cost and of the risk of not meeting its completion time. The adoption of the earliest (latest) starting time for each activity decreases (increases) the risk of delays but increases (decreases) the discounted cost of the project. Therefore, an optimal compromise has to be achieved. This problem of optimization is studied in terms of the probability of the duration and of the discounted cost of the project falling outside the acceptable domain (Risk function) using the concept of float factor as major decision variable. This last concept is proposed to help the manager to synthetize the large number of the decision variables representing each schedule for the studied project. Numerical results are also presented for a specific project network.     

Linear programming based algorithms for preemptive and non-preemptive RCPSP

In this paper, the RCPSP (resource constrained project scheduling problem) is solved using a linear programming model. Each activity may or may not be preemptive. Each variable is associated to a subset of independent activities (antichains). The properties of the model are first investigated. In particular, conditions are given that allow a solution of the linear program to be a feasible schedule. From these properties, an algorithm based on neighbourhood search is derived. One neighbour solution is obtained through one Simplex pivoting, if this pivoting preserves feasibility. Methods to get out of local minima are provided. The solving methods are tested on the PSPLIB instances in a preemptive setting and prove efficient. They are used when preemption is forbidden with less success, and this difference is discussed.     

Spatial Environment in Comprehensive Schools

This paper describes a mechanism for aiding the designer in generating an efficient and flexible provision of teaching space to match the complex and varying needs in comprehensive schools. The mechanism is a computer program package which comprises three parts: SECS A which outputs schedules of accommodation for any given set of group activity data: SECS B which appraises any existing schedule of accommodation in relation to the minimum; and SES C which identifies the minimum physical flexibility necessary to achieve any set of alternative future accommodation schedules.     

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.