Approximation algorithms for general one‐warehouse multi‐retailer systems

Logistical planning problems are complicated in practice because planners have to deal with the challenges of demand planning and supply replenishment, while taking into account the issues of (i) inventory perishability and storage charges, (ii) management of backlog and/or lost sales, and (iii) cost saving opportunities due to economies of scale in order replenishment and transportation. It is therefore not surprising that many logistical planning problems are computationally difficult, and finding a good solution to these problems necessitates the development of many ad hoc algorithmic procedures to address various features of the planning problems. In this article, we identify simple conditions and structural properties associated with these logistical planning problems in which the warehouse is managed as a cross‐docking facility. Despite the nonlinear cost structures in the problems, we show that a solution that is within ε‐optimality can be obtained by solving a related piece‐wise linear concave cost multi‐commodity network flow problem. An immediate consequence of this result is that certain classes of logistical planning problems can be approximated by a factor of (1 + ε) in polynomial time. This significantly improves upon the results found in literature for these classes of problems. We also show that the piece‐wise linear concave cost network flow problem can be approximated to within a logarithmic factor via a large scale linear programming relaxation. We use polymatroidal constraints to capture the piece‐wise concavity feature of the cost functions. This gives rise to a unified and generic LP‐based approach for a large class of complicated logistical planning problems. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Rank‐Cluster‐and‐Prune: An algorithm for generating clusters in complex set partitioning problems

Clustering problems are often difficult to solve due to nonlinear cost functions and complicating constraints. Set partitioning formulations can help overcome these challenges, but at the cost of a very large number of variables. Therefore, techniques such as delayed column generation must be used to solve these large integer programs. The underlying pricing problem can suffer from the same challenges (non‐linear cost, complicating constraints) as the original problem, however, making a mathematical programming approach intractable. Motivated by a real‐world problem in printed circuit board (PCB) manufacturing, we develop a search‐based algorithm (Rank‐Cluster‐and‐Prune) as an alternative, present computational results for the PCB problem to demonstrate the tractability of our approach, and identify a broader class of clustering problems for which this approach can be used. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Robust capacity planning in semiconductor manufacturing

We present a stochastic programming approach to capacity planning under demand uncertainty in semiconductor manufacturing. Given multiple demand scenarios together with associated probabilities, our aim is to identify a set of tools that is a good compromise for all these scenarios. More precisely, we formulate a mixed‐integer program in which expected value of the unmet demand is minimized subject to capacity and budget constraints. This is a difficult two‐stage stochastic mixed‐integer program which cannot be solved to optimality in a reasonable amount of time. We instead propose a heuristic that can produce near‐optimal solutions. Our heuristic strengthens the linear programming relaxation of the formulation with cutting planes and performs limited enumeration. Analyses of the results in some real‐life situations are also presented. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

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 generic model of motor‐carrier fuel optimization

Fuel optimizers are decision models (software products) that are increasingly recognized as effective fuel management tools by U.S. truckload carriers. Using the latest price data of every truck stop, these models calculate the optimal fueling schedule for each route that indicates: (i) which truck stop(s) to use, and (ii) how much fuel to buy at the chosen truck stop(s) to minimize the refueling cost. In the current form, however, these models minimize only the fuel cost, and ignore or underestimate other costs that are affected by the models' decision variables. On the basis of the interviews with carrier managers, truck drivers, and fuel‐optimizer vendors, this article proposes a comprehensive model of motor‐carrier fuel optimization that considers all of the costs that are affected by the model's decision variables. Simulation results imply that the proposed model not only attains lower vehicle operating costs than the commercial fuel optimizers, but also gives solutions that are more desirable from the drivers' viewpoint. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Stochastic call center staffing with uncertain arrival,service and abandonment rates: A Bayesian perspective

In this article, we introduce staffing strategies for the Erlang‐A queuing system in call center operations with uncertain arrival, service, and abandonment rates. In doing so, we model the system rates using gamma distributions that create randomness in operating characteristics used in the optimization formulation. We divide the day into discrete time intervals where a simulation based stochastic programming method is used to determine staffing levels. More specifically, we develop a model to select the optimal number of agents required for a given time interval by minimizing an expected cost function, which consists of agent and abandonment (opportunity) costs, while considering the service quality requirements such as the delay probability. The objective function as well as the constraints in our formulation are random variables. The novelty of our approach is to introduce a solution method for the staffing of an operation where all three system rates (arrival, service, and abandonment) are random variables. We illustrate the use of the proposed model using both real and simulated call center data. In addition, we provide solution comparisons across different formulations, consider a dynamic extension, and discuss sensitivity implications of changing constraint upper bounds as well as prior hyper‐parameters. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 460–478, 2016     

On the reduction of total‐cost and average‐cost MDPs to discounted MDPs

This article provides conditions under which total‐cost and average‐cost Markov decision processes (MDPs) can be reduced to discounted ones. Results are given for transient total‐cost MDPs with transition rates whose values may be greater than one, as well as for average‐cost MDPs with transition probabilities satisfying the condition that there is a state such that the expected time to reach it is uniformly bounded for all initial states and stationary policies. In particular, these reductions imply sufficient conditions for the validity of optimality equations and the existence of stationary optimal policies for MDPs with undiscounted total cost and average‐cost criteria. When the state and action sets are finite, these reductions lead to linear programming formulations and complexity estimates for MDPs under the aforementioned criteria.© 2017 Wiley Periodicals, Inc. Naval Research Logistics 66:38–56, 2019     

Dynamic capacity reservation and due date quoting in a make‐to‐order system

We consider a make‐to‐order manufacturer facing random demand from two classes of customers. We develop an integrated model for reserving capacity in anticipation of future order arrivals from high priority customers and setting due dates for incoming orders. Our research exhibits two distinct features: (1) we explicitly model the manufacturer's uncertainty about the customers' due date preferences for future orders; and (2) we utilize a service level measure for reserving capacity rather than estimating short and long term implications of due date quoting with a penalty cost function. We identify an interesting effect (“t‐pooling”) that arises when the (partial) knowledge of customer due date preferences is utilized in making capacity reservation and order allocation decisions. We characterize the relationship between the customer due date preferences and the required reservation quantities and show that not considering the t‐pooling effect (as done in traditional capacity and inventory rationing literature) leads to excessive capacity reservations. Numerical analyses are conducted to investigate the behavior and performance of our capacity reservation and due date quoting approach in a dynamic setting with multiple planning horizons and roll‐overs. One interesting and seemingly counterintuitive finding of our analyses is that under certain conditions reserving capacity for high priority customers not only improves high priority fulfillment, but also increases the overall system fill rate. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Reformulating linear programs with transportation constraints—With applications to workforce scheduling

We study linear programming models that contain transportation constraints in their formulation. Typically, these models have a multistage nature and the transportation constraints together with the associated flow variables are used to achieve consistency between consecutive stages. We describe how to reformulate these models by projecting out the flow variables. The reformulation can be more desirable since it has fewer variables and can be solved faster. We apply these ideas to reformulate two well‐known workforce staffing and scheduling problems: the shift scheduling problem and the tour scheduling problem. We also present computational results. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

A branch‐and‐bound‐based solution approach for dynamic rerouting of airborne platforms

This article is a sequel to a recent article that appeared in this journal, “An extensible modeling framework for dynamic reassignment and rerouting in cooperative airborne operations” [ 17 ], in which an integer programming formulation to the problem of rescheduling in‐flight assets due to changes in battlespace conditions was presented. The purpose of this article is to present an improved branch‐and‐bound procedure to solve the dynamic resource management problem in a timely fashion, as in‐flight assets must be quickly re‐tasked to respond to the changing environment. To facilitate the rapid generation of attractive updated mission plans, this procedure uses a technique for reducing the solution space, supports branching on multiple decision variables simultaneously, incorporates additional valid cuts to strengthen the minimal network constraints of the original mathematical model, and includes improved objective function bounds. An extensive numerical analysis indicates that the proposed approach significantly outperforms traditional branch‐and‐bound methodologies and is capable of providing improved feasible solutions in a limited time. Although inspired by the dynamic resource management problem in particular, this approach promises to be an effective tool for solving other general types of vehicle routing problems. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

A selective newsvendor approach to order management

Consider a supplier offering a product to several potential demand sources, each with a unique revenue, size, and probability that it will materialize. Given a long procurement lead time, the supplier must choose the orders to pursue and the total quantity to procure prior to the selling season. We model this as a selective newsvendor problem of maximizing profits where the total (random) demand is given by the set of pursued orders. Given that the dimensionality of a mixed‐integer linear programming formulation of the problem increases exponentially with the number of potential orders, we develop both a tailored exact algorithm based on the L‐shaped method for two‐stage stochastic programming as well as a heuristic method. We also extend our solution approach to account for piecewise‐linear cost and revenue functions as well as a multiperiod setting. Extensive experimentation indicates that our exact approach rapidly finds optimal solutions with three times as many orders as a state‐of‐the‐art commercial solver. In addition, our heuristic approach provides average gaps of less than 1% for the largest problems that can be solved exactly. Observing that the gaps decrease as problem size grows, we expect the heuristic approach to work well for large problem instances. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2008     

A continuous‐time strategic capacity planning model

Capacity planning decisions affect a significant portion of future revenue. In the semiconductor industry, they need to be made in the presence of both highly volatile demand and long capacity installation lead‐times. In contrast to traditional discrete‐time models, we present a continuous‐time stochastic programming model for multiple resource types and product families. We show how this approach can solve capacity planning problems of reasonable size and complexity with provable efficiency. This is achieved by an application of the divide‐and‐conquer algorithm, convexity, submodularity, and the open‐pit mining problem. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

An integer decomposition algorithm for solving a two‐stage facility location problem with second‐stage activation costs

We study a stochastic scenario‐based facility location problem arising in situations when facilities must first be located, then activated in a particular scenario before they can be used to satisfy scenario demands. Unlike typical facility location problems, fixed charges arise in the initial location of the facilities, and then in the activation of located facilities. The first‐stage variables in our problem are the traditional binary facility‐location variables, whereas the second‐stage variables involve a mix of binary facility‐activation variables and continuous flow variables. Benders decomposition is not applicable for these problems due to the presence of the second‐stage integer activation variables. Instead, we derive cutting planes tailored to the problem under investigation from recourse solution data. These cutting planes are derived by solving a series of specialized shortest path problems based on a modified residual graph from the recourse solution, and are tighter than the general cuts established by Laporte and Louveaux for two‐stage binary programming problems. We demonstrate the computational efficacy of our approach on a variety of randomly generated test problems. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Incorporating learning curve costs in acquisition strategy optimization

Each year, the U.S. Army procures billions of dollars worth of weapons and equipment. The process of deciding what to buy, when to buy, and in what quantities is extremely complex, requiring extensive analysis. Two techniques used in this analysis are mathematical programming and cost estimation. Although they are related through constraints on available procurement funds, the use of nonlinear cost learning curves, which better represent system costs as a function of quantity produced, have not been incorporated into the mathematical programming formulations that compute the quantities of items to be procured. As a result, the solutions obtained could be either suboptimal, or even infeasible with respect to budgetary limitations. In this paper we present a piecewise linear approximation of the learning curve costs for a more accurate portrayal of budgetary constraints used in a mixed integer linear programming for acquisition strategy optimization. In addition, implementation issues are discussed, and performance results are given. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 255–271, 1999     

Column generation for stochastic green telecommunication network planning with switchable base stations

We present the green telecommunication network planning problem with switchable base stations, where the location and configuration of the base stations are optimized, while taking into account uncertainty and variability of demand. The problem is formulated as a two‐stage stochastic program under demand uncertainty with integers in both stages. Since solving the presented problem is computationally challenging, we develop the corresponding Dantzig‐Wolfe reformulation and propose a solution approach based on column generation. Comprehensive computational results are provided for instances of varying characteristics. The results show that the joint location and dynamic switching of base stations leads to significant savings in terms of energy cost. Up to 30% reduction in power consumption cost is achieved while still serving all users. In certain cases, allowing dynamic configurations leads to more installed base stations and higher user coverage, while having lower total energy consumption. The Dantzig‐Wolfe reformulation provides solutions with a tight LP‐gap eliminating the need for a full branch‐and‐price scheme. Furthermore, the proposed column generation solution approach is computationally efficient and outperforms CPLEX on the majority of the tested instances. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 351–366, 2016     

Exact algorithms for integrated facility location and production planning problems

We consider a class of facility location problems with a time dimension, which requires assigning every customer to a supply facility in each of a finite number of periods. Each facility must meet all assigned customer demand in every period at a minimum cost via its production and inventory decisions. We provide exact branch‐and‐price algorithms for this class of problems and several important variants. The corresponding pricing problem takes the form of an interesting class of production planning and order selection problems. This problem class requires selecting a set of orders that maximizes profit, defined as the revenue from selected orders minus production‐planning‐related costs incurred in fulfilling the selected orders. We provide polynomial‐time dynamic programming algorithms for this class of pricing problems, as well as for generalizations thereof. Computational testing indicates the advantage of our branch‐and‐price algorithm over various approaches that use commercial software packages. These tests also highlight the significant cost savings possible from integrating location with production and inventory decisions and demonstrate that the problem is rather insensitive to forecast errors associated with the demand streams. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Demand shuffle—A method for multilevel proportional lot sizing and scheduling

This contribution acquaints the reader with a model for multilevel single-machine proportional lot sizing and scheduling problems (PLSPs) that appear in the scope of short-term production planning. It is one of the first articles that deals with dynamic capacitated multilevel lot sizing and scheduling, which is of great practical importance. The PLSP model refines well-known mixed-integer programming formulations for dynamic capacitated lot sizing and scheduling as, for instance, the DLSP or the CSLP. A special emphasis is given on a new method called demand shuffle to solve multilevel PLSP instances efficiently but suboptimally. Although the basic idea is very simple, it becomes clear that in the presence of precedence and capacity constraints many nontrivial details are to be concerned. Computational studies show that the presented approach decidedly improves recent results. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 319–340, 1997     

Chance‐constrained multi‐terminal network design problems

We consider a reliable network design problem under uncertain edge failures. Our goal is to select a minimum‐cost subset of edges in the network to connect multiple terminals together with high probability. This problem can be seen as a stochastic variant of the Steiner tree problem. We propose two scenario‐based Steiner cut formulations, study the strength of the proposed valid inequalities, and develop a branch‐and‐cut solution method. We also propose an LP‐based separation for the scenario‐based directed Steiner cut inequalities using Benders feasibility cuts, leveraging the success of the directed Steiner cuts for the deterministic Steiner tree problem. In our computational study, we test our branch‐and‐cut method on instances adapted from graphs in SteinLib Testdata Library with up to 100 nodes, 200 edges, and 17 terminals. The performance of our branch‐and‐cut method demonstrates the strength of the scenario‐based formulations and the benefit from adding the additional valid inequalities that we propose. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 321–334, 2015     

The parallel replacement problem with demand and capital budgeting constraints

A generalized parallel replacement problem is considered with both fixed and variable replacement costs, capital budgeting, and demand constraints. The demand constraints specify that a number of assets, which may vary over time, are required each period over a finite horizon. A deterministic, integer programming formulation is presented as replacement decisions must be integer. However, the linear programming relaxation is shown to have integer extreme points if the economies of scale binary variables are fixed. This allows for the efficient computation of large parallel replacement problems as only a limited number of 0–1 variables are required. Examples are presented to provide insight into replacement rules, such as the “no‐splitting‐rule” from previous research, under various demand scenarios. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 40–56, 2000     

Crane scheduling with spatial constraints

In this work, we examine port crane scheduling with spatial and separation constraints. Although common to most port operations, these constraints have not been previously studied. We assume that cranes cannot cross, there is a minimum distance between cranes and jobs cannot be done simultaneously. The objective is to find a crane‐to‐job matching which maximizes throughput under these constraints. We provide dynamic programming algorithms, a probabilistic tabu search, and a squeaky wheel optimization heuristic for solution. Experiments show the heuristics perform well compared with optimal solutions obtained by CPLEX for small scale instances where a squeaky wheel optimization with local search approach gives good results within short times. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.