The series-parallel replacement problem

Traditional equipment replacement models focus on single machine problems. However, the capacity of many production facilities is defined by multiple, heterogeneous machines. In this situation, optimal replacement (and expansion) decisions must consider all machines and their integration simultaneously as they define system capacity and are therefore economically interdependent. We model a multiple machine replacement problem that is characterized as a parallel flow shop environment. Work flows through processes in a facility according to a predetermined processing order for the product(s). For a given process, numerous machines, which may differ according to type (different manufacturers), capacity, and/or age, operate in parallel. A series of these processes defines a line and in our analysis, a plant is comprised of multiple, parallel lines. In this preliminary investigation, we present an integer programming formulation to determine optimal purchase, salvage, utilization and storage decisions for each asset over a finite horizon. We illustrate that this model is difficult to solve. We provide valid inequalities to improve the lower bound provided by the linear programming relaxation and a dynamic programming approach to provide initial upper bounds. (C) 2002 Elsevier Science Ltd. All rights reserved.