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.
본 논문은 예산제약이 있는 상황하에서 유연생산설비의 단계적 도입방안을 결정 하는 문제를 다루고 있다. 각 시점에서 어떤 유형의 유연생산설비를 도입하여 어떻게 사용하는 것이 효율적인가를 결정한다. 이 문제를 정수계획으로 모형화하여 라그랑지안 완화기법을 이용하여 원문제의 하경계치를 결정했다. 라그랑지안기법으로 완화된 문제를 그것의 최적해에 대한 성질들을 이용하여 일반적인 배낭문제와 이진정수계획 문제로 분리시키고 각각 동적계획 알고리듬과 최적해의 성질을 이용한 간단한 해법으로 풀었다. 여기서 구한 완화된 해를 가지고 원문제의 가능해를 구하기 위해 라그랑지안 휴리스틱 알고리듬을 개발하였다. 이 알고리듬은 그리디휴리스틱과의 비교를 통해 그 성능이 평가 되었다. 그리디 휴리스틱에 비해 해를 찾는데 소요되는 시간은 길었지만 구해진 해의 성질은 그리디 휴리스틱보다 상당히 좋다는 결론을 내릴 수 있었다.
