Phased implementation of flexible technology under budget restrictions

Abstract

We consider a problem of acquiring flexible technology and replacing equipment under budget restrictions over a finite planning horizon. In the problem, we determine a replacement schedule and assignments of operations to machines with the objective of minimizing discounted acquisition and operation costs of flexible modules minus salvage values of conventional dedicated machines. The problem is formulated as a mixed integer linear program and solved with a Lagrangian relaxation approach, in which the Lagrangian relaxation problem is obtained by dualizing demand constraints. The relaxed problem is decomposed into two independent subproblems. Using optimal solution properties of the two subproblems, one subproblem can be converted into a general integer knapsack problem and the other is reformulated as a pure integer program. The former subproblem is solved by an optimal dynamic programming recursion, while the latter is solved easily using the optimal solution property of the problem. We develop a linear programming based Lagrangian heuristic algorithm that uses solutions of the two subproblems to find a feasible solution of the original problem. The algorithm is tested on randomly generated test problems and compared with a greedy type heuristic algorithm.