Non-cyclic scheduling and timing control of timed Petri nets

Abstract

There have been many approaches and algorithms for scheduling diverse complex discrete event systems, such as workflows, job shops, flow shops, and automated manufacturing systems. Most of these methods have focused on their effectiveness or efficiency in solving their own problems. Hence, they tend to ignore the issue of compatibility with other scheduling problems, and the solution methods are ad hoc and hard to be used for other scheduling problems even with small changes. Since various scheduling problems with different constraints and objectives can be easily represented with a timed Petri net, we examine non-cyclic scheduling problems of timed Petri nets which have start and end transitions. We first develop an efficient branch and bound procedure for obtaining an optimal solution based on a reachability tree. A dynamic branching strategy that branches only enabled transitions is used, and a lower bound is computed by relaxing resource capacity constraints. The widely used resource-based lower bound is also generalized to timed Petri nets. The efficiency of the algorithm is verified with many complicated cluster tool scheduling problems. However, the reachability tree is so large for even a small Petri net that it takes a long time to search all possible paths in a reasonable time. Thus, we propose a new type of a reachability tree called a time-feasible reachability tree to reduce the search space of a scheduling problem by analyzing a firing sequence of transitions in a timed Petri net. A linear cluster tool scheduling problem with multiple robots and different types of wafers is easily handled with the new reachability tree. In addition to sequencing decision while assuming deterministic process times, we also analyze a schedulability issue of a timed event graph when activities or tasks have time window constraints and bounded time variations. We develop necessary and sufficient conditions for which there always or never exists a feasible firing sch...