Heuristic scheduling of resource-constrained projects with cash flows

Resource-constrained project scheduling with cash flows occurs in many settings, ranging from research and development to commercial and residential construction. Although efforts have been made to develop efficient optimal procedures to maximize the net present value of cash flows for resource-constrained projects, the inherent intractability of the problem has led to the development of a variety of heuristic methods to aid in the development of near-optimal schedules for large projects. This research focuses on the use of insights gained from the solution of a relaxed optimization model in developing heuristic procedures to schedule projects with multiple constrained resources. It is shown that a heuristic procedure with embedded priority rules that uses information from the revised solution of a relaxed optimization model increases project net present value. The heuristic procedure and nine different embedded priority rules are tested in a variety of project environments that account for different network structures, levels of resource constrainedness, and cash-flow parameters. Extensive testing with problems ranging in size from 21 to 1000 activities shows that the new heuristic procedures dominate heuristics using information from the critical path method (CPM), and in most cases outperform heuristics from previous research. The best performing heuristic rules classify activities into priority and secondary queues according to whether they lead to immediate progress payments, thus front loading the project schedule. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 365–381, 1997     

A new heuristic solution method in resource-constrained project scheduling

A new heuristic method is presented for the resolution of multiresource constrained conflicts in project scheduling. In attempting to find a minimal makespan solution, the algorithm employs a simple procedure to generate a feasible solution with no backtracking. A postanalysis phase then applies a hill-climbing search. The solution method is different from existing heuristic methods in that it repairs resource conflicts rather than constructs detailed schedules by dispatching activities. Resource-violating sets of activities are identified which must be prevented from concurrent execution because this would violate resource constraints. Repairs are made by imposing an arc to sequence two activities in such a resource violating set. Computational results are compared with those of existing heuristics for the minimal makespan problem.     

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     

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.     

Using multiple searchers in constrained-path,moving-target search problems

The search theory open literature has paid little, if any, attention to the multiple-searcher, moving-target search problem. We develop an optimal branch-and-bound procedure and six heuristics for solving constrained-path problems with multiple searchers. Our optimal procedure outperforms existing approaches when used with only a single searcher. For more than one searcher, the time needed to guarantee an optimal solution is prohibitive. Our heuristics represent a wide variety of approaches: One solves partial problems optimally, two use paths based on maximizing the expected number of detections, two are genetic algorithm implementations, and one is local search with random restarts. A heuristic based on the expected number of detections obtains solutions within 2% of the best known for each one-, two-, and three-searcher test problem considered. For one- and two-searcher problems, the same heuristic's solution time is less than that of other heuristics. For three-searcher problems, a genetic algorithm implementation obtains the best-known solution in as little as 20% of other heuristic solution times. © 1996 John Wiley & Sons, Inc.     

Generation and storage dispatch in electricity networks with generator disruptions

We present methods for optimizing generation and storage decisions in an electricity network with multiple unreliable generators, each colocated with one energy storage unit (e.g., battery), and multiple loads under power flow constraints. Our model chooses the amount of energy produced by each generator and the amount of energy stored in each battery in every time period in order to minimize power generation and storage costs when each generator faces stochastic Markovian supply disruptions. This problem cannot be optimized easily using stochastic programming and/or dynamic programming approaches. Therefore, in this study, we present several heuristic methods to find an approximate optimal solution for this system. Each heuristic involves decomposing the network into several single‐generator, single‐battery, multiload systems and solving them optimally using dynamic programming, then obtaining a solution for the original problem by recombining. We discuss the computational performance of the proposed heuristics as well as insights gained from the models. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 493–511, 2015     

An analytical evaluation of optimal solution value estimation procedures

The estimation of optimal solution values for large-scale optimization problems is studied. Optimal solution value estimators provide information about the deviation between the optimal solution and the heuristic solution. Some estimation techniques combine heuristic solutions with randomly generated solutions. In particular, we examine a class of jacknife-based estimators which incorporate any heuristic solution value with the two best randomly generated solution values. The primary contribution of this article is that we provide a framework to analytically evaluate a class of optimal solution value estimators. We present closed-form results on the relationship of heuristic performance, sample size, and the estimation errors for the case where the feasible solutions are uniformly distributed. In addition, we show how to compute the estimation errors for distributions other than uniform given a specific sample size. We use a triangular and an exponential distribution as examples of other distributions. A second major contribution of this article is that, to a large extent, our analytical results confirm previous computational results. In particular, the best estimator depends on how good the heuristic is, but seems to be independent of the underlying distribution of solution values. Furthermore, there is essentially an inverse relationship between the heuristic performance and the performance of any estimator. © 1994 John Wiley & Sons, Inc.     

A heuristic for capacity expansion planning with multiple facility types

A capacity expansion model with multiple facility types is examined, where different facility types represent different quality levels. Applications for the model can be found in communications networks and production facilities. The model assumes a finite number of discrete time periods. The facilities are expanded over time. Capacity of a high-quality facility can be converted to satisfy demand for a lower-quality facility. The costs considered include capacity expansion costs and excess capacity holding costs. All cost functions are nondecreasing and concave. An algorithm that finds optimal expansion policies requires extensive computations and is practical only for small scale problems. Here, we develop a heuristic that employs so-called distributed expansion policies. It also attempts to decompose the problem into several smaller problems solved independently. The heuristic is computationally efficient. Further, it has consistently found near-optimal solutions.     

Resource allocation with lumpy demand: To speed or not to speed?

In the classical EPQ model with continuous and constant demand, holding and setup costs are minimized when the production rate is no larger than the demand rate. However, the situation may change when demand is lumpy. We consider a firm that produces multiple products, each having a unique lumpy demand pattern. The decision involves determining both the lot size for each product and the allocation of resources for production rate improvements among the products. We find that each product's optimal production policy will take on only one of two forms: either continuous production or lot‐for‐lot production. The problem is then formulated as a nonlinear nonsmooth knapsack problem among products determined to be candidates for resource allocation. A heuristic procedure is developed to determine allocation amounts. The procedure decomposes the problem into a mixed integer program and a nonlinear convex resource allocation problem. Numerical tests suggest that the heuristic performs very well on average compared to the optimal solution. Both the model and the heuristic procedure can be extended to allow the company to simultaneously alter both the production rates and the incoming demand lot sizes through quantity discounts. Extensions can also be made to address the case where a single investment increases the production rate of multiple products. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Non‐greedy heuristics and augmented neural networks for the open‐shop scheduling problem

In this paper we propose some non‐greedy heuristics and develop an Augmented‐Neural‐Network (AugNN) formulation for solving the classical open‐shop scheduling problem (OSSP). AugNN is a neural network based meta‐heuristic approach that allows integration of domain‐specific knowledge. The OSSP is framed as a neural network with multiple layers of jobs and machines. Input, output and activation functions are designed to enforce the problem constraints and embed known heuristics to generate a good feasible solution fast. Suitable learning strategies are applied to obtain better neighborhood solutions iteratively. The new heuristics and the AugNN formulation are tested on several benchmark problem instances in the literature and on some new problem instances generated in this study. The results are very competitive with other meta‐heuristic approaches, both in terms of solution quality and computational times. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

A generalization of the weighted set covering problem

We study a generalization of the weighted set covering problem where every element needs to be covered multiple times. When no set contains more than two elements, we can solve the problem in polynomial time by solving a corresponding weighted perfect b‐matching problem. In general, we may use a polynomial‐time greedy heuristic similar to the one for the classical weighted set covering problem studied by D.S. Johnson [Approximation algorithms for combinatorial problems, J Comput Syst Sci 9 (1974), 256–278], L. Lovasz [On the ratio of optimal integral and fractional covers, Discrete Math 13 (1975), 383–390], and V. Chvatal [A greedy heuristic for the set‐covering problem, Math Oper Res 4(3) (1979), 233–235] to get an approximate solution for the problem. We find a worst‐case bound for the heuristic similar to that for the classical problem. In addition, we introduce a general type of probability distribution for the population of the problem instances and prove that the greedy heuristic is asymptotically optimal for instances drawn from such a distribution. We also conduct computational studies to compare solutions resulting from running the heuristic and from running the commercial integer programming solver CPLEX on problem instances drawn from a more specific type of distribution. The results clearly exemplify benefits of using the greedy heuristic when problem instances are large. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Cost analysis and extension of a simple maintenance-scheduling heuristic

Practitioners of maintenance scheduling sometimes use a simple analytic formula, derived based on inspection scheduling, as a heuristic to determine the length of the preventive maintenance period. The sensitivity of this heuristic solution is analyzed and the cost penalties are calculated compared to the exact solution that utilizes the lifetime distribution in the derivation of the optimal preventive maintenance period. A simple extension of the heuristic is suggested to improve the approximation with a slightly increased computational effort. The sensitivity and cost analysis of the improved heuristic are discussed as well. © 1994 John Wiley & Sons, Inc.     

The single and multi‐item transshipment problem with fixed transshipment costs

This article deals with supply chain systems in which lateral transshipments are allowed. For a system with two retailers facing stochastic demand, we relax the assumption of negligible fixed transshipment costs, thus, extending existing results for the single‐item case and introducing a new model with multiple items. The goal is to determine optimal transshipment and replenishment policies, such that the total centralized expected profit of both retailers is maximized. For the single‐item problem with fixed transshipment costs, we develop optimality conditions, analyze the expected profit function, and identify the optimal solution. We extend our analysis to multiple items with joint fixed transshipment costs, a problem that has not been investigated previously in the literature, and show how the optimality conditions may be extended for any number of items. Due to the complexity involved in solving these conditions, we suggest a simple heuristic based on the single‐item results. Finally, we conduct a numerical study that provides managerial insights on the solutions obtained in various settings and demonstrates that the suggested heuristic performs very well. © 2014 Wiley Periodicals, Inc. Naval Research Logistics, 61: 637–664, 2014     

一种基于纳什议价解的自组网时隙分配策略

自组网中的分布式多节点资源分配问题为NP完全问题,一般采用启发式算法进行协议设计,缺少严格的数学证明.基于博弈与纳什议价解理论,提出了一种分布式动态时隙分配策略,并通过严格的数学推导,证明了自组网中不同节点之间的时隙竞争问题存在纳什议价解,为自组网中分布式动态时分多址信道访问控制协议的设计提供了理论依据.     

航天测控调度问题的拉格朗日启发式算法

通过分析航天测控调度问题的测控需求,建立了航天测控调度0-1整数规划模型,运用拉格朗日松弛方法对模型中的任务约束和设备约束进行了松弛,运用次梯度优化算法求得了航天测控调度问题上界,同时得到了决策变量对应的拉格朗日权重,可以作为决策变量在最优解中是否被调度的启发式信息,对拉格朗日权重进行分析,提出了求解问题可行解的拉格朗日启发式算法。最后,通过对两个场景的试验分析验证了拉格朗日启发式算法所求可行解的优越性。     

Heuristic modeling of supply availabilities in large networks

The objective of this article is to describe heuristic solutions to the problem of modeling inventories at each node of a large network in the context of a computer simulation model of that network. The heuristic solutions are compared with the mathematical solution which is too unwieldy for use in a simulation model. The Weibull cumulative distribution is used as an approximation for the heuristic models. We question whether the good performance of the Weibull is coincidence or perhaps mathematically justifiable.     

Lot sizing when yields increase during the production run

We investigate the problem of determining lot sizes for multiple items when the expected percentage of acceptable output increases with the duration of the production run, usually due to adjustments made during the early part of the production run. Such problems arise in metal stamping, textile finishing processes, and a variety of other industries. The goal is to minimize the total cost of production, inventory holding costs, and setup costs (where applicable). We develop a heuristic procedure based on a Lagrangian relaxation that differs from relaxations used in earlier studies. We use various properties of the objective function to guide the adjustment of the initial solution from the relaxation toward feasibility. Computational results indicate that, on the average, the heuristic produces solutions within 4.9% of the lower bound obtained from the Lagrangian relaxation. © 1996 John Wiley & Sons, Inc.     

Note: A local-search heuristic for large set-covering problems

In this note we describe a local-search heuristic (LSH) for large non-unicost set-covering problems (SCPs). The new heuristic is based on the simulated annealing algorithm and uses an improvement routine designed to provide low-cost solutions within a reasonable amount of CPU time. The solution costs associated with the LSH compared very favorably to the best previously published solution costs for 20 large SCPs taken from the literature. In particular, the LSH yielded new benchmark solutions for 17 of the 20 test problems. We also report that, for SCPs where column cost is correlated with column coverage, the new heuristic provides solution costs competitive with previously published results for comparable problems. © 1995 John Wiley & Sons, Inc.     

The fixed charge problem

The fixed charge problem is a nonlinear programming problem of practical interest in business and industry. Yet, until now no computationally feasible exact method of solution for large problems had been developed. In this paper an exact algorithm is presented which is computationally feasible for large problems. The algorithm is based upon a branch and bound approach, with the additional feature that the amount of computer storage required remains constant throughout (for a problem of any given size). Also presented are three suboptimal heuristic algorithms which are of interest because, although they do not guarantee that the true optimal solution will be found, they usually yield very good solutions and are extremely rapid techniques. Computational results are described for several of the heuristic methods and for the branch and bound algorithm.