Task level optimum scheduling by truncated Petri nets applied to operation of multi-robot workcell

In an earlier paper, the authors presented a method of applying Petri nets to model and analyze task level scheduling. A truncation technique, which converted a search in a large Petri net into that in several smaller subnets, was proposed. In certain circumstances the search algorithms for the subnets failed to find a proper sub-schedule for each subnet which would yield an overall optimal schedule. A comprehensive and more efficient search algorithm for the subnets is presented. This algorithm treats each subnet from a global perspective by satisfying all the inter-subnet constraints. Thus an overall optimum schedule is guaranteed. The algorithm is more efficient because no modification to the sub-schedules is required. The application of the Petri net truncation technique to manufacturing systems is illustrated by an example of task-level scheduling in a multi-robot workcell