Resource-constrained project scheduling with concave processing rate functions

In this paper, we address a resource-constrained project scheduling problem involving a single resource. The resource can be applied at varying consumption rates to the activities of the project. The duration of each activity is defined by a convex, non-increasing time-resource trade-off function. In addition, activities are not preemptable (ie, the resource consumption rate of an activity cannot be altered while the activity is being processed). We explicitly consider variation of the rate at which an activity is performed with variation in resource consumption rate. We designate the number of units (amount of an activity) performed per unit time with variation in resource consumption rate as the processing rate function, and assume this function to be concave. We present a tree-search-based method in concert with the solution of a nonlinear program and the use of dominance properties to determine: (i) the sequence in which to perform the activities of the project, and (ii) the resource consumption rate to allocate to each activity so as to minimize the project duration (makespan). We also present results of an experimental investigation that reveal the efficacy of the proposed methodology. Finally, we present an application of this methodology to a practical setting.     

LOB中基于工期决定因素分析的资源均衡算法研究

资源均衡是重复性项目中的经典调度问题,本文提出一种新的基于平衡线法(line of balance,LOB)的资源均衡方法。首先,本文提出LOB中关键路线的确定方法,确定关键路线及关键工序类型。而后,本文分析项目总工期的决定因素,对不同类型关键工序的特性及其与总工期、资源调整之间的关系进行了研究,论证了在LOB的资源均衡问题中,由于逆关键工序、点关键工序这些特殊工序的存在,可以在保证项目总工期不变的前提下,通过同时调整关键工序和非关键工序实现资源优化。按照这一思路,论文设计了LOB中资源均衡的遗传算法。算例分析表明该资源均衡算法的优化性能。本文提出的资源均衡思路和算法能帮助项目计划人员拓展资源优化空间,达到更好的资源均衡效果。     

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.     

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.     

Product development resource allocation with foresight

Shortening project duration is critical to product development project success in many industries. As a primary driver of progress and an effective management tool, resource allocation among development activities can strongly influence project duration. Effective allocation is difficult due to the inherent closed loop flow of development work and the dynamic demand patterns of work backlogs. The Resource Allocation Policy Matrix is proposed as a means of describing resource allocation policies in dynamic systems. Simple system dynamics and control theoretic models of resource allocation in a product development context are developed. The control theory model is used to specify a foresighted policy, which is tested with the system dynamics model. The benefits of foresight are found to reduce with increasing complexity. Process concurrence is found to potentially reverse the impact of foresight on project duration. The model structure is used to explain these results and future research topics are discussed.     

A framework for an interactive project scheduling system under limited resources

In this paper, we propose a framework for an interactive project scheduling system under limited resources. The framework includes a modelling module (model) and a scheduling module (scheduler). The modelling module model allows the Decision Maker (DM) to develop his/her own model with features such as alternative operating modes for activities; renewable, nonrenewable and/or doubly-constrained resource constraints; general cash flow patterns, related to the realization of activities or events; and progress payments distributed over the project span. The performance criteria include the maximization of Net Present Value (NPV), and either the minimization of maximum tardiness (when a project due date exists) or the minimization of the project duration (when there is no project due date). The scheduler is developed on a constraint-based scheduling algorithm, which is called Local Constraint Based Analysis (lcba) and which has previously been tested and shown to produce near-optimal results with respect to the criterion of minimizing project duration. The decisions taken in the scheduler consist of determining the start times of activities and the specific operating modes in which they are to be realized. The decisions are taken by activating relevant essential conditions in lcba and in cases where resource conflicts are not resolved, the DM reaches a final decision by testing the alternatives proposed by lcba through a what-if routine. The scheduler represents a realistic scheduling system which is useful not only in the planning phase of a project but can also be employed during the progress of a project for updating the project plan, if necessary. An important feature is that the project plan can be updated by performing the least modification of future commitments. It is possible to freeze the activities already scheduled in the near future while admitting the changes in the activity/network information.     

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.     

Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting

This paper presents results from an extensive computational study of the multi-mode resource-constrained project scheduling problem when activities can be split during scheduling under situations where resources may be temporarily not available. All resources considered are renewable and each resource unit may not be available at all times due to resource vacations, which are known in advance, and assignment to other finite duration activities. A designed experiment is conducted that investigates project makespan improvement when activity splitting is permitted in various project scenarios, where different project scenarios are defined by parameters that have been used in the research literature. A branch-and-bound procedure is applied to solve a number of small project scheduling problems with and without activity splitting. The results show that, in the presence of resource vacations and temporary resource unavailability, activity splitting can significantly improve the optimal project makespan in many scenarios, and that the makespan improvement is primarily dependent on those parameters that impact resource utilization.     

Multiple-Project Scheduling with Controllable Project Duration and Hard Resource Constraint: Some Solvable Cases

In many large-scale project scheduling problems, multiple projects are either taking place at the same time or scheduled into a tight sequence in order to efficiently share a common resource. One example of this is the computing resource allocation at an Application Service Provider (ASP) which provides data processing services for multiple paying customers. Typical services provided by ASPs are data mining, payroll processing, internet-based storage backup services and Customer Relation Management (CRM) services. The processing mode of an ASP can be either batch or concurrent, depending on the type service rendered. For example, for CPU intensive or long processing time required services, it would be more economical to processes one customer request at a time in order to minimize the context switching overhead. While the data transaction processes within a service request are subject to certain precedence relationships, the requests from different customers to an ASP are independent of each other, and the total time required to process a service request depends on the computing resource allocated to that request. The related issue of achieving an optimal use of resources at ASPs leads to problem of project scheduling with controllable project duration.In this paper, we present efficient algorithms for solving several special cases of such multi-project scheduling problems with controllable project duration and hard resource constraints. Two types of problems are considered. In type I, the duration of each project includes a constant and a term that is inversely proportional to the amount of resource allocated. In type II, the duration of each individual project is a continuous decreasing function of the amount of resource allocated.     

Proactive policies for the stochastic resource-constrained project scheduling problem

The resource-constrained project scheduling problem involves the determination of a schedule of the project activities, satisfying the precedence and resource constraints while minimizing the project duration. In practice, activity durations may be subject to variability. We propose a stochastic methodology for the determination of a project execution policy and a vector of predictive activity starting times with the objective of minimizing a cost function that consists of the weighted expected activity starting time deviations and the penalties or bonuses associated with late or early project completion. In a computational experiment, we show that our procedure greatly outperforms existing algorithms described in the literature.     

A priority-rule method for project scheduling with work-content constraints

The activities of a project are in general characterized by a work content in terms of resource–time units, e.g. person-days. Even though most project scheduling models assume a time-invariant resource usage, normally it is possible to vary the resource usage during the execution of an activity. Typically, a lower and an upper bound on this resource usage and a minimum time lag between consecutive changes of this resource usage are prescribed. The project scheduling problem studied in this paper consists in determining a feasible resource-usage profile for each activity such that the project duration is minimized subject to precedence and resource-capacity constraints. While the known solution methods interpret the prescribed work content as a lower bound, we assume that each activity’s work content must be processed exactly.     

A management oriented approach to reduce a project duration and its risk (variability)

The effects of different activities on risk and the expected completion time of a project are not the same; various activities have various effects on the successful completion of a project. Based on this fact, one of the most important issues in project management is to determine important activities and the amount of effort that should be assigned to control them, thereby completing the project successfully. In this paper, one index and one method are proposed to satisfy this necessity. Our main hypothesis is, expending effort on activities and controlling them actively results in activities risk reduction. Based on this hypothesis, the proposed index and method are compared to existing indices in the literature. Comparison results show that the proposed index and method strongly surpass other indices.     

基于工期-成本综合效用最大的关键链项目缓冲确定

为提高关键链中工期和成本的综合效用,研究一种基于关键链工期和成本进行双目标优化的缓冲确定方法。首先,该方法考虑项目不同工序间工期和成本之间的关系,并基于工期和成本的风险暴露度确定权重,解决不同工序间工期和成本偏好难以量化的问题;其次,根据权重多效用函数对工期和成本进行归一化处理,并确定综合效用最大情况下不同工序的最佳工期;最后基于尾部集中法确定项目缓冲。通过蒙特卡洛模拟实验,将此方法提取缓冲后的项目实际综合效用与传统方法进行比较。比较结果显示,该方法极大地提高项目中工期和成本的综合效用,并且对项目工期和成本均形成更有效的保护。     

An optimization approach to adaptive multi-dimensional capital management

Firms should keep capital to offer sufficient protection against the risks they are facing. In the insurance context methods have been developed to determine the minimum capital level required, but less so in the context of firms with multiple business lines including allocation. The individual capital reserve of each line can be represented by means of classical models, such as the conventional Cramér–Lundberg model, but the challenge lies in soundly modelling the correlations between the business lines. We propose a simple yet versatile approach that allows for dependence by introducing a common environmental factor. We present a novel Bayesian approach to calibrate the latent environmental state distribution based on observations concerning the claim processes. The calibration approach is adjusted for an environmental factor that changes over time. The convergence of the calibration procedure towards the true environmental state is deduced. We then point out how to determine the optimal initial capital of the different business lines under specific constraints on the ruin probability of subsets of business lines. Upon combining the above findings, we have developed an easy-to-implement approach to capital risk management in a multi-dimensional insurance risk model.     

Comparison of the Bayesian and Randomised Decision Tree Ensembles within an Uncertainty Envelope Technique

Multiple Classifier Systems (MCSs) allow evaluation of the uncertainty of classification outcomes that is of crucial importance for safety critical applications. The uncertainty of classification is determined by a trade-off between the amount of data available for training, the classifier diversity and the required performance. The interpretability of MCSs can also give useful information for experts responsible for making reliable classifications. For this reason Decision Trees (DTs) seem to be attractive classification models for experts. The required diversity of MCSs exploiting such classification models can be achieved by using two techniques, the Bayesian model averaging and the randomised DT ensemble. Both techniques have revealed promising results when applied to real-world problems. In this paper we experimentally compare the classification uncertainty of the Bayesian model averaging with a restarting strategy and the randomised DT ensemble on a synthetic dataset and some domain problems commonly used in the machine learning community. To make the Bayesian DT averaging feasible, we use a Markov Chain Monte Carlo technique. The classification uncertainty is evaluated within an Uncertainty Envelope technique dealing with the class posterior distribution and a given confidence probability. Exploring a full posterior distribution, this technique produces realistic estimates which can be easily interpreted in statistical terms. In our experiments we found out that the Bayesian DTs are superior to the randomised DT ensembles within the Uncertainty Envelope technique.     

Optimal control policies for resource allocation in an activity network

In the paper a class of project-scheduling problems concerning the allocation of continuously divisible resources is considered. It is assumed that performing speeds of activities are continuous functions of the resource amount, and that the initial and terminal states of activities are known. For such mathematical models of project activities the problem of time-optimal resource allocation under instantaneous and integral constrains on a resource, and the problem of cost-optimal resource allocation with fixed project duration are formulated and a general solution concept is proposed. Necessary and sufficient conditions for the existence of a solution in particular cases are derived and properties of optimal schedules are given. The control policies for resource allocation are constructed for the example of the cost-optimal problem.     

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.     

Determination of critical chain project buffer based on information flow interactions

It has been well accepted in the literature that co-dependency between project activity durations is caused by resource tightness and network complexity. However, we show that information flow interaction between activities is the key factor for it. Based on whether there exist spliced relationships between activities, we introduce the concept of rework safety time. We propose a method to compute the rework safety time using the information output and input time factors, rework probability matrix, and rework impact matrix. We achieve the optimization of the critical chain sequencing via the design structure matrix so that the dependency between activities is reduced. The project buffer is then determined by the tail concentration method based on the optimized chain. The empirical results show that, as opposed to the traditional RSEM method, our approach improves the project buffer consumption rate, shortens project duration, reduces project cost, and increases project on-time completion rate.     

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

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

基于活动重叠的DSM项目进度优化与仿真

项目活动之间的重叠虽然可以缩短项目工期,但又存在返工风险。为此,本文采用设计结构矩阵(DSM),提出活动超前重叠因子矩阵和活动赶工重叠因子矩阵,结合返工风险矩阵,完整地描述了项目活动的重叠及其对返工的影响。提出了基于活动重叠的混合粒子群项目进度优化方法。通过案例计算表明,该法可以有效缩短项目工期,同时为项目决策者合理选择活动重叠量提供了新思路。