Scheduling manufacturing systems with blocking: a Petri net approach

This paper introduces a Petri net-based approach for scheduling manufacturing systems with blocking. The modelling of the job routings and the resource and blocking constraints is carried out with the Petri net formalism due to their capability of representing dynamic, concurrent discrete-event dynamic systems. In addition Petri nets can detect deadlocks typically found in systems with blocking constraints. The scheduling task is performed with an algorithm that combines the classical A* search with an aggressive node-pruning strategy. Tests were conducted on a variety of manufacturing systems that included classical job shop, flexible job shop and flexible manufacturing scheduling problems. The optimisation criterion was makespan. The experiments show that the algorithm performed well in all types of problems both in terms of solution quality and computing times.