An extended event graph with negative places and tokens for time window constraints

Abstract

We introduce places with negative holding times and tokens with negative token counts into a timed event graph in order to model and analyze time window constraints. We extend the enabling and firing rules for such an extended event graph named a negative event graph (NEG). We develop necessary and sufficient conditions based on the circuits for which the NEG is live, that is, an infinite sequence of feasible firing epochs exist for each transition. We prove that the minimum cycle time is the same as the maximum circuit ratio of the circuits with positive token counts. We also show that when there exists circuits with negative token counts, the maximum cycle time is bounded and the same as the minimum circuit ratio of such circuits. A scheduling example for a robot-based cluster tool with wafer residency time constraints for semiconductor manufacturing is explained.