An optimal periodic scheduler for dual-arm robots in cluster tools with residency constraints

This paper discusses a scheduling technique, for cluster tools, that addres ses postprocessing residency constraints and throughput requirements. The r esidency constraints impose a limit on the postprocessing time that a mater ial unit spends in a processing module. The technique searches in the time and resource domains for a feasible schedule with a maximum throughput. It operates in two main phases; the initial one of which (and the lower comple xity one) computes a simple periodic schedule. For a large number of proble m instances, the simple periodic schedule feasibly solves the problem. If a feasible schedule cannot be found in the first phase, the scheduler enters phase two (the higher complexity one) to compute a feasible schedule. Duri ng this phase, the scheduler incrementally increases the period only if nec essary, to keep the throughput at a maximum. Several heuristics are designe d and added to reduce the complexity of the scheduling algorithm. The resul ting schedules are deadlock free, since resources are scheduled according t o the times that they are available. Analytical and experimental analyzes d emonstrate the correctness and efficiency of our proposed technique.