Evaluating the robustness of scheduling in uncertain environment with Petri nets

This paper is about the incremental computation of control sequences in uncertain environments where uncontrollable events may occur. Timed Petri nets under earliest firing policy are used for that purpose. The aim is to drive the marking of the net from an initial value to a reference one, in minimal or near-minimal time, by avoiding forbidden markings, deadlocks and dead branches. The approach is inspired from model predictive control and at each step only a small area of the reachability graph is explored in order to limit the computation effort. For each computed sequence the probability of uncontrollable events is estimated to evaluate the robustness of the resulting trajectory. A sufficient condition is provided to compute robust trajectories. The proposed results are applicable to a large class of discrete event systems in the domains of flexible manufacturing, communication, computer science, transportation and traffic. In particular, they are suitable for dynamical deadlock-free scheduling and reconfiguration problems in uncertain environments.