Dynamic programming algorithm to determine optimal assembly sequences using Petri nets

Shang Tae Yee, Jose Antonio Ventura

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)27-37
Number of pages11
JournalInternational Journal of Industrial Engineering : Theory Applications and Practice
Issue number1
StatePublished - Mar 1 1999

All Science Journal Classification (ASJC) codes

  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Dynamic programming algorithm to determine optimal assembly sequences using Petri nets'. Together they form a unique fingerprint.

Cite this