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

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.