Scheduling a wet station using a branch and bound algorithm

摘要

We examine a scheduling problem of a wet station with multiple job flows. The wet station performs cleaning processes for removing residual contaminants after wafer fabrication processes. It consists of several chemical and rinse baths, and multiple transport robots. Most studies on scheduling robotized systems including a wet station assume identical jobs and deal with cyclic scheduling that repeats a predefined work cycle. However, jobs arrive dynamically and many different jobs are processed concurrently at a wet station. We therefore examine a non-cyclic scheduling problem of the wet station to minimize the makespan. We first develop a Petri net model and solve the problem using a branch and bound (B&B) algorithm. We also propose a dynamic branching method and evaluate a lower bound based on a bottleneck process. During searching the nodes, we analyze deadlocks and add places to the Petri net model for precedence relations among the robot tasks by applying the deadlock prevention conditions. We finally show that the proposed B&B algorithm is sufficient to solve practical problems.