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." 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 M0, with a small number of tokens, even if other algorithms are too slow to compute M0 as the size of an input instance gets very large." />


Improved Heuristic Algorithms for Minimizing Initial Markings of Petri Nets

Satoshi TAOKA  Masahiro YAMAUCHI  Toshimasa WATANABE  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E88-A   No.11   pp.3051-3061
Publication Date: 2005/11/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Concurrent/Hybrid Systems: Theory and Applications)
Category: 
Keyword: 
Petri nets,  minimal initial marking problems,  legal firing sequence problems,  deficient siphons,  heuristic algorithms,  experimental evaluation,  

Full Text: PDF(393KB)
>>Buy this Article


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 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." 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 M0, with a small number of tokens, even if other algorithms are too slow to compute M0 as the size of an input instance gets very large.