Petri net truncation: an effective approach to solving complex scheduling problem

A Petri net truncation technique is proposed to ease the computational demand in some applications problems. The truncation technique is used to convert the search in a large Petri net into that in several smaller subnets. Each subnet is examined separately, and therefore the search effort is reduced. An overall optimum schedule may be obtained by combining the sub-schedules resulted from the subnet-wide search. The question of how each sub-schedule should be generated is addressed. Two new algorithms for the subnet-wide search that would take a global perspective while searching for a sub-schedule are developed. The resulting sub-schedules may not have a minimum makespan by themselves, but their combination is guaranteed to yield an overall optimal schedule