A Petri net model to determine optimal assembly sequences with assembly operation constraints

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 on1y 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.