In this thesis, we examine the project sequencing problem for capacity expansion, where a project can be implemented only at discrete time points and distribution costs as well as expansion costs are considered. The objective of this problem is to find the sequence of expansions necessary to provide sufficient capacities to meet the regional demands in all periods at a minimum total cost which is the sum of capacity expansion costs and distribution costs.
Project sequencing problems are difficult combinatorial problems for which the optimal solutions can be found only if the number of possible projects is small. Dynamic programming algorithm can not be applied if the number of projects is large. Here we concentrate on solving large size problems efficiently.
Assuming independence of each project, this problem can be formulated as a mixed integer programming problem, and is solved using Lagrangean relaxation method combined with subgradient optimization procedure. Several heuristics to find a feasible solution are presented.
Finally, computational results are provided and future research directions are discussed.
본 논문은 설비확장 프로젝트의 수행순서 결정에 관한 해법의 연구이다.
증가하는 수요를 충족시키기 위하여, 생산설비의 확장이 필요하며, 계속적인 설비확장이 어려운경우, 설비확장 프로젝트는 독특한 특성을 갖게된다. 이러한 설비확장 프로젝트가 여러개 있는 경우, 그 수행순서와 시기의 결정이 중요하다.
프로젝트의 수행순서 결정 문제는 설비확장 프로젝트의 수가 적은 경우에만 최적해를 찾을 수 있는 풀기 어려운 문제이다. 기존의 동적계획법으로는 설비확장 프로젝트의 수가 많은 경우에는 이문제를 풀수가 없다. 본 논문에서는 이러한 문제를 효율적으로 풀수 있는 해법의 개발에 촛점을 두었다.
Lagrangean Relaxation기법을 적용함으로써 설비확장 프로젝트의 수행순서 결정 문제는 풀기 쉬운 문제가 되며, 최적해에 가까운 해를 빨리 구할 수가 있다.
