Project network models with discounted cash flows a guided tour through recent developments

The vast majority of the project scheduling methodologies presented in the literature have been developed with the objective of minimizing the project duration subject to precedence and other constraints. In doing so, the financial aspects of project management are largely ignored. Recent efforts have taken into account discounted cash flows and have focused on the maximization of the net present value (npv) of the project as the more appropriate objective. In this paper we offer a guided tour through the important recent developments in the expanding field of research on deterministic and stochastic project network models with discounted cash flows. Subsequent to a close examination of the rationale behind the npv objective, we offer a taxonomy of the problems studied in the literature and critically review the major contributions. Proper attention is given to npv maximization models for the unconstrained scheduling problem with known cash flows, optimal and suboptimal scheduling procedures with various types of resource constraints, and the problem of determining both the timing and amount of payments.     

Performance of the heuristic procedures for constrained projects with progress payments

All large scale resource constrained projects involve cash flows occurring during their life cycle. Several recent studies consider the problem of scheduling projects to maximise the net present value (NPV) of these cash flows. Their basic common assumption is that cash flows are mainly associated with specific events and they occur at event realisation times. An alternative assumption, which can be more realistic, is that cash inflows occur periodically, for example every month, as progress payments. This article considers the problem of maximising NPV given the alternative assumption. Three different heuristic rules are developed. The performance of these heuristic rules is analysed through a full factorial experiment with 108 scheduling conditions. The results indicate that three rules provide near-optimal schedules with respect to NPV maximisation while producing time schedules that do not delay the project completion time extensively.     

A Two Stage Search Heuristic for Scheduling Payments in Projects

When the Net Present Value (NPV) of a project is used as a measure of its financial performance, effective management of cash flows over the duration of the project is critical for improved profitability. Progress payments are a major component of project cash flows. In many project environments, the contractor can negotiate payment terms. Payments are typically tied to completion of project activities and therefore have significant impact on the schedule of activities and the timing of the payments. In this paper, we consider the problem of simultaneously determining the amount, timing and location of progress payments in projects to maximize NPV. Due to the combinatorial nature of the problem, heuristics are a practical approach to solving the problem. We propose a two-stage heuristic where simulated annealing is used in the first stage to determine a set of payments. In the second stage, activities are rescheduled to improve project NPV. We compare the performance of this general purpose heuristic with other problem-dependent heuristics from the literature. Our results indicate that the simulated annealing heuristic significantly outperforms the parameter-based heuristics. Although rescheduling in the second stage improves NPV, increases are relatively small in magnitude. While the specific parameters settings suggested by the simulated annealing heuristic in this study may have limited generalizability at this time due to the narrow range of problems tested, our analysis suggests that a pure simulated annealing approach is a very attractive alternative for obtaining good heuristic solutions to the complex problem of scheduling payments in projects.     

Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models

In this paper the multi-mode resource-constrained project scheduling problem with discounted cash flows is considered. A project is represented by an activity-on-node (AoN) network. A positive cash flow is associated with each activity. Four different payment models are considered: lump-sum payment at the completion of the project, payments at activities' completion times, payments at equal time intervals and progress payments. The objective is to maximize the net present value of all cash flows of the project. Local search metaheuristics: simulated annealing and tabu search are proposed to solve this strongly NP-hard problem. A comprehensive computational experiment is described, performed on a set of instances based on standard test problems constructed by the ProGen project generator, where, additionally, the activities' cash flows are generated randomly with the uniform distribution. The metaheuristics are computationally compared, the results are analyzed and discussed and some conclusions are given.     

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.     

Flow shop scheduling jobs with position-dependent processing times

The paper is devoted to some flow shop scheduling problems, where job processing times are defined by functions dependent on their positions in the schedule. An example is constructed to show that the classical Johnson's rule is not the optimal solution for two different models of the two-machine flow shop scheduling to minimize makespan. In order to solve the makespan minimization problem in the two-machine flow shop scheduling, we suggest Johnson's rule as a heuristic algorithm, for which the worst-case bound is calculated. We find polynomial time solutions to some special cases of the considered problems for the following optimization criteria: the weighted sum of completion times and maximum lateness. Some furthermore extensions of the problems are also shown.     

Coordination mechanisms with hybrid local policies

We study coordination mechanisms for scheduling n jobs on m parallel machines where agents representing the jobs interact to generate a schedule. Each agent acts selfishly to minimize the completion time of his/her own job, without considering the overall system performance that is measured by a central objective. The performance deterioration due to the lack of a central coordination, the so-called price of anarchy, is determined by the maximum ratio of the central objective function value of an equilibrium schedule divided by the optimal value. In the first part of the paper, we consider a mixed local policy with some machines using the SPT rule and other machines using the LPT rule. We obtain the exact price of anarchy for the problem of minimizing the makespan and some bounds for the problem of minimizing the total completion time. In the second part of the paper, we consider parallel machine scheduling subject to eligibility constraints. We devise new local policies based on the flexibilities and the processing times of the jobs. We show that the newly devised local policies outperform both the SPT and the LPT rules.     

A new heuristic for the multi-mode resource investment problem

This paper considers the problem of minimizing resource investment required to execute the tasks in a project network by a given project due date. A project consists of non-pre-emptive tasks executed in a known and required precedence order. Each task is completed in one of its feasible modes, which may differ not only in task duration but also in consumption of renewable resources. A priority rule heuristic with polynomial computational complexity is presented for this computationally intractable problem. This heuristic simultaneously considers due date constraints and resource usage to select and schedule tasks with one decision rule. This differs from prior multi-mode priority rule scheduling heuristics that apply two consecutive decision rules to schedule tasks. Extensive computational testing indicates promising results.     

基于随机活动工期的多模式现金流均衡项目调度优化

承包商在项目执行过程中的现金流均衡是保证项目成功的关键因素。本文研究基于随机活动工期的多模式现金流均衡项目调度问题,旨是在项目工期及鲁棒性阈值约束下合理安排活动执行模式与开始时间,实现承包商现金流均衡。本文通过构建整数规划优化模型对研究问题进行刻画,随后设计模拟退火算法进行求解,最后进行案例分析。结果表明:鲁棒性阈值虽然可以保证基准进度的稳定性,但是提高鲁棒性阈值水平反而不利于承包商的现金流均衡,该值过高时甚至得不到可行解。本文研究可为随机活动工期背景下承包商的现金流控制提供定量化决策支持。     

Scheduling in network flow shops

We consider the general problem of static scheduling of a set of jobs in a network flow shop. In network flow shops, the scheduler not only has to sequence and schedule but also must concurrently determine the process routing of the jobs through the shop. In this paper, we establish the computational complexity of this new class of scheduling problem and propose a general purpose heuristic procedure. The performance of the heuristic is analyzed when makespan, cycle time and average flow time are the desired objectives.This research has been supported by the UCLA Academic Senate Grant #95.     

Project Scheduling with Discounted Cash Flows and Progress Payments

In all large scale projects, there correspond cash flows that incur throughout the life of the project. The scheduling of these projects to maximize the present value of the cash flows has been a topic of recent research. The basic assumption of earlier research is that the cash flows are mainly associated with some events of the project and they occur at the event realization times. However, in several real life projects, the cash inflows do not occur at the event realization times, rather they occur at the end of some time periods, like months, as progress payments. In this article, maximizing the present value of the cash flows in such projects is considered and a mixed-integer formulation of the problem is presented. In this formulation, activity profit curves are defined and used. Computational experience on some randomly generated test problems provides promising results especially when the Benders Decomposition technique is employed for solving the problem.     

Some single-machine scheduling problems with actual time and position dependent learning effects

In this paper we study some single-machine scheduling problems with learning effects where the actual processing time of a job serves as a function of the total actual processing times of the jobs already processed and of its scheduled position. We show by examples that the optimal schedules for the classical version of problems are not optimal under this actual time and position dependent learning effect model for the following objectives: makespan, sum of kth power of the completion times, total weighted completion times, maximum lateness and number of tardy jobs. But under certain conditions, we show that the shortest processing time (SPT) rule, the weighted shortest processing time (WSPT) rule, the earliest due date (EDD) rule and the modified Moore’s Algorithm can also construct an optimal schedule for the problem of minimizing these objective functions, respectively.     

Four Payment Models for the Multi-Mode Resource Constrained Project Scheduling Problem with Discounted Cash Flows

In this paper, the multi-mode resource constrained project scheduling problem with discounted cash flows is considered. The objective is the maximization of the net present value of all cash flows. Time value of money is taken into consideration, and cash in- and out-flows are associated with activities and/or events. The resources can be of renewable, nonrenewable, and doubly constrained resource types. Four payment models are considered: lump sum payment at the terminal event, payments at prespecified event nodes, payments at prespecified time points and progress payments. For finding solutions to problems proposed, a genetic algorithm (GA) approach is employed, which uses a special crossover operator that can exploit the multi-component nature of the problem. The models are investigated at the hand of an example problem. Sensitivity analyses are performed over the mark up and the discount rate. A set of 93 problems from literature are solved under the four different payment models and resource type combinations with the GA approach employed resulting in satisfactory computation times. The GA approach is compared with a domain specific heuristic for the lump sum payment case with renewable resources and is shown to outperform it.     

Maximizing the Net Present Value of a Project Under Resource Constraints Using a Lagrangian Relaxation Based Heuristic with Tight Upper Bounds

Resource-constrained project scheduling under a net present value objective attracts growing interest. Because this is an NP-hard problem, it is unlikely that optimum solutions can be computed for large instances within reasonable computation time. Thus, heuristics have become a popular research field. Up to now, however, upper bounds are not well researched. Therefore, most researchers evaluate their heuristics on the basis of a best known lower bound, but it is unclear how good the performance really is. With this contribution we close this gap and derive tight upper bounds on the basis of a Lagrangian relaxation of the resource constraints. We also use this approach as a basis for a heuristic and show that our heuristic as well as the cash flow weight heuristic proposed by Baroum and Patterson yield solutions very close to the optimum result. Furthermore, we discuss the proper choice of a test-bed and emphasize that discount rates must be carefully chosen to give realistic instances.     

Scheduling by positional completion times: Analysis of a two-stage flow shop problem with a batching machine

We consider a scheduling problem introduced by Ahmadi et al., Batching and scheduling jobs on batch and discrete processors, Operation Research 40 (1992) 750–763, in which each job has to be prepared before it can be processed. The preparation is performed by a batching machine; it can prepare at mostc jobs in each run, which takes an amount of time that is independent of the number and identity of the jobs under preparation. We present a very strong Lagrangian lower bound by using the new concept of positional completion times. This bound can be computed in O(n logn) time only, wheren is the number of jobs. We further present two classes of O(n logn) heuristics that transform an optimal schedule for the Lagrangian dual problem into a feasible schedule. Any heuristic in one class has performance guarantee of 3/2. We further show that even the most naive heuristic in this class has a compelling empirical performance. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.An earlier draft of this paper has appeared in the Proceedings of the Fourth International IPCO Conference, Lecture Notes in Computer Science, vol. 920, Springer, Berlin.     

Lagrangian heuristics for scheduling new product development projects in the pharmaceutical industry

To stay ahead of their competition, pharmaceutical firms must make effective use of their new product development (NPD) capabilities by efficiently allocating its analytical, clinical testing and manufacturing resources across various drug development projects. The resulting project scheduling problems involve coordinating hundreds of testing and manufacturing activities over a period of several quarters. Most conventional integer programming approaches are computationally impractical for problems of this size, while priority rule-driven heuristics seldom provide consistent solution quality. We propose a Lagrangian decomposition (LD) heuristic that exploits the special structure of these problems. Some resources (typically manpower) are shared across all on-going projects while others (typically equipment) are specific to individual project categories. Our objective function is a weighted discounted cost expressed in terms of activity completion times. The LD heuristics were subjected to a comprehensive experimental study based on typical operational instances. While the conventional “Reward–Risk” priority rule heuristic generates duality gaps between 47–58%, the best LD heuristic achieves duality gaps between 10–20%. The LD heuristics also yield makespan reductions of over 30% over the Reward–Risk priority rule.     

基于随机活动工期的现金流动态均衡前摄性与反应性项目调度优化

承包商的现金流动态均衡对不确定条件下项目的顺利实施有重要影响。作者研究基于随机活动工期的现金流动态均衡前摄性及反应性项目调度问题,目标是在随机活动工期条件下,为承包商生成现金流均衡基准进度,并根据执行过程中的实际情况,动态地对其进行反应性调整。首先,通过建立前摄性调度优化模型生成基准进度,并提出两个反应性调度策略对其进行调整。其次,为以上诸模型的求解设计了模拟退火和禁忌搜索相结合的混合算法tabu-SA。最后,针对前摄性调度模型,在随机生成的算例集合上对算法进行测试,并进行大规模仿真实验。研究结果可以为随机活动工期下承包商保持现金流动态均衡、确保项目顺利实施,提供定量化决策支持。     

Safe scheduling: Setting due dates in single-machine problems

We consider single-machine stochastic scheduling models with due dates as decisions. In addition to showing how to satisfy given service-level requirements, we examine variations of a model in which the tightness of due-dates conflicts with the desire to minimize tardiness. We show that a general form of the trade-off includes the stochastic E/T model and gives rise to a challenging scheduling problem. We present heuristic solution methods based on static and dynamic sorting procedures. Our computational evidence identifies a static heuristic that routinely produces good solutions and a dynamic rule that is nearly always optimal. The dynamic sorting procedure is also asymptotically optimal, meaning that it can be recommended for problems of any size.     

Forming and scheduling jobs with capacitated containers in semiconductor manufacturing: Single machine problem

We study a scheduling problem motivated by the challenges observed in the newest semiconductor manufacturing wafer fabrication facilities. As wafers are larger and heavier in these wafer fabs, it is becoming more common to use specialized material handling containers that carry multiple orders coming from different customers and to schedule the containers as jobs in the fab. The system performance is a function of the completion times of orders, which ultimately depend on both (1) how the orders are assigned to such containers (“job formation”), and (2) how the containers are scheduled in the fab (“job scheduling”). The overall problem is to find the best way to form and schedule the jobs subject to complicating constraints, including the restrictions on the number of containers that can be used at one time and on the number of wafers the containers can carry. We focus on the single machine job formation and scheduling problem with the total completion time objective. We show that this problem is quite different from conventional parallel and serial batching scenarios and prove that the uncapacitated special case is polynomially solvable and the capacitated case is strongly NP-hard. We use a dynamic programming algorithm to solve the uncapacitated problem, which not only provides tight lower bounds for the capacitated problem, but also becomes a basis for a heuristic approach for the capacitated problem. The computational results show that this approach is very effective, leading to small optimality gaps that get even smaller as the problems become larger.     

Branch and bound based solution algorithms for the budget constrained discrete time/cost trade-off problem

The time/cost trade-off models in project management aim to reduce the project completion time by putting extra resources on activity durations. The budget problem in discrete time/cost trade-off scheduling selects a time/cost mode for each activity so as to minimize the project completion time without exceeding the available budget. There may be alternative modes that solve the budget problem optimally and each solution may have a different total cost value. In this study we consider the budget problem and aim to find the minimum cost solution among the minimum project completion time solutions. We analyse the structure of the problem together with its linear programming relaxation and derive some mechanisms for reducing the problem size. We solve the reduced problem by branch and bound based optimization and heuristic algorithms. We find that our branch and bound algorithm finds optimal solutions for medium-sized problem instances in reasonable times and the heuristic algorithms produce high quality solutions very quickly.