La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Two Enhanced Heuristic Algorithms for the Minimum Initial Marking Problem of Petri Nets Deux algorithmes heuristiques améliorés pour le problème de marquage initial minimum des réseaux de Petri

Satoru OCHIIWA, Satoshi TAOKA, Masahiro YAMAUCHI, Toshimasa WATANABE

  • Vues en texte intégral

    0

  • Citer

Résumé:

Le problème du marquage initial minimum des réseaux de Petri (MIM) est défini comme suit : "Étant donné un réseau de Petri et un vecteur de comptage de tirs X, retrouver un marquage initial M0, avec le nombre total minimum de jetons, pour lequel il existe une séquence δ de transitions telle que chaque transition t apparaît exactement X(t) fois dans δ, la première transition est activée à M0 et le reste peut être déclenché un par un par la suite. » Dans un système de production tel que l'automatisation d'usine, la distribution économique des ressources initiales, à partir de laquelle un calendrier de traitement des tâches est exécutable, peut être formulée comme suit : MIM. AAD est connu pour produire les meilleures solutions parmi les algorithmes existants. Bien que les solutions proposées par AMIM+ est pire que ceux de AAD, Il est connu que AMIM+ est très rapide. Cet article propose de nouveaux algorithmes heuristiques AADO et à la AMDLO, versions améliorées des algorithmes existants AAD et à la AMIM+, respectivement. La netteté des solutions ou le temps CPU court sont la cible principale de AADO or AMDLO, respectivement. Il est démontré, sur la base d'une expérience informatique, que le nombre total moyen de jetons dans les marquages ​​initiaux par AADO est environ 5.15 % de moins que celui de AAD, et le temps CPU moyen par AADO représente environ 17.3 % de celui d'ici AAD. AMDLO produit des solutions légèrement pires que celles de AAD, alors qu'ils sont environ 10.4 % meilleurs que ceux de AMIM+. Bien que le temps CPU de AMDLO est environ 180 fois celui de AMIM+, c'est quand même rapide : temps CPU moyen de AMDLO est d'environ 2.33% de celui de AAD. Généralement, on observe que les solutions se détériorent à mesure que la taille des instances d'entrée augmente, et c'est le cas avec AAD et à la AMIM+. Cette tendance indésirable est grandement améliorée dans AADO et à la AMDLO.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.11 pp.2732-2744
Date de publication
2009/11/01
Publicisé
ISSN en ligne
1745-1337
DOI
10.1587/transfun.E92.A.2732
Type de manuscrit
Special Section PAPER (Special Section on Theory of Concurrent Systems and its Applications)
Catégories

Auteurs

Mots-clés

Table des matières