Improved Heuristic Algorithms for Minimizing Initial Markings of Petri Nets(<Special Section>Concurrent/Hybrid Systems : Theory and Applications)

概要

論文の詳細を見る
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_0, 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_0 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_0, with a small number of tokens, even if other algorithms are too slow to compute M_0 as the size of an input instance gets very large.
社団法人電子情報通信学会の論文
2005-11-01