INPUT SEQUENCING FOR ASSEMBLY LINES A CUTTING PLANE ALGORITHM

Mixed model assembly lines are becoming increasingly used in manufacturing facilities to meet the diversified demands of customers. In this paper we deal with syncronous flow lines and wish to determine the job input sequence minimizing total tardiness. A ILP formulation of the problem is given. We prove the strong NP-hardness of the problem, we try to solve the linear relaxation of the problem and then introduce a number of cutting planes to solve the separation problem. Computational results confirm the effectiveness of the procedure.