A bidirectional heuristic for maximizing the net present value of large‐scale projects subject to limited resources

We consider the scheduling of large‐scale projects to maximize the project net present value given temporal and resource constraints. The net present value objective emphasizes the financial aspects of project management. Temporal constraints between the start times of activities make it possible to handle practical problem assumptions. Scarce resources are an expression of rising cost. Since optimization techniques are not expedient to solve such problems and most heuristic methods known from literature cannot deal with general temporal constraints, we propose a new bidirectional priority‐rule based method. Scheduling activities with positive cash flows as early and activities with negative cash flows as late as possible results in a method which is completed by unscheduling techniques to cope with scarce resources. In a computational experiment, we compare the well‐known serial generation scheme where all activities are scheduled as early as possible with the proposed bidirectional approach. On the basis of a comprehensive data set known from literature containing instances with up to 1002 activities, the efficiency of the new approach is demonstrated. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

A metaheuristic scheduling procedure for resource-constrained projects with cash flows

Resource-constrained project scheduling problems with cash flows (RCPSPCF) are complex, combinatorial optimization problems. Many heuristics have been reported in the literature that produce reasonable schedules in limited project environments. However, the lack of a heuristic that dominates under differing project conditions can lead to a suboptimal choice of an appropriate heuristic for scheduling any given project. This may result in poor schedules and monetary losses. This paper reports on the application of the tabu search metaheuristic procedure for the RCPSPCF. Strategies for neighborhood generation and candidate selection that exploit the special features of the problem are combined with a simple multiheuristic start procedure. Extensive experimentation, with multiple data sets and comparison with an upper bound, indicates a significant improvement, both in project Net Present Value (NPV) as well as the number of projects, where the metaheuristic outperforms the best known heuristics in the literature. More specifically, this procedure produces the best schedules in over 85% of the projects tested, in contrast to the best single-pass heuristics which have been shown to dominate in at most 20% of the same cases. This iterative, general purpose heuristic is able to adapt significantly better to the complex interactions of the many critical parameters of the RCPSPCF than single-pass heuristics that use more specific information about each project environment. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 912–927, 1999     

Scheduling recurrent construction

A problem we call recurrent construction involves manufacturing large, complex, expensive products such as airplanes, houses, and ships. Customers order configurations of these products well in advance of due dates for delivery. Early delivery may not be permitted. How should the manufacturer determine when to purchase and release materials before fabrication, assembly, and delivery? Major material expenses, significant penalties for deliveries beyond due dates, and long product makespans in recurrent construction motivate choosing a release timetable that maximizes the net present value of cash flows. Our heuristic first projects an initial schedule that dispatches worker teams to tasks for the backlogged products, and then solves a series of maximal closure problems to find material release times that maximize NPV. This method compares favorably with other well‐known work release heuristics in solution quality for large problems over a wide range of operating conditions, including order strength, cost structure, utilization level, batch policy, and uncertainty level. Computation times exhibit near linear growth in problem size. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Solving time/cost trade-off problems with discounted cash flows using generalized benders decomposition

In this article we consider a project scheduling problem where there are cash flows throughout the life of the project and where shorter activity durations can be attained by incurring greater direct costs. In particular, the objective of this problem is to determine the activity durations and a schedule of activity start times so that the net present value of cash flows is maximized. We formulate this problem as a mixed-integer nonlinear program which is amenable to solution using the generalized Benders decomposition technique developed by Geoffrion. We test the algorithm on 140 project scheduling problems, the largest of which contains 30 nodes and 64 activities. Our computational results are quite encouraging inasmuch as 123 of the 140 problems require less than 1 CPU second of solution time. © 1993 John Wiley & Sons, Inc.     

A self‐adapting genetic algorithm for project scheduling under resource constraints

This papers deals with the classical resource‐constrained project scheduling problem (RCPSP). There, the activities of a project have to be scheduled subject to precedence and resource constraints. The objective is to minimize the makespan of the project. We propose a new heuristic called self‐adapting genetic algorithm to solve the RCPSP. The heuristic employs the well‐known activity list representation and considers two different decoding procedures. An additional gene in the representation determines which of the two decoding procedures is actually used to compute a schedule for an individual. This allows the genetic algorithm to adapt itself to the problem instance actually solved. That is, the genetic algorithm learns which of the alternative decoding procedures is the more successful one for this instance. In other words, not only the solution for the problem, but also the algorithm itself is subject to genetic optimization. Computational experiments show that the mechanism of self‐adaptation is capable to exploit the benefits of both decoding procedures. Moreover, the tests show that the proposed heuristic is among the best ones currently available for the RCPSP. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 433–448, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10029     

Adaptive search for solving hard project scheduling problems

In this article we propose a new heuristic solution technique for resource-constrained project scheduling problems. Basically, it is a hybrid of priority rule and random search techniques which employs two types of adaptations in order to determine the solution space. We enhance this general scheme by the use of a new priority rule and by lower bounding techniques. The method is evaluated by comparing it with other recently proposed heuristics on a widely used set of benchmark-instances. Furthermore, we show that the procedure can be usefully applied to solve different hard problems within the field of project scheduling. © 1996 John Wiley & Sons, Inc.     

Performance of heuristics for the uncapacitated lot-size problem

Although the uncapacitated lot-size problem can be solved optimally very efficiently, heuristics are often used instead in practice. Recent research on the performance of these heuristics has focused on worst-case analysis and empirical testing. This article extends earlier worst-case results, for several of the commonly used heuristics, to more specific problem classes to obtain a better understanding of when a heuristic can be expected to perform well and when it is likely to perform poorly. In particular, we obtain bounds for the finite-horizon problem (earlier results all assume an infinite horizon) and for problems in which demand is (i) constant, and (ii) bounded from above or below. We also show how the heuristics can be classified into three categories, with heuristics in each category using similar rules to construct feasible production schedules. Using this categorization, our analysis reveals that a small change in the definition of a heuristic can often have a significant impact on its performance. © 1992 John Wiley & Sons, Inc.     

The payment scheduling problem

Large complicated projects with interdependent activities can be described by project networks. Arcs represent activities, nodes represent events, and the network's structure defines the relation between activities and events. A schedule associates an occurrence time with each event: the project can be scheduled in several different ways. We assume that a known amount of cash changes hands at each event. Given any schedule the present value of all cash transactions can be calculated. The payment scheduling problem looks for a schedule that maximizes the present value of all transactions. This problem was first introduced by Russell [2]; it is a nonlinear program with linear constraints and a nonconcave objective. This paper demonstrates that the payment scheduling problem can be transformed into an equivalent linear program. The linear program has the structure of a weighted distribution problem and an efficient procedure is presented for its solution. The algorithm requires the solution of triangular systems of equations with all matrix coefficients equal to ± or 0.     

Decomposition and hybrid simulated annealing heuristics for the parallel-machine total tardiness problem

A polynomial decomposition heuristic is developed for the parallel-machine tardiness problem (P&sol& sol;T) by extending the decomposition principle embedded in the single-machine tardiness problem (1&sol/T) to a parallel-machine setting. The subproblems generated by the decomposition are solved by an effective heuristic that yields solutions such that the schedule on any individual machine satisfies the single-machine decomposition principle. A hybrid simulated annealing heuristic tailored to the P&sol/T problem is also presented. Computational results demonstrate the efficiency and effectiveness of the decomposition heuristic. © 1997 John Wiley & Sons, Inc.     

Dynamic routing of prioritized warranty repairs

Recent years have seen a strong trend toward outsourcing warranty repair services to outside vendors. In this article we consider the problem of dynamically routing warranty repairs to service vendors when warranties have priority levels. Each time an item under warranty fails, it is sent to one of the vendors for repair. Items covered by higher priority warranty receive higher priority in repair service. The manufacturer pays a fixed fee per repair and incurs a linear holding cost while an item is undergoing or waiting for repair. The objective is to minimize the manufacturer's long‐run average cost. Because of the complexity of the problem, it is very unlikely that there exist tractable ways to find the optimal routing strategies. Therefore, we propose five heuristic routing procedures that are applicable to real‐life problems. We evaluate the heuristics using simulation. The simulation results show that the index‐based “generalized join the shortest queue” policy, which applies a single policy improvement step to an initial state‐independent policy, performs the best among all five heuristics. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

A competitive genetic algorithm for resource-constrained project scheduling

In this paper we consider the resource-constrained project scheduling problem (RCPSP) with makespan minimization as objective. We propose a new genetic algorithm approach to solve this problem. Subsequently, we compare it to two genetic algorithm concepts from the literature. While our approach makes use of a permutation based genetic encoding that contains problem-specific knowledge, the other two procedures employ a priority value based and a priority rule based representation, respectively. Then we present the results of our thorough computational study for which standard sets of project instances have been used. The outcome reveals that our procedure is the most promising genetic algorithm to solve the RCPSP. Finally, we show that our genetic algorithm yields better results than several heuristic procedures presented in the literature. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 733–750, 1998     

An approximate dynamic programing approach to the development of heuristics for the scheduling of impatient jobs in a clearing system

A single server is faced with a collection of jobs of varying duration and urgency. Each job has a random lifetime during which it is available for nonpreemptive service. Should a job's lifetime expire before its service begins then it is lost from the system unserved. The goal is to schedule the jobs for service to maximize the expected number served to completion. Two heuristics have been proposed in the literature. One (labeled π^S) operates a static priority among the job classes and works well in a “no premature job loss” limit, whereas the second (π^M) is a myopic heuristic which works well when lifetimes are short. Both can exhibit poor performance for problems at some distance from the regimes for which they were designed. We develop a robustly good heuristic by an approximative approach to the application of a policy improvement step to the asymptotically optimal heuristic π^S, in which we use a fluid model to obtain an approximation for the value function of π^S. The performance of the proposed heuristic is investigated in an extensive numerical study. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 2010     

Efficient methods for sequencing minimum job sets on mixed model assembly lines

For sequencing different models on a paced assembly line, the commonly accepted objective is to keep the operators within the boundaries of their stations. When the operators reach the right boundary, they terminate the operation prematurely. In this article we address the problem of sequencing jobs decomposed into identical and repeating sets to minimize the total amount of remaining work, or, equivalently, to maximize the total amount of work completed. We propose an optimum algorithm and a heuristic procedure that utilizes different priority functions based on processing times. Experimental results indicate that the proposed heuristic requires less computational effort and performs better than the existing procedures: On the average, 11–14% of improvements are obtained over real data mentioned in the literature (20 groups of 1000 jobs from a U.S. automobile manufacturer). © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44 : 419–437, 1997     

遥感数据处理任务调度的Petri网模型及求解算法

为了对多源遥感数据的处理任务进行有效的调度和管理,提高处理资源的利用率,根据遥感数据处理任务调度问题的特点,采用Petri网对该问题进行形式化描述,建立了遥感数据处理任务调度的数学模型,根据该问题的多目标特性,采用蚁群算法进行求解.给出仿真实例,将蚁群算法的求解结果与启发式算法和模拟退火算法的求解结果进行比较,验证算法...     

Optimal sequential replenishment of ships during combat

A carrier battle group is operating in an area where it is subject to attack by enemy aircraft. It is anticipated that air raids will occur in large waves. The uncertain time between raids is available for the replenishment of supplies. We consider the problem of how best to schedule ammunition replenishment during this period. The theory of Gittins indices provides the technical background to the development of a range of models which yield a hierarchy of index-based heuristics for replenishment. One such heuristic is assessed computationally in a more realistic scenario than is explicitly allowed for by the models.     

Maximizing project cash availability

Consider a project during the life cycle of which there are cash payouts and in‐flows. To better meet his financial commitments, the project owner would like to meet all deadlines without running out of cash. We show that the cash availability objective is similar to the total weighted flowtime used to measure work‐in‐progress performance in the scheduling and inventory control literatures. In this article we provide several specialized solution methods for the problem of minimizing total weighted flowtime in an arbitrary acyclic project network, subject to activity release times and due dates, where the activity weights may be positive or negative and represent cash in‐ and out‐flows. We describe the structure of an optimal solution and provide several efficient algorithms and their complexity based on mincost and maxflow formulations. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

A branch-and-bound algorithm to minimize total flow time with unequal release dates

This article examines the single-machine scheduling problem to minimize total flow time with unequal release dates. This problem has been proven to be NP-hard. We present a necessary and sufficient condition for local optimality which can also be considered as a priority rule. On the basis of this condition, we then define a class of schedules which contains all optimal solutions. We present some efficient heuristic algorithms using the previous condition to build a schedule belonging to this subset. We also prove some new dominance theorems, discuss the results found in the literature for this problem, and propose a branch-and-bound algorithm in which the heuristics are used to provide good upper bounds. We compare this new algorithm with existing algorithms found in the literature. Computational results on problems with up to 100 jobs indicate that the proposed branch-and-bound algorithm is superior to previously published algorithms. © 1992 John Wiley & Sons. Inc.     

Coordinated scheduling of customer orders for quick response

The scheduling problem addressed in this paper concerns a manufacturer who produces a variety of product types and operates in a make‐to‐order environment. Each customer order consists of known quantities of the different product types, and must be delivered as a single shipment. Periodically the manufacturer schedules the accumulated and unscheduled customer orders. Instances of this problem occur across industries in manufacturing as well as in service environments. In this paper we show that the problem of minimizing the weighted sum of customer order delivery times is unary NP‐hard. We characterize the optimal schedule, solve several special cases of the problem, derive tight lower bounds, and propose several heuristic solutions. We report the results of a set of computational experiments to evaluate the lower bounding procedures and the heuristics, and to determine optimal solutions. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Case‐based reasoning and improved adaptive search for project scheduling

Most scheduling problems are notoriously intractable, so the majority of algorithms for them are heuristic in nature. Priority rule‐based methods still constitute the most important class of these heuristics. Of these, in turn, parametrized biased random sampling methods have attracted particular interest, due to the fact that they outperform all other priority rule‐based methods known. Yet, even the “best” such algorithms are unable to relate to the full range of instances of a problem: Usually there will exist instances on which other algorithms do better. We maintain that asking for the one best algorithm for a problem may be asking too much. The recently proposed concept of control schemes, which refers to algorithmic schemes allowing to steer parametrized algorithms, opens up ways to refine existing algorithms in this regard and improve their effectiveness considerably. We extend this approach by integrating heuristics and case‐based reasoning (CBR), an approach that has been successfully used in artificial intelligence applications. Using the resource‐constrained project scheduling problem as a vehicle, we describe how to devise such a CBR system, systematically analyzing the effect of several criteria on algorithmic performance. Extensive computational results validate the efficacy of our approach and reveal a performance similar or close to state‐of‐the‐art heuristics. In addition, the analysis undertaken provides new insight into the behaviour of a wide class of scheduling heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 201–222, 2000     

Heuristics for the location of inspection stations on a network

This article considers the preventive flow interception problem (FIP) on a network. Given a directed network with known origin‐destination path flows, each generating a certain amount of risk, the preventive FIP consists of optimally locating m facilities on the network in order to maximize the total risk reduction. A greedy search heuristic as well as several variants of an ascent search heuristic and of a tabu search heuristic are presented for the FIP. Computational results indicate that the best versions of the latter heuristics consistently produce optimal or near optimal solutions on test problems. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 287–303, 2000