Reducing the computational complexity of scheduling problems in Petri nets by means of transformation rules
Juan Carlos Mugarza, Hervé Camus, J.C. Gentina, Enrique Teruel, Manuel Silva · 2002
Scheduling problems are very important in order to optimise the behaviour of discrete events dynamic systems. Nevertheless, the computation of scheduling policies turns out to be NP-hard in most interesting cases in practice. The purpose of the paper is to apply transformation/reduction rules to the solution of the scheduling problem. These kind of rules have already been applied to the analysis of autonomous Petri nets or to program coding optimisation by means of time Petri nets. Here, reduction is intended to preserve the existence of at least one optimal solution for the scheduling problem. In many practical cases, transformation/reduction allows us to alleviate the computational problem of synthesising an optimal schedule. We show its usefulness by means of an illustrative example.