(A) strong cutting plane algorithm for simple assembly line balancing problem

Abstract

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.