時間付きペトリネットにおける最小初期マーキング問題に対する発見的解法TPMとTMDLO

摘要

本稿で対象とする時間付きペトリネットに対する最小初期マーキング問題（TPMIM）は「時間付きペトリネットTPN，発火回数ベクトルXが与えられたとき，発火回数ベクトルを満たし，かつ，実行終了時間がπ以下である発火系列δが存在する初期マーキングのうち，総トークン数が最も少ない初期マーキングを求めよ」と定義される．TPMIMの定義において，各トランジションの時間遅れ，および実行終了時間を削除した問題はペトリネットの最小初期マーキング問題（MIM）とよばれ、システムの最適初期資源配分に関わる問題の一つである。MIMはNP－困難であることが知られており、いくつかの発見的解法が提案されている。その中でAADOは，計算機実験比較により既存解法の中では最も性能が良いことが示されている。本稿では，MIMに対する解法であるAADOとAMDLOをMIMに拡張することにより，それぞれ発見的解法TPMとTMDLO牟して提案し，計算機実験によってその性能を検証する．