Université Lille1 - Sciences et Technologies L'accessibilité dans les réseaux de Pétri : une approche basée sur la programmation par contraintes 629.8 Programmation (mathématiques) Graphes, Théorie des Petri, Réseaux de Ordonnancement (gestion) Text Electronic Thesis or Dissertation fr 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. application/pdf 1 : 1 Mo https://pepite-depot.univ-lille.fr/RESTREINT/Th_Num/2000/50376-2000-65.pdf Benasser Ahmer 1900-01-01 061055611 Thèse : 2000LIL10021 2000-01-01 Productique, automatique et informatique industrielle Université Lille1 - Sciences et Technologies 026404184 Doctorat non oui Gentina Jean-Claude 059857501 ddc:620 ASCII PDF 9999 restriction 2012-01-01 9999-01-01 restriction 2012-01-01 9999-01-01