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.     

基于活动延期风险加权时差的资源受限项目调度鲁棒性度量

在项目调度鲁棒性研究中,当活动出现延期风险时,由于各活动性质不同,其延期风险权重也不同,权重越大的活动越有可能影响项目的完工时间。针对资源受限项目调度问题,提出一个基于活动延期风险加权时差的鲁棒性度量新指标。在出现不确定因素干扰时,该指标不仅考虑了活动延期风险权重的影响,同时为实现时差在多个任务之间的共享,还考虑了紧前任务数量的影响。建立一个以加权时差最大化为目标的资源受限项目调度鲁棒优化模型,并针对模型特点,设计了基于禁忌搜索的模拟退火算法。最后,通过算例验证了该度量方式和算法的合理性和有效性,对比分析结果表明所提出的指标优于现有的度量指标,较好地满足了项目调度质量鲁棒性的要求。     

A survey of variants and extensions of the resource-constrained project scheduling problem

The resource-constrained project scheduling problem (RCPSP) consists of activities that must be scheduled subject to precedence and resource constraints such that the makespan is minimized. It has become a well-known standard problem in the context of project scheduling which has attracted numerous researchers who developed both exact and heuristic scheduling procedures. However, it is a rather basic model with assumptions that are too restrictive for many practical applications. Consequently, various extensions of the basic RCPSP have been developed. This paper gives an overview over these extensions. The extensions are classified according to the structure of the RCPSP. We summarize generalizations of the activity concept, of the precedence relations and of the resource constraints. Alternative objectives and approaches for scheduling multiple projects are discussed as well. In addition to popular variants and extensions such as multiple modes, minimal and maximal time lags, and net present value-based objectives, the paper also provides a survey of many less known concepts.     

Using revenue management to improve pricing and capacity management in programme management

This paper presents revenue management models for pricing, capacity planning, and capacity reallocation and demonstrates their applicability for programme (project) management. In programme management, the allocation of capacity (resource time) to schedule activities requires the resolution of time versus revenue trade-offs. Thus, capacity planning and scheduling present a hierarchical problem for programme managers. Furthermore, current programme management methods do not consider the issue of price sensitivity exhibited in many programme management situations. Because of this omission, critical linkages between capacity management and scheduling of activities among programmes have not been addressed. Specifically, the issue of the reservation of capacity specifically for higher revenue generating activities has been omitted from programme management research. This paper asserts that, through capacity planning and scheduling, specific capacity should be reserved for customers willing to pay higher prices to have critical activities, for example, change orders, expedited. This capacity has scheduling effects that impact the programme NPV. This paper proposes potential solutions to capacity and programme scheduling problems using revenue management techniques.     

New fuzzy models for time-cost trade-off problem

The time-cost trade-off problem is a specific type of the project scheduling problem which studies how to modify project activities so as to achieve the trade-off between the completion time and the project cost. In real projects, the trade-off between the project cost and the completion time, and the uncertainty of the environment are both considerable aspects for managers. In this paper, three new fuzzy time-cost trade-off models are proposed, in which credibility theory is applied to describe the uncertainty of activity duration times. A searching method by integrating fuzzy simulation and genetic algorithm is produced to search the quasi-optimal schedules under some decision-making criteria. The purpose of the paper is to reveal how to obtain the optimal balance of the completion time and the project cost in fuzzy environments.     

Time and work generalised precedence relationships in project scheduling with pre-emption: An application to the management of Service Centres

In this paper we present an application of project scheduling concepts and solution procedures for the solution of a complex problem that comes up in the daily management of many company Service Centres. The real problem has been modelled as a multi-mode resource-constrained project scheduling problem with pre-emption, time and work generalised precedence relationships with minimal and maximal time lags between the tasks and due dates. We present a complete study of work GPRs which includes proper definitions, a new notation and all possible conversions amongst them. Computational results that show the efficiency of the proposed hybrid genetic algorithm and the advantages of allowing pre-emption are also presented.     

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

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

Active and stable project scheduling

The paper proposes a new classification of schedules for resource-constrained project scheduling problems with minimum and maximum time lags between project activities and regular and different types of nonregular objective functions. The feasible region of the scheduling problems represents a (generally disconnected) union of polytopes. In addition to the well-known concepts of active and semiactive schedules, pseudoactive and quasiactive as well as stable, semistable, pseudostable, and quasistable schedules are introduced. The (quasi-, pseudo-, semi-)active schedules are related to different types of left-shifts of sets of activities and correspond to minimal points of certain subsets of the feasible region. The (quasi-, pseudo-, semi-)stable schedules do not allow oppositely directed shifts and correspond to extreme points of certain subsets of the feasible region. The different sets of schedules contain optimal schedules for project scheduling problems which differ in their objective functions. The correspondence between those sets of schedules and vertices of specific polyhedral subsets of the feasible region can be exploited for analyzing schedule generation schemes which have been developed recently for finding solutions to the different classes of project scheduling problems.     

A new heuristic for resource-constrained project scheduling in stochastic networks using critical chain concept

This paper presents a newly developed resource-constrained project scheduling method in stochastic networks by merging the new and traditional resource management methods. In each project, the activities consume various types of resources with fixed capacities. The duration of each activity is a random variable with a given density function. Since the backward pass method is implemented for feeding-in resources. The problem is to determine the finish time of each activity instead of its start time. The objective of the presented model is defined as minimizing the multiplication of expected project duration and its variance. The values of activities finish times are determined at decision points when at least one activity is ready to be operated and there are available resources. If at a certain point of time, more than one activity is ready to be operated but available resources are lacking, a competition among ready activities is carried out in order to select the activities which must be operated first. This paper suggests a competition routine by implementing a policy to maximize the total contribution of selected activities in reducing the expected project duration and its variance. In this respect, a heuristic algorithm is developed and compared with the other existing methods.     

Railway scheduling reduces the expected project makespan over roadrunner scheduling in a multi-mode project scheduling environment

The Critical Chain Scheduling and Buffer Management (CC/BM) methodology, proposed by Goldratt (Critical chain, 1997), introduced the concepts of feeding buffers, project buffers and resource buffers as well as the roadrunner mentality. This last concept, in which activities are started as soon as possible, was introduced in order to speed up projects by taking advantage of predecessors finishing early. Later on, the railway scheduling concept of never starting activities earlier than planned was introduced as a way to increase the stability of the project, typically at the cost of an increase in the expected project makespan. In this paper, we will indicate a realistic situation in which railway scheduling improves both the stability and the expected project makespan over roadrunner scheduling.     

广义优先关系约束下Max-npv项目调度问题及其遗传算法

以往Max-npv项目调度问题的研究都假定活动之间的关系为单一结束-开始类型,现实中活动之间关系复杂多变,因此,将广义优先关系引入Max-npv项目调度问题中,构建了广义优先关系约束下的Max-npv项目调度模型。针对该优化模型设计了一种双层遗传算法,外层遗传算法负责任务执行模式的优化,内层遗传算法负责任务调度的优化。在内层遗传算法中,采用任务开始时间之差作为新的编码方式,大大简化了交叉变异算子,针对网络图中的环状结构设计了修复算子,确保了编码的有效性。通过一个算例对算法进行了测试,实验结果验证了算法的有效性。     

A multicriteria decision model for assigning priority classes to activities in project management

Problems related to the management of construction projects are addressed in many studies. Falling behind schedule and being over budget are examples of bad results, due to the uncertainties and the dynamic environment of the construction process. This study proposes a decision model for helping project managers to focus on the main tasks of a project network during the life cycle of a project based on a MCDA (multiple criteria decision analysis) method. The model assigns priorities classes to activities in project management, taking into account several points of view. The model is based on the ELECTRE TRI-C method, which permits activities to be assigned to categories. As the environment is very dynamic, the model was built taking into consideration changes that may occur while a project is being carried out, and therefore the model must be reassessed during the project life cycle. Furthermore, the model supports a decision making environment where responsibilities are distributed amongst project team members and it brings the benefit of developing disciplines that lead to the team??s greater effectiveness. An application of the model, based on a realistic situation, is presented in the context of a construction project in order to demonstrate the use of the model. The results show that by using the model, managers can improve their performance with regard to controlling project activities.     

MARKOV SKELETON PROCESS IN PERT NETWORKS

In this article, we investigate Programming Evaluation and Review Technique networks with independently and generally distributed activity durations. For any path in this network, we select all the activities related to this path such that the completion time of the sub-network （only consisting of all the related activities） is equal to the completion time of this path. We use the elapsed time as the supplementary variables and model this sub-network as a Markov skeleton process, the state space is related to the subnetwork structure. Then use the backward equation to compute the distribution of the sub-network＇s completion time, which is an important rule in project management and scheduling.     

Controlling a Production Scheduling System

When using an automatic production scheduling system management require the system to respond to different overall policies, such as clear all arrears or minimize average lateness weighted by job importance. In many commercial scheduling packages there is no quantitative explanation of how to achieve this response. A successfully implemented scheduling system is introduced here where each policy or objective is obtained by selecting the appropriate criterion on which to sort the jobs. An analytical relationship between the policy and the sorting criterion is established. A new type of lateness penalty is developed heuristically, which is basically an exponential function. The sorting criterion to minimise this lateness penalty turns out to be simply sorting by least slack.     

Branch-and-price approach for the multi-skill project scheduling problem

This work introduces a procedure to solve the multi-skill project scheduling problem (MSPSP) (Néron and Baptista, International symposium on combinatorial, optimization (CO’2002), 2002). The MSPSP mixes both the classical resource constrained project scheduling problem and the multi-purpose machine model. The aim is to find a schedule that minimizes the completion time (makespan) of a project, composed of a set of activities. In addition, precedence relations and resources constraints are considered. In this problem, resources are staff members that master several skills. Thus, a given number of workers must be assigned to perform each skill required by an activity. Practical applications include the construction of buildings, as well as production and software development planning. We present a column generation approach embedded within a branch-and-price (B&P) procedure that considers a given activity and time-based decomposition approach. Obtained results show that the proposed B&P procedure is able to reach optimal solutions for several small and medium sized instances in an acceptable computational time. Furthermore, some previously open instances were optimally solved.     

A model to optimize project resource allocation by construction of a balanced histogram

This paper examines a scheduling method to improve productivity in resource-constrained projects. When resources are nonrenewable the duration of each activity has only one value. Optimal solutions are derived through criticalism of groups of activities using the same resource so as to eliminate interruption times and associated costs. The corresponding resource histogram is balanced and its design is derived by means of a program suitable for personal computer implementation.In the case where resources are renewable, activity durations are resource driven. We introduce a new view of discreetness for activity execution times which enables us to obtain optimal solutions relating to the cost functions of the activities.Finally we account for doubly constrained resources by (a) defining a maximum level of resource utilization and a maximum cost increase per period of usage of renewable resources and (b) considering as acceptable only those optimal solutions which keep total cost increase for the overall project below a tolerable limit.An application example is given using personal computer and commercially available software.     

Solving project scheduling problem with the philosophy of fuzzy random programming

Project scheduling problem is to determine the schedule of allocating resources to achieve the trade-off between the project cost and the completion time. In real projects, the trade-off between the project cost and the completion time, and the uncertainty of the environment are both considerable aspects for managers. Due to the complex external environment, this paper considers project scheduling problem with coexisted uncertainty of randomness and fuzziness, in which the philosophy of fuzzy random programming is introduced. Based on different ranking criteria of fuzzy random variables, three types of fuzzy random models are built. Besides, a searching approach by integrating fuzzy random simulations and genetic algorithm is designed for searching the optimal schedules. The goal of the paper is to provide a new method for solving project scheduling problem in hybrid uncertain environments.     

Markov skeleton process in PERT networks

In this article, we investigate Programming Evaluation and Review Technique networks with independently and generally distributed activity durations. For any path in this network, we select all the activities related to this path such that the completion time of the sub-network (only consisting of all the related activities) is equal to the completion time of this path. We use the elapsed time as the supplementary variables and model this sub-network as a Markov skeleton process, the state space is related to the sub-network structure. Then use the backward equation to compute the distribution of the sub-network's completion time, which is an important rule in project management and scheduling.     

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.