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

Shang Tae Yee, Jose A. Ventura

Research output: Contribution to journalArticlepeer-review

28 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)203-213
Number of pages11
JournalJournal of Manufacturing Systems
Issue number3
StatePublished - 1999

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Hardware and Architecture
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'A Petri net model to determine optimal assembly sequences with assembly operation constraints'. Together they form a unique fingerprint.

Cite this