This thesis proposes an integer programming algorithm for assigning tasks on an assembly line to work stations in such a way that the number of work stations is minimum for the rate of production desired (cycle time). The formulation insures that precedence restrictions and cycle time restrictions are not violated.
The first part of algorithm is to add some constraints called cutting planes based on specific structure of line balancing problem to LP-relaxed formulation, resulting in more tight formulation. The second part is B＆B(Branch and Bound) procedure. In many cases, B＆B procedure is very time consuming, so the idea of this approach is tightening the formulation before entering B＆B stage, which can reduce the size of the B＆B tree to be searched significantly.
본 논문은 단순 라인 밸런싱 문제의 최적해를 구하는 새로운 접근방법을 제시한다. 기존의 접근방법이 주로 분지한계 나무 위에서의 탐색 방법이었으나 본 논문에서는 강한(strong) 절단평면 (cutting plane) 을 사용하여 탐색 나무를 대폭 줄이는 방법을 다루었다.
이 방법의 장점은 문제의 제한조건이 변하더라도 비교적 쉽게 적용 될 수 있다는 것이다. 오늘날의 조립라인 상황은 복잡해서 단순 라인 밸런싱 문제의 해법으로는 해결하지 못하는 경우가 많으므로 이러한 둔감성 (robustness)은 중요하다.
반면, 이 방법은 기존의 방법들 보다 훨씬 큰 컴퓨터 메모리를 요구한다.
최근 강한 절단평면을 이용한 접근방법이 최적화 분야의 문제에 폭넓게 적용되어 좋은 결과를 내고 있음으로 미루어 라인 밸런싱 문제에도 이 방법이 성공적으로 적용 되리라고 기대된다.
