Optimal Scheduling of Timed Petri Nets With Resource Marking and Ready Times: Application to Robotic Flow Shops

Many scheduling problems, especially for automated manufacturing systems, have been addressed with a timed Petri net (TPN) by developing optimal or heuristic algorithms based on it. However, most of them have focused on cyclic scheduling, in which a firing sequence of transitions in a TPN is repeated, to minimize the cycle time. A few studies have considered a noncyclic scheduling problem but focused on developing a heuristic search method. In this study, a noncyclic scheduling problem for automated manufacturing systems is considered with a TPN to obtain an optimal solution with the makespan measure. Specifically, a scheduling problem of a dual-gripper robotic flow shop with a given job sequence is considered to determine an optimal robot task sequence. We first define resource marking and resource ready times for the dual-gripper robotic flow shop based on a TPN and develop dominance properties based on them. Then, an optimal algorithm that eliminates dominated nodes in a reachability tree by using those properties is proposed. The experimental results show that the proposed algorithm significantly outperforms the existing studies.