Setting gates for activities in the stochastic project scheduling problem through the cross entropy methodology

This paper addresses the problem of scheduling activities in projects with stochastic activity durations. The aim is to determine for each activity a gate—a time before it the activity cannot begin. Setting these gates is analogous to setting inventory levels in the news vendor problem. The resources required for each activity are scheduled to arrive according to its gate. Since activities’ durations are stochastic, the start and finish time of each activity is uncertain. This fact may lead to one of two outcomes: (1) an activity is ready to start its processing as all its predecessors have finished, but it cannot start because the resources required for it were scheduled to arrive at a later time. (2) The resources required for the activity have arrived and are ready to be used but the activity is not ready to start because of precedence constraints. In the first case we will incur a “holding” cost while in the second case, we will incur a “shortage” cost. Our objective is to set gates so as to minimize the sum of the expected holding and shortage costs. We employ the Cross-Entropy method to solve the problem. The paper describes the implementation of the method, compares its results to various heuristic methods and provides some insights towards actual applications.     

Setting gates for activities in the stochastic project scheduling problem through the cross entropy methodology

This paper addresses the problem of scheduling activities in projects with stochastic activity durations. The aim is to determine for each activity a gate—a time before it the activity cannot begin. Setting these gates is analogous to setting inventory levels in the news vendor problem. The resources required for each activity are scheduled to arrive according to its gate. Since activities’ durations are stochastic, the start and finish time of each activity is uncertain. This fact may lead to one of two outcomes: (1) an activity is ready to start its processing as all its predecessors have finished, but it cannot start because the resources required for it were scheduled to arrive at a later time. (2) The resources required for the activity have arrived and are ready to be used but the activity is not ready to start because of precedence constraints. In the first case we will incur a “holding” cost while in the second case, we will incur a “shortage” cost. Our objective is to set gates so as to minimize the sum of the expected holding and shortage costs. We employ the Cross-Entropy method to solve the problem. The paper describes the implementation of the method, compares its results to various heuristic methods and provides some insights towards actual applications.     

A linear Bayesian stochastic approximation to update project duration estimates

By relaxing the unrealistic assumption of probabilistic independence on activity durations in a project, this paper develops a hierarchical linear Bayesian estimation model. Statistical dependence is established between activity duration and the amount of resource, as well as between the amount of resource and the risk factor. Upon observation or assessment of the amount of resource required for an activity in near completion, the posterior expectation and variance of the risk factor can be directly obtained in the Bayesian scheme. Then, the expected amount of resources required for and the expected duration of upcoming activities can be predicted. We simulate an application project in which the proposed model tracks the varying critical path activities on a real time basis, and updates the expected project duration throughout the entire project. In the analysis, the proposed model improves the prediction accuracy by 38.36% compared to the basic PERT approach.     

The multi-mode resource-constrained project scheduling problem with generalized precedence relations

In this paper, we tackle the challenging problem of scheduling activities to minimize the project duration, in which the activities (a) are subject to generalized precedence relations, (b) require units of multiple renewable, non-renewable and doubly constrained resources for which a limited availability is imposed, and (c) can be performed in one of several different ways, reflected in multiple activity scenarios or modes. These multiple modes give rise to several kinds of trade-offs (time/resource, time/cost and resource/resource trade-offs) which allow for a more efficient allocation and use of resources. We present a local search-based solution methodology which is able to handle many real-life project scheduling characteristics such as time-varying resource requirements and availabilities, activity ready times, due dates and deadlines, activity overlaps, activity start time constraints and other types of temporal constraints.     

Time-cost trade-off via optimal control theory in Markov PERT networks

We develop a new analytical model for the time-cost trade-off problem via optimal control theory in Markov PERT networks. It is assumed that the activity durations are independent random variables with generalized Erlang distributions, in which the mean duration of each activity is a non-increasing function of the amount of resource allocated to it. Then, we construct a multi-objective optimal control problem, in which the first objective is the minimization of the total direct costs of the project, in which the direct cost of each activity is a non-decreasing function of the resources allocated to it, the second objective is the minimization of the mean of project completion time and the third objective is the minimization of the variance of project completion time. Finally, two multi-objective decision techniques, viz, goal attainment and goal programming are applied to solve this multi-objective optimal control problem and obtain the optimal resources allocated to the activities or the control vector of the problem     

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.     

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.     

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.     

On-line control model for network construction projects

An activity-on-arc network project of the PERT type with random activity durations is considered. For each activity, its accomplishment is measured in percentages of the total project. When operated, each activity utilizes resources of a pregiven capacity and no resource reallocation is undertaken in the course of the project's realization. Each activity can be operated at several possible speeds that are subject to random disturbances and correspond to one and the same resource capacity; that is, these speeds depend only on the degree of intensity of the project's realization. For example, in construction projects partial accomplishments are usually measured in percentages of the total project, while different speeds correspond to different hours a day per worker. The number of possible speeds is common to all activities. For each activity, speeds are sorted in ascending order of their average values—namely speeds are indexed. It is assumed that at any moment t>0 activities, in operation at that moment, have to apply speeds of one and the same index that actually determines the project's speed. The progress of the project can be evaluated only via inspection at control points that have to be determined. The project's due date and the chance constraint to meet the deadline are pregiven. An on-line control model is suggested that, at each control point, faces a stochastic optimization problem. Two conflicting objectives are imbedded in the model:(1) to minimize the number of control points, and(2) to minimize the average index of the project's speeds which can be changed only at a control point.At each routine control point, decision-making centers on determining the next control point and the new index of the speeds (for all activities to be operated) up to that point. The model's performance is verified via simulation.The developed on-line control algorithm can be used for various PERT network projects which can be realized with different speeds, including construction projects and R&D projects.     

Activity consolidation to improve responsiveness

There is a long history of modeling projects to meet time and cost objectives. Most of these models look at adjusting the level of resources available to the project in order to crash the time required to complete certain activities. These models usually take the activities and the graph structure of the project as given and fixed, but in practice there is often significant discretion in how activities are defined. This is especially important when there are information flows and time delays associated with the hand-off between an activity and its successor. This paper models the choice of how to meet the time and cost objectives through combining multiple activities into one while maintaining the original activity precedence relationships. A mixed-integer linear programming model is developed for the problem, and an implicit enumeration and a tabu search heuristic are tested with a suite of problem examples.     

A Stochastic Model for Bidding

Competitive bidding situations involve considering a multiplicity of factors. Organizations must be able to weigh the relative probability of potential projects based on resource usage, project duration and competitor actions to decide which of many possible bids to submit. A bidding strategy designed to maximize expected long run return is crucial, since an organization can usually submit only one bid per project.This paper presents a family of stochastic dynamic programming models considering different bidding situations. Several projects, each with several potential bids, are available for each situation. The objective is to determine what bidding strategy will maximize expected returns. Models are developed for two principle bidding situations: sequential, where projects are bid individually; and simultaneous, where several projects are bid at one time. Next, the effects of over- or under-commitment of resources are incorporated into the models. Finally, changes in project timing and the resultant effects on bidding strategy are included.A numerical example traces the changes in bidding strategy which occur as the models are expanded. The general formulation of bidding problems is also discussed, including changing the bid success probabilities due to competitor actions, the possibility of crashing projects and alternate methods of performing projects.     

新产品研发项目GERT模型及其模拟求解

本文以新产品研发项目—— V CDM3型真空树脂灌注机的研发过程为背景 ,利用随机网络技术建立了该项目的 GERT模型 ;基于 GERT模型的简化递推算法 ,作者编制了专用软件对该模型进行了模拟求解 ,获得了项目完成时间的各种统计特征值和概率分布直方图 ;根据模拟计算结果 ,作者进一步对项目完成时间进行了统计推断 ,从而为项目进度的控制和决策提供了定量化的参考依据 .     

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 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.     

A dependent project evaluation and review technique: A Bayesian network approach

The Program Evaluation and Review Technique (PERT) dates back to 1959. This method evaluates the uncertainty distribution of a project’s completion time given the uncertain completion times of the activities/tasks comprised within it. Each activity’s uncertainty was defined originally by a unique two parameter beta PERT distribution satisfying what is known to be the PERT mean and PERT variance. In this paper, a three-parameter PERT family of bounded distributions is introduced satisfying that same mean and variance, generalizing the beta PERT distribution. Their additional flexibility allows for the modeling of statistical dependence in a continuous Bayesian network, generalizing in turn the traditional PERT procedure where statistical independence is assumed among beta PERT activity durations. Through currently available Bayesian network software and the construction of that PERT family herein, the coherent monitoring of remaining project completion time uncertainty given partial completion of a project may become more accessible to PERT analysts. An illustrative example demonstrating the benefit of monitoring of remaining project completion time uncertainty as activities complete in that Bayesian fashion shall be presented, including expressions and algorithms for the specification of the three prior parameters for each activity in the project network to adhere to classical the PERT mean and PERT variance and a degree of statistical dependence between them.     

Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting

This paper presents a priority rule-based heuristic for the multi-mode resource-constrained project scheduling problem with the splitting of activities around unavailable resources allowed. 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. A new concept called moving resource strength is developed to help identify project situations where activity splitting is likely to be beneficial during scheduling. The moving resource strength concept is implemented in priority rule-based heuristics to control activity splitting when scheduling. Multiple comparisons of the performance of combination of activity–mode priority rules used in the heuristics are provided. Computational experiments demonstrate the effectiveness of the heuristic in reducing project makespan, and minimizing activity splitting.     

计划评审技术的改进

由于计划评审技术存在的不足,导致项目管理存在一定的偏差.对计划评审技术中的活动期望时间和方差的公式做了改进,从而提高了项目管理的精确性.还指出计划评审技术中活动期望时间和方差的计算公式,实际上是改进后公式的特殊情形.     

Discrete-continuous project scheduling with discounted cash inflows and various payment models—a review of recent results

In this work discrete-continuous project scheduling problems with discounted cash flows are considered. These problems are characterized by the fact that activities of a project simultaneously require discrete and continuous resources for their execution. A class of these problems is considered, where the number of discrete resources is arbitrary, and there is one continuous, renewable resource, whose total amount available at a time is limited. Activities are non-preemptable, and the processing rate of an activity is a continuous, increasing function of the amount of the continuous resource allotted to the activity at a time. A positive cash flow (cash inflow) is associated with each activity, and the objective is to maximize the net present value (NPV). The discrete-continuous resource-constrained project scheduling problem with discounted cash flows (DCRCPSPDCF) is defined. Four payment models are considered: lump-sum payment at the completion of the project, payments at activity completion times, payments at equal time intervals, and progress payments. Some properties of optimal schedules are proved for two important classes of processing rate functions: all functions not greater than a linear function (including linear and convex functions), and concave processing rate functions.     

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.