An approach based on timed Petri nets and tree encoding to implement search algorithms for a class of scheduling problems

Scheduling problems have been approached several times by Petri nets. Indeed, the usage of a Petri net model guarantees the feasibility of the candidate solutions, but it does not provide an accurate evaluation of the time required to complete the considered workshop. For this purpose, a class of timed Petri nets, namely structured nets, is defined and the encoding of the structure and time information of such nets as a tree is presented. This encoding, in combination with the resolution of some linear matrix inequalities, is used to estimate the residual time required to complete each job of the considered workshop. The main advantage of this computation is to provide an estimation of the residual time as an interval that includes necessarily the exact residual duration. Consequently, the lower bound of the interval never overestimates the exact duration and can be used as a part of the cost function involved in many exploration algorithms as the A* or the Beam Search algorithms. In this paper, the proposed estimation function is used with the Hybrid Filtered Beam Search algorithm and performances are discussed for several examples of workshops. The paper also illustrates that the approach can be combined with supervisory control to accelerate the convergence of the exploration since deadlocked solutions can be eliminated directly in the model.