Decomposition of timed Petri Nets for solving scheduling problems with multiple entities

In this paper, we propose a general decomposition and coordination method for timed Petri Nets to determine an optimal transition firing sequence to minimize an objective function. A timed Petri Net model for multiple entities is decomposed into several subnets in which the optimal firing sequence for each subnet is easily solved in polynomial computational complexity. The solution of each subproblem is coordinated by repetitive optimization of the number of tokens for duplicated places. The proposed method is applied to a flowshop scheduling problem. The effectiveness of the proposed method is confirmed by comparing the performance between the simulated annealing method.