An approach based on timed Petri nets and tree encoding to implement search algorithms for a class of scheduling problems
Résumé
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.
Domaines
Automatique
Origine : Fichiers produits par l'(les) auteur(s)
