離散型シミュレーション
【りさんがたしみゅれーしょん (discrete-event simulation)】
概要
待ち行列型モデルの混雑現象を分析・評価するためのシミュレーションのこと. システムの状態変化を起こす出来事は事象と呼ばれ,離散事象システムを対象とするので離散事象(型)シミュレーションとも呼ばれる.システムへの要素(顧客, 呼, ジョブ等)の到着のしかた, サービスのしかた,要素の動き等でモデルが規定される. 到着やサービスの確率的な変動を乱数によって再現し, 混雑状況を分析することが多い.多数の商用ソフトウェアが提供されている.
詳説
離散型シミュレーションは, 離散事象型シミュレーションとも呼ばれ, 待ち行列タイプのモデルのシミュレーションを指す. ここで, 事象 (event)とはシステムに状態変化を起こす瞬間的な出来事を指し, 単純な待ち行列システムにおける典型的な事象として, 顧客の到着やサービスの終了が上げられる.
[待ち行列モデルのシミュレーションとその応用]
離散型シミュレーションが扱うモデルは, 待ち行列モデルあるいは離散事象ダイナミカルシステム等の名で呼ばれ, なんらかのサービスを受けにシステムに到着する要素(工場やコンピュータのジョブ, サービスシステムの客, 電話の呼等)の混雑現象を分析・評価することを目的とする. 基本的に, 要素の到着時間間隔, サービス時間, サーバーの数, サービス提供順序, 待ち場所の容量, 要素の系内の動き等の特性を定めることでモデルが定義される.
自動化・情報化の進展に伴って, 待ち行列型のモデルで表現可能, かつ, シミュレーションによる分析・評価を必要とする大規模システムが随所に存在する. 待ち行列理論に基づく解析結果も有用であるが, 現実システムの多くは待ち行列理論で解析的に扱うことの困難な要因を含む場合が多く, 現実的な分析をしようとするとシミュレーションに頼らざるを得ない場合が少なくない. このようなシステムの典型には, 工場等の生産システムやロジスティクスシステム, 通信・コンピュータシステムがあげられ, シミュレーションがシステム設計時の性能評価に必要不可欠なツールとなっている. 実際は, 生産シミュレータやLANシミュレータというような形で, シミュレーションの詳細を知らなくても性能評価が可能なシミュレータが数多く提供され, 活用されている.
シミュレーションは, かつてはシステム設計や改善活動における事前評価のための利用が圧倒的多数を占めた. しかし, シミュレーション技術の普及・発展に伴って, 日々の運用にもシミュレーションが活用されるようになっている. その典型はスケジューリング分野であり, スケジューラと呼ばれるソフトウェアはシミュレーション機能を備えているのが普通である.
各種イベントやファーストフード, また, テレフォンショッピングやソフトウェアの相談センター等の電話応対サービス等, 各種サービスシステムの性能評価にもシミュレーションがよく用いられている.
[離散型シミュレーションの要素技術]
シミュレーションはいろいろな側面を有する総合的なシステム分析技術である [3]. このため, 離散型シミュレーションをとりまく要素技術はきわめて広汎多岐にわたり, 主要なものだけでも以下があげられる:
(1) 事象処理の方法論(事象処理ロジックとデータ構造, 並列処理等)
(2) モデル規定の方法
(3) 乱数発生(擬似一様乱数, 特定の分布に従う乱数)
(4) 入力確率分布の同定
(5) 出力結果の統計的分析
(6) 出力結果のアニメーション表示
(7) 実験の計画と分散減少法
(8) シミュレーションによる最適化
(9) 結果のプレゼンテーション
ユーザーが詳細を知らなくとも技法が利用可能であること, つまり, 技法がブラックボックス化されていることが技法の普及発展に必要である. 上にあげた要素技術のうち(1), (2), (3)は, ユーザが中身の詳細を知らなくても技術を使いこなせるという意味で, ほぼ完全にブラックボックス化され, (5), (6)もブラックボックス化が進みつつある.
[離散型シミュレーションのモデル化]
離散型シミュレーションにおけるモデル化のポイントを以下に整理する:
(1) システムの境界の明確化: どこからどこまでをモデル化の対象とするかを定める
(2) 詳細度の決定: システム内をどれだけ詳しく見るか, すなわち, 抽象化の度合いを定める.
(3) システム内を動き回るものの明確化: 待ち行列システムの中を動き回る「もの」(以下, 「要素」)がなにかを明らかにする.
(4) リソースの明確化: 待ち行列システムには, 通常, 容量の限られたリソースが存在し, システム内を動き回る要素が限られたリソースを使用/占有してサービスを受ける. なにをリソースとみたてるかやどれだけのリソースがシステム内に存在するかを明らかにする.
(5) 要素の系外からの到着のしかたを規定: 要素が, 系外からどのようなタイミングでどこに到着するかを規定する. 通常, 要素の到着時間間隔の分布や, 場合によってはさらに同時に到着する要素数の分布を指定することによって, 系外からの要素の到着が定められることが多い.
(6) 要素へのサービスに必要なリソースの決定とリソースの競合解決規則の規定: 要素に特定のサービスを提供するために, どのリソースを使用/占有してサービスを受けるかを明らかにする. また, 要素間のリソースの競合をいかに解決するかを規定する.
(7) サービスに要する時間の規定: サービス時間を規定する. 通常, サービス時間の分布を定め, 擬似乱数を発生させて実際のサービス時間を決定することが多い.
(8) 要素の動きの規定: 要素がシステム内をいかに動くかを定める.
(9) 要素の系外への退去の規定: 要素が, どこでシステム内から退去するかを規定する.
多くの実際問題では, モデルの境界, 詳細度や, 何を要素とするかがあらかじめ決まっている訳ではない. これらをどうとらえるかが分析の大枠, したがって, その効果や有用性を規定することが少なくない.
[事象処理と時間の進め方]
離散型シミュレーションでは, システムの状態変化をもたらす(離散)事象を, 発生時刻順に追跡し, 事象発生時にモデルで規定されたシステムの状態変化を(論理的に)発生させながら, システムの動的な挙動を再現してゆく. 将来発生予定の事象を事象カレンダ, 事象チェイン等の名前で呼ばれる事象リスト (event list)として, また混雑に伴う待ち行列もリストとして表現し, 事象リスト中で発生予定時刻が最早の事象を取り出し, その処理を繰り返す. 実際のソフトウェアでは, 処理効率を上げるためにデータ構造等に様々な工夫がなされている.
離散型シミュレーションの事象処理は, 時間的に隣りあう事象間ではシステムの状態が変化しないと考え, 事象発生時にシステムがどう変化するかを時刻順に追跡することによって進めるので, 時間の進み方は一般に不均等となる. このような時間の進め方, すなわち, 時間制御方式 (time advance mechanism)は事象-事象時間進行方式と呼ばれ, 時間の刻み幅を定めて「コマ」を進めていく連続型シミュレーション等の単位時間進行方式と対比される.
[実験の計画と結果の統計的分析]
不確定な要素を含む確率的なシミュレーションを実行するためにはコンピュータ上で生成される擬似乱数が用いられる. 乱数の出方によってシミュレーションの結果が変わるので: (1)シミュレーションの繰り返し回数, (2)一回のシミュレーションの長さ, (3)乱数の設定, (4)初期条件の設定, など, 実験の計画を立てる必要がある. また, 離散型シミュレーションから得られるデータは非定常的で自己相関をもつことが多いので, 実験の計画や結果の統計的解析には注意を要する [1] [2].
参考文献
[1] J. Banks, J. S. Carson and B. Nelson, Discrete-Event Simulation (it 2nd ed.), Prentice Hall, 1995.
[2] A. M. Law and D. E. Kelton, Simulation Modeling and Analysis (it 2nd ed.), McGraw Hill, 1991.
[3] J. Banks, ed., Handbook of Simulation, John Wiley & Sons, 1998.