• Langue : Français
• Discipline : Productique, automatique et informatique industrielle
• Identifiant : Thèse : 2000LIL10021
• Type de thèse : Doctorat
• Date de soutenance : 01/01/2000

Résumé en langue originale

La complexité de l'exploration du graphe d'accessibilité est alors repoussée au niveau de la résolution de contraintes : la propagation des contraintes nous interdit d'explorer les branches qui correspondent à des séquences de steps qui ne mènent pas au marquage final désiré. Pour résoudre les problèmes d'ordonnancement, il est nécessaire d'introduire l'aspect temporel. Nous définissons un modèle de réseau de Pétri temporisé et autonome. A chaque marquage, nous associons une date pour chacune des places. Cette date correspond à la date de création du dernier jeton dans cette place. Ainsi, le temps n'est pas contrôlée par une horloge externe. Ce sont les tirs des transitions qui font varier localement au niveau des places le temps. L'algorithme d'accessibilité peut alors être adapté pour ce type de réseau. Nous obtenons alors des séquences de tirs dates qui peuvent etre interprétés comme des ordonnancements réalisables. Le problème de l'accessibilité est d'un grand intérêt théorique. En effet, plusieurs problèmes relatifs à l'analyse des réseaux de Pétri peuvent être formulés en terme d'accessibilité. L'exploration du graphe d'accessibilité n'est pas une méthode de résolution satisfaisante du fait de l'explosion combinatoire. La notion de marquage partiel, permet de réduire cet explosion combinatoire. Les marquages partiels sont des marquages dont les composantes contiennent des variables contraintes. Ainsi, un marquage partiel représente un ensemble de marquages obtenus en instanciant les variables tout en respectant la contrainte qui les lie. De la même facon, un step partiel est un step non-clos et dénote ainsi un ensemble de steps. Le tir d'un step partiel à partir d'un marquage partiel capture le tir de n'importe quel step à partir d'un marquage quelconque représente par le marquage partiel. Nous montrons que la recherche de l'accessibilité d'un marquage peut être réduit à une recherche d'un marquage donné dans une séquence de marquages partiels.