Truncation of Petri net models for simplifying computation of optimum scheduling problems

Abstract Scheduling problems with constraints on precedence relationship and resource requirements may be modeled by timed Petri nets. A search algorithm that integrates the execution of the Petri net and the modified branch-and-bound technique is presenyed to seek for an optimum schedule. For many practical applications, their Petri net models tend to become large, and the number of transitions in the models grows rapidly. Unreasonably long computing time and large computer memory may be required to implement the above algorithm. To solve this complexity problem, a truncation technique is developed to divide the Petri net into smaller subnets. It is illustrated by a practical example that the technique greatly reduces the demand of the overall computing time and computer memory for reaching an optimum solution.