Petri net modeling and Lagrangian relaxation approach to vehicle scheduling in 300mm semiconductor manufacturing

Da Yin Liao, Mu Der Jeng, Mengchu Zhou

Research output: Contribution to journalConference articlepeer-review

17 Scopus citations

Abstract

Instead of making decisions with fast but local dispatching functions, the increasing computing power and upto-moment information provisioning have made possible real-time vehicle scheduling in an automated material handling environment in 300mm semiconductor manufacturing. To our best knowledge, this paper is the first work to adopt the scheduling approach to solve the 300mm vehicle transportation problems. We adopt Petri nets to model the coupling dynamics among transport jobs and OHT vehicles in an intrabay loop. The congestion phenomenon among OHT vehicles is captured. The OHT scheduling problem is then formulated into an integer programming problem whose goal is to efficiently allocate OHT vehicles to jobs such that average job delivery time is minimized. A solution methodology that combines Lagrangian relaxation and the surrogate subgradient methods [13] is developed. To reduce computational efforts in solving each subproblem optimally, an approximation method is developed to solve for subproblems. 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 25.6% improvements on the average delivery time in our realistic test cases.

Original languageEnglish (US)
Pages (from-to)5301-5306
Number of pages6
JournalProceedings - IEEE International Conference on Robotics and Automation
Volume2004
Issue number5
StatePublished - Jul 5 2004
EventProceedings- 2004 IEEE International Conference on Robotics and Automation - New Orleans, LA, United States
Duration: Apr 26 2004May 1 2004

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Petri net modeling and Lagrangian relaxation approach to vehicle scheduling in 300mm semiconductor manufacturing'. Together they form a unique fingerprint.

Cite this