Title :
An Efficient Mixed Integer Programming Model Based on Timed Petri Nets for Diverse Complex Cluster Tool Scheduling Problems
Author :
Jung, Chihyun ; Lee, Tae-Eog
Author_Institution :
GLOBALFOUNDRIES, Inc., Malta, NY, USA
fDate :
5/1/2012 12:00:00 AM
Abstract :
Cluster tools are automated production cells which are largely used for semiconductor manufacturing. They consist of several processing modules (PMs) and a transportation robot. Since cluster tools have limited buffers and diverse scheduling requirements such as complex wafer flow patterns, parallel PMs, wafer residency time constraints, and dual-arm robot, and so on, their scheduling problems are difficult. Due to the diversity of scheduling problems, dealing with those problems one by one may be impractical. Computational complexity is another difficulty. In this paper, we propose an efficient scheduling method to deal with diverse complex cluster tool scheduling problems by using timed Petri nets (TPN). We propose TPN models of cluster tools with various scheduling requirements. Then, based on the TPN models and their state equations, we develop a new mixed integer programming (MIP) model that can efficiently determine the optimal cyclic schedules. We show that many kinds of scheduling requirements such as parallel, reentrant and multiple material flows, a dual-armed robot, and time constrained PMs can be dealt with by the MIP model. Through experiments, we also show that the MIP model can efficiently solve most practical cluster tool scheduling problems.
Keywords :
Petri nets; integer programming; scheduling; TPN model; automated production cell; computational complexity; diverse complex cluster tool scheduling problem; dual-armed robot; mixed integer programming model; optimal cyclic schedule; semiconductor manufacturing; state equation; timed Petri nets; transportation robot; wafer flow pattern; wafer residency time constraint; Availability; Job shop scheduling; Load modeling; Optimal scheduling; Petri nets; Robots; Semiconductor device modeling; Cluster tool; Petri net; cyclic scheduling; mixed integer programming (MIP);
Journal_Title :
Semiconductor Manufacturing, IEEE Transactions on
DOI :
10.1109/TSM.2011.2180547