Capacity planning for phased implementation of flexible manufacturing systems under budget restrictions

We consider a problem of gradually replacing conventional dedicated machines with flexible manufacturing modules (FMMs) under budget restrictions over a finite planning horizon assuming that dedicated machines cannot be purchased during the planning horizon and acquired FMMs are kept until the end of the horizon. In the problem, a replacement schedule is to be determined and operations are to be assigned to the FMMs or the dedicated machines with the objective of minimizing the sum of discounted costs of acquisition and operation of FMMs and operation costs of conventional dedicated machines. In this research, the problem is formulated as a mixed integer linear program and solved by a Lagrangean relaxation approach. A subgradient optimization method is employed to obtain lower bounds of solutions and a multiplier adjustment method is devised to improve the lower bounds. We develop a linear programming-based Lagrangean heuristic algorithm to find a good feasible solution of the original problem in a reasonable amount of computation time. The algorithm is tested on randomly generated test problems and the results are reported.