Token delays and generalized workload balancing for timed event graphs with application to cluster tool operation

Abstract

There have been numerous works on controlling task delays in discrete event systems such as automated manufacturing systems. Since the systems are often modelled by timed event graphs, the task delays correspond to token delays in the models. We characterize the token delays based on imbalance between the circuit ratios. We prove that the token delays can be eliminated by balancing the circuit ratios. We propose strategies for balancing circuit ratios or workloads for timed event graphs and apply them to eliminating wafer delays in a cluster tool. We demonstrate that token delay analysis based on circuit ratio imbalance and circuit ratio balancing are effective for identifying and eliminating wafer delays in a cluster tool. We discuss how circuit ratio and circuit ratio balancing can be considered as generalizations of conventional workload and workload balancing for flow lines