An Efficient Mixed Integer Programming Model Based on Timed Petri Nets for Diverse Complex Cluster Tool Scheduling Problems

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.