An integrated approach to dynamic plant location and capacity planning

We consider a dynamic capacitated plant location problem in which capacities of opened plants are determined by acquisition and/or disposal of multiple types of facilities. We determine the opening schedule of plants, allocations of customers' demands and plans for acquisition and/or disposal of plant capacities that minimise the sum of discounted fixed costs for opening plants, delivery costs of products, and acquisition and operation costs of facilities. The dynamic capacitated plant location problem is formulated as a mixed integer linear program and solved by a heuristic algorithm based on Lagrangian relaxation and a cut and branch algorithm which uses Gomory cuts. Several solution properties of the relaxed problem are found and used to develop efficient solution procedures for the relaxed problem. A subgradient optimisation method is employed to obtain better lower bounds. The heuristic algorithm is tested on randomly generated test problems and results show that the algorithm finds good solutions in a reasonable amount of computation time.     

Locational analysis

For our purposes, locational analysis is the formulation and solution of location problems. We consider locational analysis which is carried out by the construction and solution of locational models. Such models typically involve locating one or more new facilities, and may include transport costs, fixed costs, constraints on the number of new facilities, upper bounds on distances between new and existing facilities, as well as determining amounts to be shipped between new and existing facilities.We give a selective review of the locational analysis literature, concentrating on models which have been thoroughly tested, and which can be solved by ‘reliable algorithms’. For convenience, we consider four classes of locational models: planar models, warehousing models, network models, and discrete, or mixed-integer programming, models.     

A combinatorial approach to level of repair analysis

This paper presents an approach to optimise level of repair decisions taking into account submodular properties of standard life cycle cost functions, which include fixed and variable costs. It proposes an integer programming formulation to solve level of repair problems for multi-echelon multi-indenture level systems. The method converges quickly to the optimum solution relying on heuristics to obtain tight bounds for a subsequent branch-and-bound procedure. A software package called level of repair optimisation model (LOROM) was developed to implement the branch-and-bound method that does not rely on linear programming relaxations. This approach is rather generic and can be applied to a wide class of problems with convex total cost functions such as plant location problems or transportation problems with fixed costs.     

Dominance Criteria for the Capacitated Warehouse Location Problem

The paper examines the capacitated warehouse location problem where fixed costs, generally relating to the installation of warehouses and variable costs, consisting mainly of transportation costs, are minimized. The minimization of each kind of cost drives the solution towards opposite directions with respect to the number of warehouses to be opened/closed. Therefore, dominance criteria between fixed and variable costs are examined. This leads to exact tests as well as greedy heuristics, the latter known in the literature as ADD/DROP techniques.     

A production-transportation problem with stochastic demand and concave production costs

Well known extensions of the classical transportation problem are obtained by including fixed costs for the production of goods at the supply points (facility location) and/or by introducing stochastic demand, modeled by convex nonlinear costs, at the demand points (the stochastic transportation problem, [STP]). However, the simultaneous use of concave and convex costs is not very well treated in the literature. Economies of scale often yield concave cost functions other than fixed charges, so in this paper we consider a problem with general concave costs at the supply points, as well as convex costs at the demand points. The objective function can then be represented as the difference of two convex functions, and is therefore called a d.c. function. We propose a solution method which reduces the problem to a d.c. optimization problem in a much smaller space, then solves the latter by a branch and bound procedure in which bounding is based on solving subproblems of the form of [STP]. We prove convergence of the method and report computational tests that indicate that quite large problems can be solved efficiently. Problems up to the size of 100 supply points and 500 demand points are solved. Received October 11, 1993 / Revised version received July 31, 1995 Published online November 24, 1998     

Simulated N-Body: New Particle Physics-Based Heuristics for a Euclidean Location-Allocation Problem

The general facility location problem and its variants, including most location-allocation and P-median problems, are known to be NP-hard combinatorial optimization problems. Consequently, there is now a substantial body of literature on heuristic algorithms for a variety of location problems, among which can be found several versions of the well-known simulated annealing algorithm. This paper presents an optimization paradigm that, like simulated annealing, is based on a particle physics analogy but is markedly different from simulated annealing. Two heuristics based on this paradigm are presented and compared to simulated annealing for a capacitated facility location problem on Euclidean graphs. Experimental results based on randomly generated graphs suggest that one of the heuristics outperforms simulated annealing both in cost minimization as well as execution time. The particular version of location problem considered here, a location-allocation problem, involves determining locations and associated regions for a fixed number of facilities when the region sizes are given. Intended applications of this work include location problems with congestion costs as well as graph and network partitioning problems.     

Plant location and procurement planning in knockdown production systems

We consider an integrated problem of plant location and capacity planning for components procurement in knockdown production systems. The problem is that of determining the schedule of opening components manufacturing plants, plans for acquisition of capacities in opened components manufacturing plants, and plans for components procurement in final assembly plants with the objective of minimizing the sum of fixed costs for opening plants, acquisition and operation costs of facilities, and delivery and subcontracting costs of components. The problem is formulated as a mixed integer linear program and solved by a two-stage solution procedure. In the solution procedure, the problem is decomposed into two tractable subproblems and these subproblems are solved sequentially. In the first stage, a dynamic plant location problem is solved using a cut and branch algorithm based on Gomory cuts, while a multiperiod capacity planning problem is solved in the second stage by a heuristic algorithm that uses a cut and branch algorithm and a variable reduction scheme. The solution procedure is tested on problems of a practical size and results show that the procedure gives reasonably good solutions.     

Warehouse location with production,inventory, and distribution decisions: a case study in the lube oil industry

In this paper, a supply chain management problem from a real case study is modeled and solved. A company in Pakistan wanted to outsource part of its warehousing activity to a third party logistics (3PL) provider. Consequently, the company had to decide on where to rent space in the 3PL warehouses. Knowing that such a strategic decision is affected by tactical and operational decisions, the problem is presented as a facility location problem integrating production, inventory, and distribution decisions. The problem is formulated as a mixed integer linear programming model which minimizes the total cost composed of location, distribution, production, and inventory costs. Several constraints specific to the situation and policy of the company were considered. A thorough analysis was done on the results obtained with respect to formulation efficiency, sensitivity analysis, and distribution of costs. In addition to the solution of the company problem, a set of 1215 problem instances was generated by varying five types of relevant costs in a full factorial manner. The solution of the generated problems always suggests to open in the same two locations and the integrality gaps averaged 0.062 % with a maximum of 0.102 %. On average, the major components of the total cost are production cost (96.6 %), transportation costs (2.7 %), and inventory holding costs (0.38 %). The total warehouse opening cost accounted for less than 0.05 % of the total costs.     

Die Bestimmung des optimalen Standorts eines Auslieferungslagers bei entfernungsabhängiger Nachfrage und nichtlinearen Transportkosten

Zusammenfassung Das verallgemeinerte Weber-Problem (transportkostenminimale Standortbestimmung in der Ebene bei linearen Transportkosten) wird für den Fall standortabhängiger Transport-, d.h. Nachfragemengen und nichtlinearer Transportkosten weiterentwickelt. Es werden zwei Modelle zur Bestimmung des deckungsbeitragsmaximalen Standorts eines Auslieferungslagers formuliert und gelöst; das erste Modell berücksichtigt auf der Kostenseite nur die Transportkosten, während in das zweite Modell auch regional unterschiedlich verlaufende Lagerkosten einbezogen werden. Beide Modelle werden anhand eines numerischen Beispiels illustriert.

---

Summary The generalized Weber-problem (cost minimal location of a distribution centre on a plane with linear transport costs) is extended to the case in which demands are related to the location of the depot and when transport costs are concave. Two Models for determining the location that maximizes profits are formulated and solved. In the first model warehousing costs are omitted whereas the second model applies to warehousing cost functions which differ by region. Both models are illustrated by numerical examples.

     

Optimal location and design of a competitive facility

A single facility has to be located in competition with fixed existing facilities of similar type. Demand is supposed to be concentrated at a finite number of points, and consumers patronise the facility to which they are attracted most. Attraction is expressed by some function of the quality of the facility and its distance to demand. For existing facilities quality is fixed, while quality of the new facility may be freely chosen at known costs. The total demand captured by the new facility generates income. The question is to find that location and quality for the new facility which maximises the resulting profits.It is shown that this problem is well posed as soon as consumers are novelty oriented, i.e. attraction ties are resolved in favour of the new facility. Solution of the problem then may be reduced to a bicriterion maxcovering-minquantile problem for which solution methods are known. In the planar case with Euclidean distances and a variety of attraction functions this leads to a finite algorithm polynomial in the number of consumers, whereas, for more general instances, the search of a maximal profit solution is reduced to solving a series of small-scale nonlinear optimisation problems. Alternative tie-resolution rules are finally shown to result in problems in which optimal solutions might not exist.Mathematics Subject Classification (2000):90B85, 90C30, 90C29, 91B42Partially supported by Grant PB96-1416-C02-02 of the D.G.E.S. and Grant BFM2002-04525-C02-02 of Ministerio de Ciencia y Tecnología, Spain     

Exact solution methods for uncapacitated location problems with convex transportation costs

In this paper we study exact solution methods for uncapacitated facility location problems where the transportation costs are nonlinear and convex. An exact linearization of the costs is made, enabling the formulation of the problem as an extended, linear pure zero–one location model. A branch-and-bound method based on a dual ascent and adjustment procedure is developed, and compared to application of a modified Benders decomposition method. The specific application studied is the simple plant location problem (SPLP) with spatial interaction, which is a model suitable for location of public facilities. Previously approximate solution methods have been used for this problem, while we in this paper investigate exact solution methods. Computational results are presented.     

Approximate and exact algorithms for the fixed-charge knapsack problem

The subject of this paper is the formulation and solution of a variation of the classical binary knapsack problem. The variation that is addressed is termed the “fixed-charge knapsack problem”, in which sub-sets of variables (activities) are associated with fixed costs. These costs may represent certain set-ups and/or preparations required for the associated sub-set of activities to be scheduled. Several potential real-world applications as well as problem extensions/generalizations are discussed. The efficient solution of the problem is facilitated by a standard branch-and-bound algorithm based on (1) a non-iterative, polynomial algorithm to solve the LP relaxation, (2) various heuristic procedures to obtain good candidate solutions by adjusting the LP solution, and (3) powerful rules to peg the variables. Computational experience shows that the suggested branch-and-bound algorithm shows excellent potential in the solution of a wide variety of large fixed-charge knapsack problems.     

Heuristics for the fixed cost median problem

We describe in this paper polynomial heuristics for three important hard problems—the discrete fixed cost median problem (the plant location problem), the continuous fixed cost median problem in a Euclidean space, and the network fixed cost median problem with convex costs. The heuristics for all the three problems guarantee error ratios no worse than the logarithm of the number of customer points. The derivation of the heuristics is based on the presentation of all types of median problems discussed as a set covering problem.     

Facility location with increasing production costs

Facility location models determine the set of locations on a network that minimize the sum of the costs of investment, production, and distribution to meet a known set of demands. In this paper, we introduce a new type of facility location model, which combines aspects of the well-studied simple uncapacitated and capacitated facility location problems. Its distinctive feature is that unit production costs are modeled as increasing with scale of output. Such cost functions have practical value in handling cases in which capacity can be “stretched” by incurring some additional cost (e.g., by adding workers). Indeed, it is shown that average total costs are minimized at a point where average production costs are rising. Four different formulations for this problem are proposed. Using linear programming plus branch-and-bound as a solution method, the four formulations are tested and compared on a set of 216 problems with randomly generated data.     

Soft due window assignment and scheduling of unit-time jobs on parallel machines

We study problems of scheduling n unit-time jobs on m identical parallel machines, in which a common due window has to be assigned to all jobs. If a job is completed within the due window, then no scheduling cost incurs. Otherwise, a job-dependent earliness or tardiness cost incurs. The job completion times, the due window location and the size are integer valued decision variables. The objective is to find a job schedule as well as the location and the size of the due window such that a weighted sum or maximum of costs associated with job earliness, job tardiness and due window location and size is minimized. We establish properties of optimal solutions of these min-sum and min-max problems and reduce them to min-sum (traditional) or min-max (bottleneck) assignment problems solvable in O(n ⁵/m ²) and O(n ^4.5log^0.5 n/m ²) time, respectively. More efficient solution procedures are given for the case in which the due window size cost does not exceed the due window start time cost, the single machine case, the case of proportional earliness and tardiness costs and the case of equal earliness and tardiness costs.     

The plant location and flexible technology acquisition problem

In many industries, production–distribution networks have become more complex due to globalization. In particular, increasing interdependencies among structural decisions call for the development of integrated models. In this paper, we present a mathematical model for simultaneous optimization of the plant location, capacity acquisition and technology selection decisions in a multi-commodity environment. The proposed model represents the possible scale and scope economies associated with manufacturing technology alternatives. The problem is formulated as a mixed integer nonlinear program with concave costs. We developed an exact and three heuristic solution procedures. Using these procedures, we are able to solve fairly large facility design problems with reasonable computational effort.     

On the convergence of the Weiszfeld algorithm for continuous single facility location–allocation problems

A general family of single facility continuous location–allocation problems is introduced, which includes the decreasingly weighted ordered median problem, the single facility Weber problem with supply surplus, and Weber problems with alternative fast transportation network. We show in this paper that the extension of the well known Weiszfeld iterative decrease method for solving the corresponding location problems with fixed allocation yields an always convergent scheme for the location allocation problems. In a generic way, from each starting point, the limit point will be a locally minimal solution, whereas for each possible exceptional situation, a possible solution is indicated. Some computational results are presented, comparing this method with an alternating location–allocation approach. The research of the second author was partially supported by the grant of the Algerian Ministry of High Education 001BIS/PNE/ENSEIGNANTS/BELGIQUE.     

Cost Comparisons for Out-of-Phase Inventory Models

Inventory costs for a fixed time period have traditionally been determined by allocating total costs per cycle uniformly throughout that cycle as well as any partial cycles. This procedure for cost allocation has led to the solution of numerous inventory problems, most notable of which is the anticipated price-increase model. When comparing two out-of-phase inventory models, if costs are accounted for when they occur over a fixed planning horizon, inventory policies should be changed to reflect the impact of this different cost-allocation procedure. For the anticipated price-increase model, the ‘optimal’ order quantity as well as the implied savings in inventory costs will be different when cost models are developed based on these different cost-allocation methods. If the objective is to maximize over a fixed planning horizon the actual savings in inventory costs as they occur, the cost models presented here should be used.     

A decision theory based scheduling procedure for single-machine weighted earliness and tardiness problems

We consider the dynamic single-machine scheduling problem where the objective is to minimize the sum of weighted earliness and weighted tardiness costs. A single pass heuristic, based on decision theory, is developed for constructing schedules. The heuristic permits schedules with idle time between jobs and behaves like a dispatching procedure. The performance of the new heuristic is examined using 116 published problems for which the optimum solution is known. Its performance is also investigated using 540 randomly generated problems covering a variety of conditions by comparing it to two well known dispatching procedures, adapted for dynamic early/tardy problems. The results indicate that the heuristic performs very well.     

A variable neighbourhood search algorithm for the constrained task allocation problem

A variable neighbourhood search algorithm that employs new neighbourhoods is proposed for solving a task allocation problem whose main characteristics are: (i) each task requires a certain amount of resources and each processor has a capacity constraint which limits the total resource of the tasks that are assigned to it; (ii) the cost of solution includes fixed costs when using processors, task assignment costs, and communication costs between tasks assigned to different processors. A computational study shows that the algorithm performs well in terms of time and solution quality relative to other local search procedures that have been proposed.