This thesis describes a multifacility capacity expansion model with conversion. Each facility type is used to satisfy a variety of deterministic demand over a finite number of discrete time periods. An example of the model is the cable sizing problem associated with the planning of communication network. Since the problem is NP-complete, it is time consumptive to find an exact optimum solution using ordinary mixed integer programming algorithm. We decompose the problem with respect to each facility, using the special Lagrangian relaxation technique of introducing integrated variables. The integrated variable is defined as the sum of independent variables. For each facility, the decomposed problem is solved by a dynamic programming method.
We develop a heuristic method of constructing a good feasible solution from the solution of relaxed problems. Computational results show that the average tolerance is 2.66%. Compared with the average tolerances of other problems, it is reasonable. And we successfully solve the realistic problems with large-sizes within reasonable computation times.
본 논문은 설비전환이 있는 복수설비의 확장문제를 다룬다. 설비전환은 한 설비의 용량을 다른 설비의 수요를 충족시키기 위하여 사용하는 것을 의미한다. 이러한 문제의 응용은 전선의 크기를 정하는 문제에서 볼 수 있다.
제안된 모형은 NP-Complete하여 최적해를 구하는 것은 시간이 오래 걸린다. 본 논문에서는 결합변수 (integrated variable) 를 도입하여 문제를 완화 (relax) 시켜서 푼다. 완화된 문제는 설비별로 부문제 (subproblem) 로 나누어지고 부문제는 동적 계획법을 이용하여 해를 구한다. 완화된 문제를 푼 해를 이용하여 좋은 가능해를 만드는 것은 발견적 해법 (heuristic method) 를 이용하여 해결한다.
예제를 통해 본 가능해와 계산시간은 본 논문의 해법이 효율적이라는 것을 보여 준다.
