A LAGRANGIAN-RELAXATION TECHNIQUE FOR THE GENERAL-ASSEMBLY LINE BALANCING PROBLEM

This paper addresses the problem of balancing assembly or fabrication lines. In order to achieve a given production rate or to optimize the use of workstations, one has to tackle the problem of balancing the pr oduction lines. It is well known that this problem belongs to the clas s of NP-hard problems. In this paper the polyhedron of the feasible so lutions of the assembly line balancing problem is first studied. Then a Lagrangian relaxation algorithm that incorporates the set of cycle c onstraints in the objective function is proposed. These constraints ar e the complicating restrictions in the model. The relaxed problem has the interesting property that its linear programming relaxation always has integer optimal solutions. The subgradient algorithm is then used to maximize the Lagrangian dual. A heuristic is also used to find pri mal feasible solutions for the original line balancing integer program . These two bounds are then used to reduce the size of the branch-and- bound tree.