ペトリネットの初期マーキング最少化のための発見的アルゴリズムAADO

摘要

本稿で対象とするペトリネットの最小初期マーキング問題(MIM)は、システムの最適初期資源配分に関わる問題の一つである。 MIMはNP-困難であることが知られており、いくつかの発見的解法が提案されている。 その中でAAD+は,計算機実験比較により既存解法の中で最も性能が良いことが示されている。 本稿では,AAD+に新たなトランジション選択法を組み込み,トークン付加操作の改良と発火系列探索法として最も高性能な解法FEIDEQの組み込みを行った手法AADOを提案し,計算機実験によりその効果を検証する。 今回の実験では,660個の入力例をAADOに適用した結果,求められた初期マーキングのトークン数は平均してAAD+より約3少なくなり,計算時間はAAD+の約1.2倍となった.