Assembly line balancing: |a branch and bound approach

Abstract

Assembly Line Balancing (ALB) problem is a combinatorial problem which has extremely large number of feasible solutions. In the literature, there are two approaches to the solution of this problem: heuristic methods and exact methods. Heuristic methods give suboptimal solutions but they are easy to compute. Whereas, exact methods give the optimum solutions but they possess severe computational difficulties for sufficiently large problems in real-life. Therefore, exatt methods have to be improved to solve real-life ALB problems with less difficulty. In this study, it is intended to obtain optimal solutions in real-life ALB problems that would be effectively used in industry. Therefore, a package of user-friendly interactive computer programs is developed in which a new branch and bound ( B&B ) approach is implemented. The method is studied for single-model and mixed-model assembly lines. In order to make the problem more realistic, additional restrictions are added to the regular precedence and cycle time restrictions. An upper bound concept which is used for feasibility check of the lower bounds is introduced. The programs are run for several sample problems and computational efficiency of the B&B method proposed is obtained.