Deadlock-free scheduling for flexible manufacturing systems using untimed Petri nets and model predictive control

This paper proposes algorithms that incrementally compute control sequences that drive the marking of untimed Petri nets from an initial value to a reference one, avoiding forbidden states with a length or duration that approaches the minimal value. The proposed algorithms are applicable to a large class of discrete event systems with or without temporal specifications in particular in the domain of flexible manufacturing, communication and computer science or transportation and traffic. To overcome the most burdensome part of the computations, the sequences encoded in a small area of the reachability graph are worked out. The main contribution is to propose an estimation of the minimal length or duration of the remaining sequences to the reference based on the computation of the firing count vectors. The approach is suitable for deadlock-free scheduling problems encountered with flexible manufacturing systems.