A Branch and Bound Algorithm for Cyclic Scheduling of Timed Petri Nets

Abstract

A timed Petri net (TPN) has been widely used for modeling, scheduling, and analyzing discrete event dynamic systems. This study examines cyclic scheduling problems of a TPN to minimize the cycle time especially for automated manufacturing systems. Appropriate token routing at each conflict place can make a TPN repeat an identical firing sequence. We propose a systematic procedure to transform a TPN with such cyclic token routing into an equivalent timed event graph (TEG) for which the cycle time and firing schedules can be evaluated by a linear programming (LP). Based on the transformation procedure, we develop an efficient branch and bound algorithmto solve the scheduling problem. A partial solution is defined as a partial token route that has only a subset of token routes for determining the complete schedule. The lower bound of a partial solution is determined by the cycle time of a TEG that has the partial token route. The cycle time of a TEG with an additional token route for a new partial solution is computed by a dual-simplex algorithm which avoids solving the LP completely again. A dynamic branching strategy that prevents unnecessary branching for the scheduling decision is also proposed. We demonstrate the computational efficiency through intensive experiments of cluster tools and robotic flow shops.

Note to Practitioners-There are many systems which repeat an identical task sequence such as manufacturing systems, transportation systems, and robotic systems. Maximizing the throughput of such a system by optimizing the cyclic task sequence, which is called a cyclic scheduling problem, has been an important problem. In order to deal with cyclic scheduling problems, this paper uses a timed Petri net (TPN) which is a graphical modeling tool for discrete event dynamic systems. As the size of a TPN model increases, the computational complexity of the cyclic scheduling problem exponentially increases due to the combinatorial nature of sequencing problems. Therefore, an efficient algorithm for optimal cyclic scheduling of TPNs is needed. This study proposes an efficient branch and bound algorithm which is a kind of a tree search algorithm. Several important techniques are developed. First, a transformation procedure from a TPN to a timed event graph is developed. Second, an efficient branching rule which reduces the size of the search tree is proposed. Third, the lower bound which evaluates the cycle time of each node in the search tree is suggested. We verify the efficiency of the algorithm through the experiments on manufacturing systems such as a cluster tool and a robotic flow shop.