A multifacility capacity expansion model with joint expansion set-up costs

This article describes a multifacility capacity expansion model in which the different facility types represent different quality levels. These facility types are used to satisfy a variety of deterministic demands over a finite number of discrete time periods. Applications for the model can be found in cable sizing problems associated with the planning of communication networks. It is assumed that the cost function associated with expanding the capacity of any facility type is concave, and that a joint set-up cost is incurred in any period in which one or more facilities are expanded. The model is formulated as a network flow problem from which properties associated with optimal solutions are derived. Using these properties, we develop a dynamic programming algorithm that finds optimal solutions for problems with a few facilities, and a heuristic algorithm that finds near-optimal solutions for larger problems. Numerical examples for both algorithms are discussed.     

The continuous‐time single‐sourcing problem with capacity expansion opportunities

This paper develops a new model for allocating demand from retailers (or customers) to a set of production/storage facilities. A producer manufactures a product in multiple production facilities, and faces demand from a set of retailers. The objective is to decide which of the production facilities should satisfy each retailer's demand, in order minimize total production, inventory holding, and assignment costs (where the latter may include, for instance, variable production costs and transportation costs). Demand occurs continuously in time at a deterministic rate at each retailer, while each production facility faces fixed‐charge production costs and linear holding costs. We first consider an uncapacitated model, which we generalize to allow for production or storage capacities. We then explore situations with capacity expansion opportunities. Our solution approach employs a column generation procedure, as well as greedy and local improvement heuristic approaches. A broad class of randomly generated test problems demonstrates that these heuristics find high quality solutions for this large‐scale cross‐facility planning problem using a modest amount of computation time. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

A network flow approach for capacity expansion problems with two facility types

A deterministic capacity expansion model for two facility types with a finite number of discrete time periods is described. The model generalizes previous work by allowing for capacity disposals, in addition to capacity expansions and conversions from one facility type to the other. Furthermore, shortages of capacity are allowed and upper bounds on both shortages and idle capacities can be imposed. The demand increments for additional capacity of any type in any time period can be negative. All cost functions are assumed to be piecewise, concave and nondecreasing away from zero. The model is formulated as a shortest path problem for an acyclic network, and an efficient search procedure is developed to determine the costs associated with the links of this network.     

A capacity-expansion model for two facility types

This paper describes a deterministic capacity-expansion model for two facility types with a finite number of discrete time periods. Capacity expansions are initialed either by new construction or by the conversion of idle capacity from one facility type to the other. Once converted, the capacity becomes an integral part of the new facility type. The costs incurred include construction, conversion, and holding costs. All cost functions are assumed to be nondecreasing and concave. Using a network flow approach, the paper develops an efficient dynamic-programming algorithm to minimize the total costs when the demands for additional capacity are nonnegative in each period. Thereafter, the algorithm is extended for arbitrary demands. The model is applied to a cable-sizing problem that occurs in communication networks, and numerical examples are discussed.     

Discrete equal‐capacity p‐median problem

This paper examines the discrete equal‐capacity p‐median problem that seeks to locate p new facilities (medians) on a network, each having a given uniform capacity, in order to minimize the sum of distribution costs while satisfying the demand on the network. Such problems arise, for example, in local access and transport area telecommunication network design problems where any number of a set of p facility units can be constructed at the specified candidate sites (hence, the net capacity is an integer multiple of a given unit capacity). We develop various valid inequalities, a separation routine for generating cutting planes that are specific members of such inequalities, as well as an enhanced reformulation that constructs a partial convex hull representation that subsumes an entire class of valid inequalities via its linear programming relaxation. We also propose suitable heuristic schemes for this problem, based on sequentially rounding the continuous relaxation solutions obtained for the various equivalent formulations of the problem. Extensive computational results are provided to demonstrate the effectiveness of the proposed valid inequalities, enhanced formulations, and heuristic schemes. The results indicate that the proposed schemes for tightening the underlying relaxations play a significant role in enhancing the performance of both exact and heuristic solution methods for this class of problems. © 2000 John & Sons, Inc. Naval Research Logistics 47: 166–183, 2000.     

Facility location models for immobile servers with stochastic demand

This paper presents several models for the location of facilities subject to congestion. Motivated by applications to locating servers in communication networks and automatic teller machines in bank systems, these models are developed for situations in which immobile service facilities are congested by stochastic demand originating from nearby customer locations. We consider this problem from three different perspectives, that of (i) the service provider (wishing to limit costs of setup and operating servers), (ii) the customers (wishing to limit costs of accessing and waiting for service), and (iii) both the service provider and the customers combined. In all cases, a minimum level of service quality is ensured by imposing an upper bound on the server utilization rate at a service facility. The latter two perspectives also incorporate queueing delay costs as part of the objective. Some cases are amenable to an optimal solution. For those cases that are more challenging, we either propose heuristic procedures to find good solutions or establish equivalence to other well‐studied facility location problems. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

A dual-based optimization procedure for the two-echelon uncapacitated facility location problem

The two-echelon uncapacitated facility location problem (TUFLP) is a generalization of the uncapacitated facility location problem (UFLP) and multiactivity facility location problem (MAFLP). In TUFLP there are two echelons of facilities through which products may flow in route to final customers. The objective is to determine the least-cost number and locations of facilities at each echelon in the system, the flow of product between facilities, and the assignment of customers to supplying facilities. We propose a new dual-based solution procedure for TUFLP that can be used as a heuristic or incorporated into branch-and-bound procedures to obtain optimal solutions to TUFLP. The algorithm is an extension of the dual ascent and adjustment procedures developed by Erlenkotter for UFLP. We report computational experience gained by solving over 420 test problems. The largest problems solved have 25 possible facility locations at each echelon and 35 customer zones, implying 650 integer variables and 21,875 continuous variables.     

An asymptotically optimal greedy heuristic for the multiperiod single‐sourcing problem: The cyclic case

The dynamics of the environment in which supply chains evolve requires that companies frequently redesign their logistics distribution networks. In this paper we address a multiperiod single‐sourcing problem that can be used as a strategic tool for evaluating the costs of logistics network designs in a dynamic environment. The distribution networks that we consider consist of a set of production and storage facilities, and a set of customers who do not hold inventories. The facilities face production capacities, and each customer's demand needs to be delivered by a single facility in each period. We deal with the assignment of customers to facilities, as well as the location, timing, and size of inventories. In addition, to mitigate start and end‐of‐study effects, we view the planning period as a typical future one, which will repeat itself. This leads to a cyclic model, in which starting and ending inventories are equal. Based on an assignment formulation of the problem, we propose a greedy heuristic, and prove that this greedy heuristic is asymptotically feasible and optimal in a probabilistic sense. We illustrate the behavior of the greedy heuristic, as well as some improvements where the greedy heuristic is used as the starting point of a local interchange procedure, on a set of randomly generated test problems. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 412–437, 2003     

The network redesign problem for access telecommunications networks

The network redesign problem attempts to design an optimal network that serves both existing and new demands. In addition to using spare capacity on existing network facilities and deploying new facilities, the model allows for rearrangement of existing demand units. As rearrangements mean reassigning existing demand units, at a cost, to different facilities, they may lead to disconnecting of uneconomical existing facilities, resulting in significant savings. The model is applied to an access network, where the demands from many sources need to be routed to a single destination, using either low‐capacity or high‐capacity facilities. Demand from any location can be routed to the destination either directly or through one other demand location. Low‐capacity facilities can be used between any pair of locations, whereas high‐capacity facilities are used only between demand locations and the destination. We present a new modeling approach to such problems. The model is described as a network flow problem, where each demand location is represented by multiple nodes associated with demands, low‐capacity and high‐capacity facilities, and rearrangements. Each link has a capacity and a cost per unit flow parameters. Some of the links also have a fixed‐charge cost. The resulting network flow model is formulated as a mixed integer program, and solved by a heuristic and a commercially available software. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 487–506, 1999     

Risk‐sensitive sizing of responsive facilities

We develop a risk‐sensitive strategic facility sizing model that makes use of readily obtainable data and addresses both capacity and responsiveness considerations. We focus on facilities whose original size cannot be adjusted over time and limits the total production equipment they can hold, which is added sequentially during a finite planning horizon. The model is parsimonious by design for compatibility with the nature of available data during early planning stages. We model demand via a univariate random variable with arbitrary forecast profiles for equipment expansion, and assume the supporting equipment additions are continuous and decided ex‐post. Under constant absolute risk aversion, operating profits are the closed‐form solution to a nontrivial linear program, thus characterizing the sizing decision via a single first‐order condition. This solution has several desired features, including the optimal facility size being eventually decreasing in forecast uncertainty and decreasing in risk aversion, as well as being generally robust to demand forecast uncertainty and cost errors. We provide structural results and show that ignoring risk considerations can lead to poor facility sizing decisions that deteriorate with increased forecast uncertainty. Existing models ignore risk considerations and assume the facility size can be adjusted over time, effectively shortening the planning horizon. Our main contribution is in addressing the problem that arises when that assumption is relaxed and, as a result, risk sensitivity and the challenges introduced by longer planning horizons and higher uncertainty must be considered. Finally, we derive accurate spreadsheet‐implementable approximations to the optimal solution, which make this model a practical capacity planning tool.© 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Strategic investment to reduce setup times in the economic lot scheduling problem

This article considers the Economic Lot Scheduling Problem where setup times and costs can be reduced by an initial investment that is amortized over time. The objective is to determine a multiple-item single facility cyclic schedule to minimize the long run average holding and setup costs plus the amortized investment. We develop a lower bound on the long run average inventory carrying and setup costs as a function of the setup times, and show that this lower bound is increasing concave on the setup times when the out-of-pocket setup costs are zero or proportional to the setup times. We then develop a model that may be helpful in deciding the magnitude and the distribution of a one-time investment in reducing the setup times when the investment is amortized over time. Numerical results based on randomly generated problems, and on Bomberger's ten item problem indicate that significant overall savings are possible for highly utilized facilities. Most of the savings are due to a significant reduction in the long run average holding cost. © 1995 John Wiley & Sons, Inc.     

Capacity allocation with machine duplication in semiconductor manufacturing

The manufacturing process for a computer chip is complex in that it involves a large number of distinct operations requiring a substantial lead‐time for completion. Our observations of such a manufacturing process at a large plant in the United States led us to identify several tactical and operational problems that were being addressed by the production planners on a recurring basis. This paper focuses on one such problem. At a tactical level, given a demand forecast of wafers to be manufactured, one specific problem deals with specifying which machine or machine groups will process different batches of wafers. We address this problem by recognizing the capacity limitations of the individual machines as well as the requirement for reducing operating and investment costs related to the machines. A mathematical model, which is a variation of the well‐known capacitated facility location problem, is proposed to solve this problem. Given the intractability of the model, we first develop problem specific lower bounding procedures based on Lagrangean relaxation. We also propose a heuristic method to obtain “good” solutions with reasonable computational effort. Computational tests, using hypothetical and industry‐based data, indicate that our heuristic approach provides optimal/near optimal solutions fairly quickly. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Multiple-facility loading under capacity-based economies of scope

Multiple-facility loading (MFL) involves the allocation of products among a set of finite-capacity facilities. Applications of MFL arise naturally in a variety of production scheduling environments. MFL models typically assume that capacity is consumed as a linear function of products assigned to a facility. Product similarities and differences, however, result in capacity-based economies or diseconomies of scope, and thus the effective capacity of the facility is often a (nonlinear) function of the set of tasks assigned to the facility. This article addresses the multiple-facility loading problem under capacity-based economies (and diseconomies) of scope (MFLS). We formulate MFLS as a nonlinear 0–1 mixed-integer programming problem, and we discuss some useful properties. MFLS generalizes many well-known combinatorial optimization problems, such as the capacitated facility location problem and the generalized assignment problem. We also define a tabu-search heuristic and a branch-and-bound algorithm for MFLS. The tabu-search heuristic alternates between two search phases, a regional search and a diversification search, and offers a novel approach to solution diversification. We also report computational experience with the procedures. In addition to demonstrating MFLS problem tractability, the computational results indicate that the heuristic is an effective tool for obtaining high-quality solutions to MFLS. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 229–256, 1997     

A general strategic capacity planning model under demand uncertainty

Capacity planning decisions affect a significant portion of future revenue. In equipment intensive industries, these decisions usually need to be made in the presence of both highly volatile demand and long capacity installation lead times. For a multiple product case, we present a continuous‐time capacity planning model that addresses problems of realistic size and complexity found in current practice. Each product requires specific operations that can be performed by one or more tool groups. We consider a number of capacity allocation policies. We allow tool retirements in addition to purchases because the stochastic demand forecast for each product can be decreasing. We present a cluster‐based heuristic algorithm that can incorporate both variance reduction techniques from the simulation literature and the principles of a generalized maximum flow algorithm from the network optimization literature. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

A class of parametric properties of transportation problems

This paper studies certain “second order” parametric relations in capacitated transportation problems. These relations concern the question of what happens to the effect of a parameter (first derivative) as another parameter is varied. These relationships have been found quite useful in the solution of many types of facility location and capacity expansion problems. The paper presents several results on the parametric behavior of the dual multipliers from which second order parametric relations can be derived.     

A generalized assignment model for dynamic supply chain capacity planning

We consider a generalization of the well‐known generalized assignment problem (GAP) over discrete time periods encompassed within a finite planning horizon. The resulting model, MultiGAP, addresses the assignment of tasks to agents within each time period, with the attendant single‐period assignment costs and agent‐capacity constraint requirements, in conjunction with transition costs arising between any two consecutive periods in which a task is reassigned to a different agent. As is the case for its single‐period antecedent, MultiGAP offers a robust tool for modeling a wide range of capacity planning problems occurring within supply chain management. We provide two formulations for MultiGAP and establish that the second (alternative) formulation provides a tighter bound. We define a Lagrangian relaxation‐based heuristic as well as a branch‐and‐bound algorithm for MultiGAP. Computational experience with the heuristic and branch‐and‐bound algorithm on over 2500 test problems is reported. The Lagrangian heuristic consistently generates high‐quality and in many cases near‐optimal solutions. The branch‐and‐bound algorithm is also seen to constitute an effective means for solving to optimality MultiGAP problems of reasonable size. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Optimal machine capacity expansions with nested limitations under stochastic demand

This paper studies capacity expansions for a production facility that faces uncertain customer demand for a single product family. The capacity of the facility is modeled in three tiers, as follows. The first tier consists of a set of upper bounds on production that correspond to different resource types (e.g., machine types, categories of manpower, etc.). These upper bounds are augmented in increments of fixed size (e.g., by purchasing machines of standard types). There is a second‐tier resource that constrains the first‐tier bounds (e.g., clean room floor space). The third‐tier resource bounds the availability of the second‐tier resource (e.g., the total floor space enclosed by the building, land, etc.). The second and third‐tier resources are expanded at various times in various amounts. The cost of capacity expansion at each tier has both fixed and proportional elements. The lost sales cost is used as a measure for the level of customer service. The paper presents a polynomial time algorithm (FIFEX) to minimize the total cost by computing optimal expansion times and amounts for all three types of capacity jointly. It accommodates positive lead times for each type. Demand is assumed to be nondecreasing in a “weak” sense. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Simultaneous price,location, and capacity decisions on a line of time‐sensitive customers

Consider a monopolist who sells a single product to time‐sensitive customers located on a line segment. Customers send their orders to the nearest distribution facility, where the firm processes (customizes) these orders on a first‐come, first‐served basis before delivering them. We examine how the monopolist would locate its facilities, set their capacities, and price the product offered to maximize profits. We explicitly model customers' waiting costs due to both shipping lead times and queueing congestion delays and allow each customer to self‐select whether she orders or not, based on her reservation price. We first analyze the single‐facility problem and derive a number of interesting insights regarding the optimal solution. We show, for instance, that the optimal capacity relates to the square root of the customer volume and that the optimal price relates additively to the capacity and transportation delay costs. We also compare our solutions to a similar problem without congestion effects. We then utilize our single‐facility results to treat the multi‐facility problem. We characterize the optimal policy for serving a fixed interval of customers from multiple facilities when customers are uniformly distributed on a line. We also show how as the length of the customer interval increases, the optimal policy relates to the single‐facility problem of maximizing expected profit per unit distance. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Spares stocking policies for repairable items with dependent repair times

This paper analyzes the problem of determining desirable spares inventory levels for repairable items with dependent repair times. The problem is important for repairable products such as aircraft engines which can have very large investment in spares inventory levels. While existing models can be used to determine optimal inventory spares levels when repair times are independent, the practical considerations of limited repair shop capacity and prioritized shop dispatching rules combine to make repair times not independent of one another. In this research a simulation model of a limited capacity repair facility with prioritized scheduling is used to explore a variety of heuristic approaches to the spares stocking decision. The heuristics are also compared with use of a model requiring independent repair times (even though that assumption is not valid here). The results show that even when repair time dependencies are present, the performance of a model which assumes independent repair times is quite good.     

Facility location and capacity acquisition: An integrated approach

The facility location and capacity acquisition decisions are intertwined, especially within the international context where capacity acquisition costs are location dependent. A review of the relevant literature however, reveals that the facility location and the capacity acquisition problems have been dealt with separately. Thus, an integrated approach for simultaneous optimization of these strategic decisions is presented. Analytical properties of the arising model are investigated and an algorithm for solving the problem is devised. Encouraging computational results are reported. © 1995 John Wiley & Sons, Inc.