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
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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Satoru OCHIIWA, Satoshi TAOKA, Masahiro YAMAUCHI, Toshimasa WATANABE, "Two Enhanced Heuristic Algorithms for the Minimum Initial Marking Problem of Petri Nets" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 11, pp. 2732-2744, November 2009, doi: 10.1587/transfun.E92.A.2732.
Abstract: The minimum initial marking problem of Petri nets (MIM) is defined as follows: "Given a Petri net and a firing count vector X, find an initial marking M0, with the minimum total token number, for which there is a sequence δ of transitions such that each transition t appears exactly X(t) times in δ, the first transition is enabled at M0 and the rest can be fired one by one subsequently." In a production system like factory automation, economical distribution of initial resources, from which a schedule of job-processings is executable, can be formulated as MIM. AAD is known to produce best solutions among existing algorithms. Although solutions by AMIM+ is worse than those by AAD, it is known that AMIM+ is very fast. This paper proposes new heuristic algorithms AADO and AMDLO, improved versions of existing algorithms AAD and AMIM+, respectively. Sharpness of solutions or short CPU time is the main target of AADO or AMDLO, respectively. It is shown, based on computing experiment, that the average total number of tokens in initial markings by AADO is about 5.15% less than that by AAD, and the average CPU time by AADO is about 17.3% of that by AAD. AMDLO produces solutions that are slightly worse than those by AAD, while they are about 10.4% better than those by AMIM+. Although CPU time of AMDLO is about 180 times that of AMIM+, it is still fast: average CPU time of AMDLO is about 2.33% of that of AAD. Generally it is observed that solutions get worse as the sizes of input instances increase, and this is the case with AAD and AMIM+. This undesirable tendency is greatly improved in AADO and AMDLO.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.2732/_p
Copier
@ARTICLE{e92-a_11_2732,
author={Satoru OCHIIWA, Satoshi TAOKA, Masahiro YAMAUCHI, Toshimasa WATANABE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Two Enhanced Heuristic Algorithms for the Minimum Initial Marking Problem of Petri Nets},
year={2009},
volume={E92-A},
number={11},
pages={2732-2744},
abstract={The minimum initial marking problem of Petri nets (MIM) is defined as follows: "Given a Petri net and a firing count vector X, find an initial marking M0, with the minimum total token number, for which there is a sequence δ of transitions such that each transition t appears exactly X(t) times in δ, the first transition is enabled at M0 and the rest can be fired one by one subsequently." In a production system like factory automation, economical distribution of initial resources, from which a schedule of job-processings is executable, can be formulated as MIM. AAD is known to produce best solutions among existing algorithms. Although solutions by AMIM+ is worse than those by AAD, it is known that AMIM+ is very fast. This paper proposes new heuristic algorithms AADO and AMDLO, improved versions of existing algorithms AAD and AMIM+, respectively. Sharpness of solutions or short CPU time is the main target of AADO or AMDLO, respectively. It is shown, based on computing experiment, that the average total number of tokens in initial markings by AADO is about 5.15% less than that by AAD, and the average CPU time by AADO is about 17.3% of that by AAD. AMDLO produces solutions that are slightly worse than those by AAD, while they are about 10.4% better than those by AMIM+. Although CPU time of AMDLO is about 180 times that of AMIM+, it is still fast: average CPU time of AMDLO is about 2.33% of that of AAD. Generally it is observed that solutions get worse as the sizes of input instances increase, and this is the case with AAD and AMIM+. This undesirable tendency is greatly improved in AADO and AMDLO.},
keywords={},
doi={10.1587/transfun.E92.A.2732},
ISSN={1745-1337},
month={November},}
Copier
TY - JOUR
TI - Two Enhanced Heuristic Algorithms for the Minimum Initial Marking Problem of Petri Nets
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2732
EP - 2744
AU - Satoru OCHIIWA
AU - Satoshi TAOKA
AU - Masahiro YAMAUCHI
AU - Toshimasa WATANABE
PY - 2009
DO - 10.1587/transfun.E92.A.2732
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2009
AB - The minimum initial marking problem of Petri nets (MIM) is defined as follows: "Given a Petri net and a firing count vector X, find an initial marking M0, with the minimum total token number, for which there is a sequence δ of transitions such that each transition t appears exactly X(t) times in δ, the first transition is enabled at M0 and the rest can be fired one by one subsequently." In a production system like factory automation, economical distribution of initial resources, from which a schedule of job-processings is executable, can be formulated as MIM. AAD is known to produce best solutions among existing algorithms. Although solutions by AMIM+ is worse than those by AAD, it is known that AMIM+ is very fast. This paper proposes new heuristic algorithms AADO and AMDLO, improved versions of existing algorithms AAD and AMIM+, respectively. Sharpness of solutions or short CPU time is the main target of AADO or AMDLO, respectively. It is shown, based on computing experiment, that the average total number of tokens in initial markings by AADO is about 5.15% less than that by AAD, and the average CPU time by AADO is about 17.3% of that by AAD. AMDLO produces solutions that are slightly worse than those by AAD, while they are about 10.4% better than those by AMIM+. Although CPU time of AMDLO is about 180 times that of AMIM+, it is still fast: average CPU time of AMDLO is about 2.33% of that of AAD. Generally it is observed that solutions get worse as the sizes of input instances increase, and this is the case with AAD and AMIM+. This undesirable tendency is greatly improved in AADO and AMDLO.
ER -