Non-Cyclic Scheduling of a Wet Station

We examine a non-cyclic scheduling problem of a wet station that performs cleaning processes for removing residual contaminants on wafer surfaces. Several chemical and rinse baths, and multiple robots for transporting jobs are linearly combined in a wet station. A wet station in a fab tends to have different types of jobs. Therefore, it is realistic to consider non-cyclic release of jobs into a wet station. We therefore examine a non-cyclic scheduling problem of a wet station that determines the task sequence of each robot so as to minimize the makespan of a given sequence of different jobs. We develop an efficient branch and bound procedure by examining the scheduling problem. To do this, we first develop a Petri net model for the scheduling problem. By identifying deadlock prevention conditions from the Petri net model, we eliminate partial solutions in advance that eventually will lead to a deadlock. By examining the feasible transition firings or state transition behavior of the Petri net model, we branch only feasible partial solutions or nodes that correspond to feasible state transitions or transition firings. We also develop a tight lower bound based on the bottleneck workload of the baths. We prove computational efficiency of the branch and bound procedure for practical problems.