ON THE EQUIVALENCE OF AN EQUIPMENT REPLACEMENT PROBLEM AND A FACILITY LOCATION PROBLEM Candace Arai Yano Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 December 1984 Technical Report 84-27

ON THE EQUIVALENCE OF AN EQUIPMENT REPLACEMENT PROBLEM AND A FACILITY LOCATION PROBLEM Candace Arai Yano Department of Industrial and Operations Engineering University of Michigan Ann Arbor, Michigan 48109, USA ABSTRACT In this note we demonstrate the equivalence of the parallel equipment replacement problem and the capacitated facility location problem. We also discuss how recent research in the facility location area may contribute to the development of more efficient algorithms for equipment replacement problems.

ON THE EQUIVALENCE OF AN EQUIPMENT REPLACEMENT PROBLEM AND A FACILITY LOCATION PROBLEM ABSTRACT In this note we demonstrate the equivalence of the parallel equipment replacement problem and the capacitated facility location problem. We also discuss how recent research in the facility location area may contribute to the development of more efficient algorithms for equipment replacement problems.

1. INTRODUCTION Much of the literature on equipment replacement has dealt with single machine problems. Many real-world equipment replacement problems involve selection of two or more machines of one or more types from a set of several possible alternative machines with different capacities and costs of purchase and operation. Often the capacities of the machines may be such that more than one machine is necessary to satisfy production requirements. Problems in which more than one machine may operate at a given time are referred to as parallel equipment replacement problems. Despite their importance, these problems have received little attention, primarily because dynamic programming approaches which are useful for single machine problems (e.g., Oakford et al. (1983)) become computationally prohibitive for parallel machine, multi-period problems. In Section 2 we demonstrate the equivalence of a parallel equipment replacement problem and a well-studied capacitated facility location problem. Section 3 provides a brief review of relevant facility location research and suggests ways in which the techniques and results can contribute to the development of better solution techniques for equipment replacement. Section 4 concludes with a brief discussion of implementation issues and directions for future research. 2. Equivalence of the Two Problems The capacitated facility location problem involves selecting the minimum cost subset of potential facility sites given a fixed cost and capacity asso 1

ciated with each facility, variable production cost per unit for each facility, transportation costs per unit for goods shipped from the facilities to various customers, and demand to be satisfied at each customer location. The parallel equipment replacement problem is to determine which machines to purchase and when, and when to retire them given installation costs, annual operating costs, variable production costs per unit, time-varying salvage value of the machines, and demand to be satisfied in each period in a finite horizon. The former typically is treated as a one period problem (although the period may be long and discounting may be implicit in the data) while the latter is a multiple period problem in which future cash flows are discounted to the present (i.e., the objective uses net present value). The capacitated facility location problem can be stated as: (Pi) minimize Z fi Yi + ZZ cij xij i ij s.t. z xij = dj i Z xij i yi Qi j (1) vj Vi (2) (3) where fi = cij = dj= Qi = xi = Yi = i = 0 or 1 Vi (4) xij - O Vi,j (5) fixed cost of facility i variable cost of producing one unit at facility i and shipping it to customer j demand at customer j capacity of facility i quantity produced at facility i for use by customer j 1 if facility i is open 0 otherwise 2

The objective function minimizes the total system cost while the constraints insure that (a) demand is satisfied, (b) capacity is not exceeded, and (c) integrality of the binary variables. The parallel equipment replacement problem can be formulated as follows: Let Fijk = sum of purchase and fixed annual operating costs less salvage value, discounted to the present time for machine type i available in year j and to be retired at the end of year k Pijkt = variable cost of unit produced by machine (i,j,k) in year t Mijkt = capacity of machine (i,j,k) in year t (units annually) = 0 if t f [j,k] Rt = demand in year t (in units) Uijkt = quantity produced by machine (i,j,k) in year t Vijk = 1 if machine (i,j,k) is chosen 0 otherwise To simplify the notation, we substitute index s for (i,j,k), using any convenient one-to-one mapping. The problem then becomes. (P2) minimize Z FsVs + ZZ Pst Ust (6) s ts s.t. Z Ust - Rt Vt (7) S Ust - Mst Vs Vs,t (8) V = or 1 Vs (9) Ust 0 Vs,t (10) 3

Notice that the only differences between P1 and P2 are in the capacity constraints in equations (3) and (8) respectively. Each plant may supply multiple customers in P1 while each machine has a single "customer" in each period in P2. Although there may be a different number of constraints in the two problems, they are fundamentally of the same type. As a result, the techniques designed to solve facility location problems can be used with little or no modification to solve the multiple machine equipment replacement problem. This is discussed further in the next section. 3. Applicability of Facility Location Algorithms to Equipment Replacement One commonly used approach to the capacitated facility location problem is branch and bound (see McGinnis (1977) for a survey). A lower bound on variable costs (see Davis and Ray (1969) ) can be found by solving a capacitated transportation subproblem using as sources those facilities not specifically excluded at the current node in the branch and bound tree. A network representation of both problems is depicted in Figure 1. The only difference between the problems is that in the facility location problem the capacity constraints are on the "aggregate" arcs connecting the source node in the network to the facility nodes, while in the equipment replacement problem the capacity constraints are on the arcs connecting the machine nodes to the period nodes. These differences, however, do not affect the manner in which the subproblems are solved. (By adding an arc from the sink to the source, both problems become a minimum cost circulation problem which can be solved using the out-of-kilter algorithm). Modifications to the problem, such as configuration constraints included by Ellwein and Gray (1971), and constraints added to eliminate uneconomical confi 4

gurations (e.g. delta and omega simplifications of Khumawala and Akinc (1972) and Benders inequalities used by Ellwein and Gray), affect only the branching procedures and not the solution of the transportation subproblem. Therefore, configuration constraints and techniques designed to reduce the number of branches can be used in the equipment replacement problem as well. Lagrangian relaxation has been suggested by Geoffrion and McBride (1978) as a possible way to solve capacitated facility location problems. They relax the configuration constraints as well as those constraints related to satisfying demand. The problem then decomposes into a set of independent subproblems, one for each source. The formulation used by Geoffrion and McBride defines the continuous variables as fraction of the customer's demand satisfied by a given source, and costs and constraints are adjusted accordingly. Problem P2 also can be reformulated in this manner, resulting in a problem equivalent to the Geoffrion and McBride formulation. Therefore, their Lagrangian relaxation approach can be applied directly to the equipment replacement problem. Davis and Ray (1969) reformulate the problem by adding the constraints 0 1 xij - Yi min (dj, Qi) Vi,j These constraints require a facility to be open if it satisfies all of a single customer's demand and therefore provide for much tighter lower bounds. An equivalent modification can be made in P2, providing tighter bounds than the original formulation. This modification, however, is not useful when dj > Qi for all i and j, as is typically true in many parallel equipment replacement problems. 5

4. Discussion It is evident that a number of existing approaches to the capacitated facility location problem can be applied, either directly or with minor modifications, to the parallel equipment replacement problem. There is, however, one very important implementation problem as yet unresolved. Typical facility location problems may require selection of several sources from perhaps a few dozen alternatives at most. Typical equipment replacement problems, on the other hand, may require selection of many machines (defined by type, year of introduction and year of retirement) from a larger set of alternatives. Thus, it may be computationally infeasible to handle the number of nodes in the resulting branch and bound tree. However, the real applications, a limited number (perhaps two or three) types of machines performing the same operation can be installed at a given time because of technical and administrative limitations. The resulting configuration constraints will limit the size of the branch and bound tree quite significantly. However, variable elimination techniques such as the delta and omega simplifications probably will not reduce the number of alternatives in equipment replacement problems as much as in the facility location problems. One reason for this is the similarities among candidate "machines"; for example machine (i,j,k) will have very similar cost characteristics to machine (i,j,k+l). Therefore, further research on elimination techniques to reduce the size of the candidate set as much as possible could be of significant benefit. Two other important issues remain. The first is the question of validity of the cost minimizing objective function, especially for equipment replacement problems. If the firm operates in a competitive environment and cannot control the price it receives for product produced, it may not necessarily be optimal to 6

satisfy all demand. Maximization of profits may be a more applicable objective, and the techniques described above will not address this problem. The profit maximization form of the problem can be solved using a branch and bound technique in which bounds are derived using Lagrangian relaxation. Additional details can be found in the Appendix. However, the solution procedure is somewhat more complex than the capacitated transportation problem used in the cost minimization form of the problem. The second issue is the sensitivity of the solution to the length of the horizon in the equipment replacement problem. Recall that the number of customers in the facility location problem is equivalent to the number of periods in the equipment replacement problem. The addition of customers to a facility location problem may influence the solution but it does not necessarily increase the number of potential facility locations. On the other hand, addition of periods to the horizon in the equipment replacement problem also increases the number of "machine" alternatives. Not only must models which become available in the last few (additional) periods be considered, but models available earlier may be retained for longer periods of time before they are retired. Thus, the solution may be extremely sensitive to the length of the horizon and it may be difficult or impossible to determine decision or planning horizons using adaptations of facility location techniques. Despite these potential difficulties, techniques from the facility location literature may provide workablesolution procedures for equipment replacement problems in the near term and insights into even better approaches and techniques in the longer term. 7

Appendix Let gst = gross margin per unit for machines in year t and Fs, Vs, Pst, Ust, rt, Mst be defined as for (P2). Then the profit maximization form of the equipment replacement problem can be stated as maximize ZZ gst Ust - Z Fs V (11) st s s.t. Z Ust rt Vt (12) s Ust Mst Vs Vs,t (13) Vs = or 1 Vs (14) Ust > 0 Vs,t (15) The objective function can be restated as minimize Z FsVs - maximum ZZ gst Ust Vs Ust To obtain the desired bounds, the maximization subproblem can be solved by relaxing the constraints in (13). The subproblem then decomposes into a set of continuous knapsack problems, one for each value of t. This now bears resemblance to the Geoffrion and McBride approach to the facility location problem, which can be applied in concept directly to this problem. 8

References [1] Akinc, V. and B. M. Khumawala (1977), "An Efficient Branch and Bound Algorithm for the Capacitated Warehouse Location Problem," Management Science, Vol. 23, No. 6, pp. 585-594. [2] Davis, P. S. and T. L. Ray, "A Branch-Bound Algorithm for the Capacitated Facilities Location Problem," Naval Research Logistics Quarterly, Vol. 16, No. 3, pp. 331-344. [3] Ellwein, L. B. and P. Gray (1971) "Solving Fixed Charge Location-Allocation Problems with Capacity and Configuration Constraints," AIIE Transactions, Vol 3, No. 4, pp. 290-298. [4] Geoffrion, A. and R. McBride (1978), "Lagrangian Relaxation Applied to Capacitated Facility Location Problems," AIIE Transactions, Vol. 10, No. 1, pp. 40-47. [5] McGinnis, L. (1977) "A Survey of Recent Results for a Class of Facilities Location Problems," AIIE Transactions, Vol. 9, No. 1, pp. 11-18. [6] Oakford, R. V., J. R. Lohmann, and A. Salazar (1984), "A Dynamic Replacement Economy Decision Model," IE Transactions, Vol. 16, No. 1, pp. 65-72. 9

Machines or Facilities Periods or Customers Figure 1 Network Representation of the Transportation Subproblems 10