Dynamic programming algorithm to determine optimal assembly sequences using Petri nets

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.