In: Journal of Manufacturing Systems, Vol. 18, No. 3, pages 203-213. 1999.
Abstract: The assembly process in an automated assembly system is the execution of successive assembly operations in which each operation joins one component with another component to form a larger component. The selection of the assembly sequence of a product has a great effect on the efficiency of the assembly process. A systematic procedure is needed not only to generate all feasible assembly sequences but also to choose an optimal sequence. This paper describes a method for finding tight bounds on optimal sequences in an assembly system. A Petri net obtained from the AND/OR graph of a product can be formulated as a 0-1 integer linear program that minimizes the total assembly time or cost while satisfying three assembly operation constraints, namely, ease of component handling, ease of component joining, and tool changes. A Lagrangian dual formulation is then developed to obtain a lower bound. A dynamic programming algorithm provides a dual solution, and a subgradient optimization algorithm is used to maximize the lower bound obtained from the dual problem. The solution procedure is validated by determining the optimal assembly sequences of three products.
Keywords: Lagrangian relaxation, Petri nets, assembly sequencing, automated assembly system, dynamic programming, multiple products.