状態機械ワークフローネットのAbort型動的変更に対する最悪変更時間の計算複雑さと性能解析について

摘要

本稿では，状態機械ワークフローネットに対してAbort型動的変更を適用した場合の最悪変更時間を求める関越の計算複雑さと他の変更方式と優劣を判定する方法について放論する．まず｝最恵変更時間を求める問題の計算複雑さについて検討する．問題を決定問題に焼き直し，形式的な定義を与え，この問題がクラスNPに属すことを明らかにした．Abort型動的変更の最悪変更時間の計算は手に負えない可能性があるが，コストの見積もりや他の変更方式とαり七掛こは必ずしも共催は必要ではない．そこで，最悪変更時間の上界と下界を与え，それらを用いて他の変更方式との優劣を多項式時間で判定可能な条件を明らかにした．270パターンのワークフローの動的変更を対象としてそれらの妥当性を評価する実験を行った．Flush方式に対する条件は事例の到着間隔が大きい場合あるいは小さい場合に適用でき，SCO方式に対する条件は事例の到着間l掛こよらず適用できることがわかった.