Scheduling cluster tools in wafer fabrication using candidate list and simulated annealing

This paper presents a new method for scheduling cluster tools in semiconductor fabrication. A cluster tool consists of a group of single-wafer chambers organized around a wafer transport device, or robot. Cluster fabrication system considered in this paper consists of serial cluster tools. Due to constraints imposed by multiple routes of each wafer type and machines with no buffer, it is difficult to find an optimal or near-optimal schedule. In order to determine the sequence of the operations to be released and the assignment of the machine to each operation, the proposed method uses a job requirement table with random keys as a solution representation. Simulated annealing seeks the optimal or near-optimal sequence and machine assignment of the operations. In this paper, the scheduling objective is to find a schedule with minimum makespan. A Gantt chart is obtained as the final schedule. To handle the constraints, the proposed method uses a candidate list. To determine which operation can be scheduled in considering the constraints, a negotiation procedure between the operations in the candidate list and a current state of the system is introduced. To show the effectiveness of the proposed method, scheduling example of a real cluster fabrication system is presented. Scheduling results are compared with those obtained by using several dispatching rules. From the experimental results, it is shown that the proposed method is promising.