An approach using petri nets and improved heuristic search for manufacturing system scheduling

Petri nets have been extensively used to model the dynamics of various types of manufacturing systems due to their power to capture the complex characteristics of many of such systems. However, the “state explosion” has prevented their use for solving real scheduling problems. To date, Petri net based algorithms have only been tested with relatively small problems with few machines and few jobs. This paper proposes an algorithm that combines the A* search with both an aggressive node-pruning strategy and improved evaluation functions to generate near-optimal schedules. Extensive computational tests were conducted on a wide variety of scenarios ranging from classical job shop to complex FMS scheduling problems. The obtained results show very promising results in terms of solution quality and computing times.