In: International Journal of Industrial Engineering - Theory, Applications and Practice, Vol. 6, No. 1, pages 27-37. 1999.
Abstract: In an automated assembly system, a product is completed through a series of assembly operations according to a predefined sequence. Partially assembled components are automatically transported from one machine to another machine until the final product is organized. This paper describes a method for finding optimal assembly sequences in an assembly system. All feasible assembly sequences can be represented by an AND/OR graph which provides all feasible geometric configurations and relationships among the components of a product. The AND/OR graph is converted into a Petri net which can be formulated as a linear program with the objective of minimizing the total assembly time or cost. A dynamic programming algorithm is developed to find the optimal sequences from the Petri net since too much computational effort is required to obtain the optimal solution of the linear program by utilizing the simplex method and interior point methods. The algorithm has the computational complexity of O(nm), where n and m denote the number of assembly operations and base components, respectively, and it is more efficient than the former methods. Three assembly products are provided to validate the algorithm. Selection of an assembly sequence for a product may greatly affect the efficiency of an assembly process. When the number of components is large, it is very time consuming to find optimal assembly sequences. The method proposed in this study provides an efficient means for minimizing the total assembly time or cost, which is a fundamental step for establishing a good assembly plan.
Keywords: Petri nets, assembly sequences, dynamic programming, multiple products.