Improved Heuristic Algorithms for Minimizing Initial Markings of Petri Nets

Satoshi TAOKA; Masahiro YAMAUCHI; Toshimasa WATANABE

doi:10.1093/ietfec/e88-a.11.3051

Improved Heuristic Algorithms for Minimizing Initial Markings of Petri Nets

Satoshi TAOKA, Masahiro YAMAUCHI, Toshimasa WATANABE

Full Text Views

0

Share
Cite this

Summary :

The minimum initial marking problem MIM of Petri nets is described as follows: "Given a Petri net and a firing count vector X, find an initial marking M₀, 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 M₀ and the rest can be fired one by one subsequently." This paper proposes two heuristic algorithms AAD and AMIM + and shows the following (1) and (2) through experimental results: (1) AAD is more capable than any other known algorithm; (2) AMIM + can produce M₀, with a small number of tokens, even if other algorithms are too slow to compute M₀ as the size of an input instance gets very large.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E88-A No.11 pp.3051-3061

Publication Date: 2005/11/01

Publicized

Online ISSN

DOI: 10.1093/ietfec/e88-a.11.3051

Type of Manuscript: Special Section PAPER (Special Section on Concurrent/Hybrid Systems: Theory and Applications)

Category

Cite this

Copy

Satoshi TAOKA, Masahiro YAMAUCHI, Toshimasa WATANABE, "Improved Heuristic Algorithms for Minimizing Initial Markings of Petri Nets" in IEICE TRANSACTIONS on Fundamentals, vol. E88-A, no. 11, pp. 3051-3061, November 2005, doi: 10.1093/ietfec/e88-a.11.3051.
Abstract: The minimum initial marking problem MIM of Petri nets is described as follows: "Given a Petri net and a firing count vector X, find an initial marking M₀, 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 M₀ and the rest can be fired one by one subsequently." This paper proposes two heuristic algorithms AAD and AMIM + and shows the following (1) and (2) through experimental results: (1) AAD is more capable than any other known algorithm; (2) AMIM + can produce M₀, with a small number of tokens, even if other algorithms are too slow to compute M₀ as the size of an input instance gets very large.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e88-a.11.3051/_p

Copy

@ARTICLE{e88-a_11_3051,
author={Satoshi TAOKA, Masahiro YAMAUCHI, Toshimasa WATANABE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Improved Heuristic Algorithms for Minimizing Initial Markings of Petri Nets},
year={2005},
volume={E88-A},
number={11},
pages={3051-3061},
abstract={The minimum initial marking problem MIM of Petri nets is described as follows: "Given a Petri net and a firing count vector X, find an initial marking M₀, 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 M₀ and the rest can be fired one by one subsequently." This paper proposes two heuristic algorithms AAD and AMIM + and shows the following (1) and (2) through experimental results: (1) AAD is more capable than any other known algorithm; (2) AMIM + can produce M₀, with a small number of tokens, even if other algorithms are too slow to compute M₀ as the size of an input instance gets very large.},
keywords={},
doi={10.1093/ietfec/e88-a.11.3051},
ISSN={},
month={November},}

Copy

TY - JOUR
TI - Improved Heuristic Algorithms for Minimizing Initial Markings of Petri Nets
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 3051
EP - 3061
AU - Satoshi TAOKA
AU - Masahiro YAMAUCHI
AU - Toshimasa WATANABE
PY - 2005
DO - 10.1093/ietfec/e88-a.11.3051
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E88-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2005
AB - The minimum initial marking problem MIM of Petri nets is described as follows: "Given a Petri net and a firing count vector X, find an initial marking M₀, 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 M₀ and the rest can be fired one by one subsequently." This paper proposes two heuristic algorithms AAD and AMIM + and shows the following (1) and (2) through experimental results: (1) AAD is more capable than any other known algorithm; (2) AMIM + can produce M₀, with a small number of tokens, even if other algorithms are too slow to compute M₀ as the size of an input instance gets very large.
ER -