State dependant scheduling using a multi-objective approach

Abstract

Recently, semiconductor manufacturing fabs tend to reduce the wafer lot size, down to just a few. Consequently, the wafer recipe or wafer flow pattern changes frequently. For such problems it is impossible to apply conventional prevalent cyclic scheduling methods that repeat processing of wafers in an identical cyclic tool operation sequence. We therefore consider the non-cyclic scheduling problem encountered in cluster tool scheduling. In Chapter 2 we dealt with scheduling of single armed cluster tools. Single armed cluster tools have a simpler architecture than other configurations, but can be difficult to schedule when additional requirements such as re-entrant wafer flow, parallel chambers and multiple recipes are introduced. To solve these problems we proposed a method to transforms the problem into a multi-objective problem by considering the ready times of the resources as objectives to minimize. Only feasible states were generated based on the initial state of the system. These feasible states form a multi-objective shortest path problem and give us O((r+1)mn) as an upper bound for the number of states, where r, n, and m are the number of different wafer recipes, wafers, and processing chambers. We solved this problem with implicit enumeration by making our scheduling decisions based on the Pareto optimal solutions for each state. The experimental results showed that the proposed algorithm can quickly solve large sized problems including ones with arbitrary initial tool states, changing recipes, re-entrant wafer flows, and parallel chambers. In Chapter 3 we developed a general scheduling algorithm for Petri nets. Petri nets are widely used for modelling and analysis of discrete event dynamic systems and are therefore suitable for scheduling more complex cluster tool architectures such as dual armed cluster tools. We defined a data structure for noncyclic Petri net scheduling problems and then transformed the scheduling problem into an equivalent multi-...