A Lagrangian relaxation approach to capacity planning for a manufacturing sysstem with flexible and dedicated machines

We consider a multiperiod capacity planning problem for determining a mix of flexible and dedicated capacities under budget restriction. These capacities are controlled by purchasing flexible machines and/or new dedicated machines and disposing of old dedicated machines. Acquisition and replacement schedules are determined and operations are assigned to the flexible or dedicated machines with the objective of minimizing the sum of discounted costs of acquisition and operation of flexible machines, new dedicated machines, and old dedicated machines. In this research, the problem is formulated as a mixed integer linear program and solved by a Lagrangian relaxation approach. A subgradient optimization method is employed to obtain lower bounds and a multiplier adjustment method is devised to improve the bounds. We develop a linear programming based Lagrangian heuristic algorithm to find a good feasible solution of the original problem. Results of tests on randomly generated test problems show that the algorithm gives relatively good solutions in a reasonable amount of computation time.