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     

An optimal procedure for the coordinated replenishment dynamic lot‐sizing problem with quantity discounts

We consider in this paper the coordinated replenishment dynamic lot‐sizing problem when quantity discounts are offered. In addition to the coordination required due to the presence of major and minor setup costs, a separate element of coordination made possible by the offer of quantity discounts needs to be considered as well. The mathematical programming formulation for the incremental discount version of the extended problem and a tighter reformulation of the problem based on variable redefinition are provided. These then serve as the basis for the development of a primal‐dual based approach that yields a strong lower bound for our problem. This lower bound is then used in a branch and bound scheme to find an optimal solution to the problem. Computational results for this optimal solution procedure are reported in the paper. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 686–695, 2000     

Transportation type problems with quantity discounts

It is known to be real that the per unit transportation cost from a specific supply source to a given demand sink is dependent on the quantity shipped, so that there exist finite intervals for quantities where price breaks are offered to customers. Thus, such a quantity discount results in a nonconvex, piecewise linear functional. In this paper, an algorithm is provided to solve this problem. This algorithm, with minor modifications, is shown to encompass the “incremental” quantity discount and the “fixed charge” transportation problems as well. It is based upon a branch-and-bound solution procedure. The branches lead to ordinary transportation problems, the results of which are obtained by utilizing the “cost operator” for one branch and “rim operator” for another branch. Suitable illustrations and extensions are also provided.     

Scheduling with parallel processors and linear delay costs

This paper deals with the sequencing problem of minimizing linear delay costs with parallel identical processors. The theoretical properties of this m-machine problem are explored, and the problem of determining an optimum scheduling procedure is examined. Properties of the optimum schedule are given as well as the corresponding reductions in the number of schedules that must be evaluated in the search for an optimum. An experimental comparison of scheduling rules is reported; this indicates that although a class of effective heuristics can be identified, their relative behavior is difficult to characterize.     

An efficient metaheuristic for integrated scheduling and staffing IT projects based on a generalized minimum cost flow network

Scheduling IT projects and assigning the project work to human resources are an important and common tasks in almost any IT service company. It is particularly complex because human resources usually have multiple skills. Up to now only little work has considered IT‐specific properties of the project structure and human resources. In this article, we present an optimization model that simultaneously schedules the activities of multiple IT projects with serial network structures and assigns the project work to multiskilled internal and external human resources with different efficiencies. The goal is to minimize costs. We introduce a metaheuristic that decomposes the problem into a binary scheduling problem and a continuous staffing problem where the latter is solved efficiently by exploiting its underlying network structure. For comparison, we solve the mixed–binary linear program with a state–of–the–art commercial solver. The impacts of problem parameters on computation time and solution gaps between the metaheuristic and the solver are assessed in an experimental study. Our results show that the metaheuristic provides very favorable results in considerable less time than the solver for midsize problems. For larger problems, it shows a similar performance while the solver fails to return feasible solutions. © 2012 Wiley Periodicals, Inc. Naval Research Logistics 59: 111–127, 2012     

融合战术与修正物理特征的空中目标战术类型识别

针对敌方飞行器隐身、伪装技术的日趋成熟,致使我方由侦察设备获取的电磁信号严重变形,特别是物理特征在目标类型识别中的作用日趋减弱的现实问题,提出了一种融合目标战术特征修正物理特征证据的目标战术类型识别方法。该方法从目标战术类型识别的军事需求出发,提出对冲突物理特征证据的阶梯式修正规则,以及对冲突证据折扣因子的优化方法,并将修正后的证据重新组合得到识别结果。仿真实例证明该方法在处理目标冲突物理特征证据时具有高准确率的特点。该方法为复杂环境下的目标战术类型识别问题提供一种新的解决思路。     

Cyclic preference scheduling for nurses using branch and price

This paper presents a new methodology to solve the cyclic preference scheduling problem for hourly workers. The focus is on nurse rostering but is applicable to any organization in which the midterm scheduling decision must take into account a complex of legal, institutional, and preferential constraints. The objective is to strike a balance between satisfying individual preferences and minimizing personnel costs. The common practice is to consider each planning period independently and to generate new rosters at the beginning of each. To reduce some of the instability in the process, there is a growing trend toward cyclic schedules, which are easier to manage and are generally perceived to be more equitable. To address this problem, a new integer programming model is presented that combines the elements of both cyclic and preference scheduling. To find solutions, a branch‐and‐price algorithm is developed that makes use of several branching rules and an extremely effective rounding heuristic. A unique feature of the formulation is that the master problem contains integer rather than binary variables. Computational results are reported for problem instances with up to 200 nurses. Most were solved within 10 minutes and many within 3 minutes when a double aggregation approach was applicable. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007.     

A bayesian approach to evaluating military investments in product improvement and testing

Two issues of frequent importance in new product development are product improvement and reliability testing. A question often faced by the developer is: Should the product be distributed in its present state, or should it be improved further and/or tested before distribution? A more useful statement of the question might be: What levels of investment in further improvement and testing are economically permissible? Products for which this question is relevant may vary widely in type and intended use. This paper presents a model for determining these levels for one such product—an equipment modification procedure. The model presented makes use of present value analysis to compare cost streams and of Bayesian statistics to relate the costs to various outcomes under conditions of uncertainty. The model is applied to an actual military problem and a method is described for examining the sensitivity of the results to changes in the prior probabilities and discount rate.     

Minimizing mean absolute deviation of completion times about a common due date

We consider a single machine scheduling problem in which the objective is to minimize the mean absolute deviation of job completion times about a common due date. We present an algorithm for determining multiple optimal schedules under restrictive assumptions about the due date, and an implicit enumeration procedure when the assumptions do not hold. We also establish the similarity of this problem to the two parallel machines mean flow time problem.     

An easy solution for a special class of fixed charge problems

The fixed charge problem is a mixed integer mathematical programming problem which has proved difficult to solve in the past. In this paper we look at a special case of that problem and show that this case can be solved by formulating it as a set-covering problem. We then use a branch-and-bound integer programming code to solve test fixed charge problems using the setcovering formulation. Even without a special purpose set-covering algorithm, the results from this solution procedure are dramatically better than those obtained using other solution procedures.     

Simultaneous determination of production and maintenance schedules using in‐line equipment condition and yield information

In many manufacturing environments, equipment condition has a significant impact on product quality, or yield. This paper presents a semi‐Markov decision process model of a single‐stage production system with multiple products and multiple maintenance actions. The model simultaneously determines maintenance and production schedules, accounting for the fact that equipment condition affects the yield of each product differently. It extends earlier work by allowing the expected time between decision epochs to vary by both action and machine state, by allowing multiple maintenance actions, and by treating the outcome of maintenance as less than certain. Sufficient conditions are developed that ensure the monotonicity of both the optimal production and maintenance actions. While the maintenance conditions closely resemble previously studied conditions for this type of problem, the production conditions represent a significant departure from earlier results. The simultaneous solution method is compared to an approach commonly used in industry, where the maintenance and production problems are treated independently. Solving more than one thousand test problems confirms that the combination of both features of the model—accounting for product differences and solving the problems simultaneously—has a significant impact on performance. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Bicriteria product design optimization: An efficient solution procedure using AND/OR trees

Competitive imperatives are causing manufacturing firms to consider multiple criteria when designing products. However, current methods to deal with multiple criteria in product design are ad hoc in nature. In this paper we present a systematic procedure to efficiently solve bicriteria product design optimization problems. We first present a modeling framework, the AND/OR tree, which permits a simplified representation of product design optimization problems. We then show how product design optimization problems on AND/OR trees can be framed as network design problems on a special graph—a directed series‐parallel graph. We develop an enumerative solution algorithm for the bicriteria problem that requires as a subroutine the solution of the parametric shortest path problem. Although this parametric problem is hard on general graphs, we show that it is polynomially solvable on the series‐parallel graph. As a result we develop an efficient solution algorithm for the product design optimization problem that does not require the use of complex and expensive linear/integer programming solvers. As a byproduct of the solution algorithm, sensitivity analysis for product design optimization is also efficiently performed under this framework. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 574–592, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10031     

Client‐contractor bargaining on net present value in project scheduling with limited resources

The client‐contractor bargaining problem addressed here is in the context of a multi‐mode resource constrained project scheduling problem with discounted cash flows, which is formulated as a progress payments model. In this model, the contractor receives payments from the client at predetermined regular time intervals. The last payment is paid at the first predetermined payment point right after project completion. The second payment model considered in this paper is the one with payments at activity completions. The project is represented on an Activity‐on‐Node (AON) project network. Activity durations are assumed to be deterministic. The project duration is bounded from above by a deadline imposed by the client, which constitutes a hard constraint. The bargaining objective is to maximize the bargaining objective function comprised of the objectives of both the client and the contractor. The bargaining objective function is expected to reflect the two‐party nature of the problem environment and seeks a compromise between the client and the contractor. The bargaining power concept is introduced into the problem by the bargaining power weights used in the bargaining objective function. Simulated annealing algorithm and genetic algorithm approaches are proposed as solution procedures. The proposed solution methods are tested with respect to solution quality and solution times. Sensitivity analyses are conducted among different parameters used in the model, namely the profit margin, the discount rate, and the bargaining power weights. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

The capital supply curve in capacity expansion models: Some economic and algorithmic aspects

Capacity expansion models typically minimize the discounted cost of acquisition and operation over a given planning horizon. In this article we generalize this idea to one in which a capital supply curve replaces the usual discount rate. A capital supply curve is a means to model financial outlook, investment limits, and risk. We show that when such a curve is included in a capacity expansion model, it will, under certain conditions, provide a less capital intensive solution than one which incorporates a discount rate. In this article, we also provide an algorithm that solves capacity expansion models that incorporate a capital supply curve. The attractive feature of this algorithm is that it provides a means to utilize the “discount rate” models efficiently. Throughout, we give applications in power generation planning and computational experience for this application is also presented.     

A node covering algorithm

This paper describes a node covering algorithm, i.e., a procedure for finding a smallest set of nodes covering all edges of an arbitrary graph. The algorithm is based on the concept of a dual node-clique set, which allows us to identify partial covers associated with integer dual feasible solutions to the linear programming equivalent of the node covering problem. An initial partial cover with the above property is first found by a labeling procedure. Another labeling procedure then successively modifies the dual node-clique set, so that more and more edges are covered, i.e., the (primal) infeasibility of the solution is gradually reduced, while integrality and dual feasibility are preserved. When this cannot be continued, the problem is partitioned and the procedure applied to the resulting subproblems. While the steps of the algorithm correspond to sequences of dual simplex pivots, these are carried out implicitly, by labeling. The procedure is illustrated by examples, and some early computational experience is reported. We conclude with a discussion of potential improvements and extensions.     

Quantity discount pricing policies for heterogeneous retailers with price sensitive demand

Although quantity discount policies have been extensively analyzed, they are not well understood when there are many different buyers. This is especially the case when buyers face price‐sensitive demand. In this paper we study a supplier's optimal quantity discount policy for a group of independent and heterogeneous retailers, when each retailer faces a demand that is a decreasing function of its retail price. The problem is analyzed as a Stackelberg game whereby the supplier acts as the leader and buyers act as followers. We show that a common quantity discount policy that is designed according to buyers' individual cost and demand structures and their rational economic behavior is able to significantly stimulate demand, improve channel efficiency, and substantially increase profits for both the supplier and buyers. Furthermore, we show that the selection of all‐units or incremental quantity discount policies has no effect on the benefits that can be obtained from quantity discounts. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Determination of suppliers' optimal quantity discount schedules with heterogeneous buyers

Although the quantity discount problem has been extensively studied in the realm of a single supplier and a single buyer, it is not well understood when a supplier has many different buyers. This paper presents an analysis of a supplier's quantity discount decision when there are many buyers with different demand and cost structures. A common discrete all‐unit quantity discount schedule with many break points is used. After formulating the model, we first analyze buyers' responses to a general discrete quantity discount schedule. This analysis establishes a framework for a supplier to formulate his quantity discount decision. Under this framework, the supplier's optimal quantity discount schedule can be formulated and solved by a simple non‐linear programming model. The applicability of the model is discussed with an application for a large U.S. distribution network. © 2002 John Wiley & Sons, Inc. Naval Research Logistics, 49: 46–59, 2002; DOI 10.1002/nav.1052     

A branch‐and‐price approach for the stochastic generalized assignment problem

In this article, we address a stochastic generalized assignment machine scheduling problem in which the processing times of jobs are assumed to be random variables. We develop a branch‐and‐price (B&P) approach for solving this problem wherein the pricing problem is separable with respect to each machine, and has the structure of a multidimensional knapsack problem. In addition, we explore two other extensions of this method—one that utilizes a dual‐stabilization technique and another that incorporates an advanced‐start procedure to obtain an initial feasible solution. We compare the performance of these methods with that of the branch‐and‐cut (B&C) method within CPLEX. Our results show that all B&P‐based approaches perform better than the B&C method, with the best performance obtained for the B&P procedure that includes both the extensions aforementioned. We also utilize a Monte Carlo method within the B&P scheme, which affords the use of a small subset of scenarios at a time to estimate the “true” optimal objective function value. Our experimental investigation reveals that this approach readily yields solutions lying within 5% of optimality, while providing more than a 10‐fold savings in CPU times in comparison with the best of the other proposed B&P procedures. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 131–143, 2014     

Capacitated lot‐sizing and scheduling with parallel machines,back‐orders,and setup carry‐over

We address the capacitated lot‐sizing and scheduling problem with setup times, setup carry‐over, back‐orders, and parallel machines as it appears in a semiconductor assembly facility. The problem can be formulated as an extension of the capacitated lot‐sizing problem with linked lot‐sizes (CLSPL). We present a mixed integer (MIP) formulation of the problem and a new solution procedure. The solution procedure is based on a novel “aggregate model,” which uses integer instead of binary variables. The model is embedded in a period‐by‐period heuristic and is solved to optimality or near‐optimality in each iteration using standard procedures (CPLEX). A subsequent scheduling routine loads and sequences the products on the parallel machines. Six variants of the heuristic are presented and tested in an extensive computational study. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Interchange fee rate,merchant discount rate,and retail price in a credit card network: A game‐theoretic analysis

We consider two game‐theoretic settings to determine the optimal values of an issuer's interchange fee rate, an acquirer's merchant discount rate, and a merchant's retail price in a credit card network. In the first setting, we investigate a two‐stage game problem in which the issuer and the acquirer first negotiate the interchange fee rate, and the acquirer and the retailer then determine their merchant discount rate and retail price, respectively. In the second setting, motivated by the recent US bill “H.R. 2695,” we develop a three‐player cooperative game in which the issuer, the acquirer, and the merchant form a grand coalition and bargain over the interchange fee rate and the merchant discount rate. Following the cooperative game, the retailer makes its retail pricing decision. We derive both the Shapley value‐ and the nucleolus‐characterized, and globally‐optimal unique rates for the grand coalition. Comparing the two game settings, we find that the participation of the merchant in the negotiation process can result in the reduction of both rates. Moreover, the stability of the grand coalition in the cooperative game setting may require that the merchant should delegate the credit card business only to the issuer and the acquirer with sufficiently low operation costs. We also show that the grand coalition is more likely to be stable and the U.S. bill “H.R. 2695” is thus more effective, if the degree of division of labor in the credit card network is higher as the merchant, acquirer, and issuer are more specialized in the retailing, acquiring, and issuing operations, respectively. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012