Application of Petri nets and Lagrangian relaxation to scheduling automatic material-handling vehicles in 300-mm semiconductor manufacturing

Da Yin Liao, Mu Der Jeng, Meng Chu Zhou

Research output: Contribution to journalArticlepeer-review

31 Scopus citations


This paper deals with vehicle-scheduling problem (VSP) in an automatic material-handling environment in 300-mm semiconductor wafer manufacturing. We adopt Petri nets (PNs) modeling techniques to model the complicated coupling dynamics among transport jobs and overhead hoist transport (OHT) vehicles in a 300-mm OHT loop. The congestion phenomenon among OHT vehicles is captured. With help of the PN models, we formulate the OHT VSP as an integer programming problem whose objective is to schedule OHT vehicles to transport jobs such that average job completion time is minimized. Instead of solving for the optimal solution, we develop a solution methodology to generate a feasible schedule efficiently. A Lagrangian relaxation step is first taken to decompose the PN-based, integer programming problem into individual job-scheduling subproblems. To reduce computation efforts in solving each subproblem optimally, we develop an approximation method to solve each job subproblem by utilizing a reduced PN model of the job. Lagrangian multipliers are then optimized by a surrogate subgradient method. A heuristic algorithm is developed to adjust the dual solution to a feasible schedule. Numerical results demonstrate that our solution methodology can generate good schedules within a reasonable amount of computation time for realistic problems. Compared to a popular vehicle-dispatching rule, our approach can achieve in average 32% improvements on the average delivery time in our realistic test cases.

Original languageEnglish (US)
Pages (from-to)504-516
Number of pages13
JournalIEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews
Issue number4
StatePublished - Jul 2007

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Software
  • Information Systems
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering


  • 300-mm semiconductor manufacturing
  • Automatic material-handling system (AMHS)
  • Lagrangian relaxation
  • Overhead hoist transport (OHT)
  • Timed Petri nets (TPNs)
  • Vehicle scheduling


Dive into the research topics of 'Application of Petri nets and Lagrangian relaxation to scheduling automatic material-handling vehicles in 300-mm semiconductor manufacturing'. Together they form a unique fingerprint.

Cite this