離散イベントシミュレーション

システムの状態とは、研究対象となるシステムの主要な特性を捉える変数の集合である。時間経過に伴う状態軌跡S(t)は、イベントが発生するたびに値が変化する階段関数によって数学的に表現できる。

シミュレーションでは、モデル化対象システムに適した測定単位で、現在のシミュレーション時間を追跡する必要があります。連続シミュレーションとは異なり、離散イベントシミュレーションでは、イベントが瞬間的に発生するため、時間が「飛び飛び」します。つまり、シミュレーションが進むにつれて、時計は次のイベント開始時刻にスキップします。

シミュレーションは、少なくとも 1 つのシミュレーション イベントのリストを保持します。これは、以前にシミュレーションされたイベントの結果として保留されているが、それ自体はまだシミュレーションされていないイベントをリストするため、保留イベント セットと呼ばれることがあります。イベントは、発生する時刻と、そのイベントをシミュレーションするために使用されるコードを示すタイプによって記述されます。イベント コードがパラメータ化されているのが一般的で、その場合、イベント記述にはイベント コードのパラメータも含まれます。イベント リストは、将来イベント リスト(FEL) または将来イベント セット(FES)とも呼ばれます。^{[ 3 ] [ 4 ] [ 5 ] [ 6 ]}

事象が瞬間的に発生する場合、時間的に継続する活動は一連の事象としてモデル化されます。一部のシミュレーションフレームワークでは、事象の発生時刻を時間間隔として指定することができ、各事象の開始時刻と終了時刻を指定できます。

瞬間的なイベントに基づくシングルスレッドのシミュレーションエンジンは、現在処理中のイベントを1つしか持ちません。一方、マルチスレッドのシミュレーションエンジンや、間隔ベースのイベントモデルをサポートするシミュレーションエンジンは、複数の現在処理中のイベントを持つ場合があります。どちらの場合も、現在処理中のイベント間の同期には重大な問題があります。

保留中のイベント セットは通常、イベント時間でソートされた優先度キューとして構成されます。^{[ 7 ]}つまり、イベントがイベント セットに追加される順序に関係なく、厳密に時系列順に削除されます。さまざまな優先度キューの実装が離散イベント シミュレーションのコンテキストで研究されています。^{[ 8 ]}研究された代替案には、スプレー ツリー、スキップ リスト、カレンダー キュー、^{[ 9 ]}およびラダー キューが含まれます。 ^{[ 10 ] [ 11 ]}マルチ コアまたはメニー コアCPUなどの大規模並列マシン では、同時実行スレッド間の同期のコストを削減するために、保留中のイベント セットは非ブロッキング アルゴリズムに依存して実装できます。 ^{[ 12 ] [ 13 ]}

通常、イベントはシミュレーションの進行に合わせて動的にスケジュールされます。たとえば、上記の銀行の例では、時刻 t におけるイベント CUSTOMER-ARRIVAL は、CUSTOMER_QUEUE が空で TELLER がアイドル状態の場合、時刻 t+s に発生する後続イベント CUSTOMER-DEPARTURE の作成を含みます。ここで、s は SERVICE-TIME 分布から生成される数値です。

シミュレーションでは、システムモデルに応じて様々な種類の乱数を生成する必要があります。これは、1つまたは複数の擬似乱数発生器によって実現されます。真の乱数ではなく擬似乱数を使用することで、シミュレーションを全く同じ動作で再実行する必要がある場合に有利になります。

離散イベントシミュレーションで使用される乱数分布の問題の1つは、イベント時間の定常状態分布が事前にわからない場合があることです。その結果、保留イベントセットに配置される最初のイベントセットの到着時間は、定常状態分布を代表するものではありません。この問題は通常、シミュレーションモデルをブートストラップすることで解決されます。最初の保留イベントセットに現実的な時間を割り当てる努力は限定的です。しかし、これらのイベントは追加のイベントをスケジュールし、時間の経過とともにイベント時間の分布は定常状態に近づきます。これをシミュレーションモデルのブートストラップと呼びます。実行中のモデルから統計情報を収集する際には、定常状態に達する前に発生するイベントを無視するか、ブートストラップ動作が定常状態動作に圧倒されるほど十分に長くシミュレーションを実行することが重要です。（このブートストラップという用語の使い方は、統計学とコンピューティングの両方での使用法とは対照的です。）

シミュレーションでは通常、システムの統計情報を追跡し、関心のある側面を定量化します。銀行の例では、平均待ち時間を追跡することが重要です。シミュレーションモデルでは、パフォーマンス指標は確率分布から解析的に導出されるのではなく、モデルの異なる実行、つまり複製における平均値として算出されます。出力の品質を評価するために、通常は信頼区間が構築されます。

イベントはブートストラップ方式で発生するため、理論的には離散イベントシミュレーションは永久に実行可能です。したがって、シミュレーション設計者はシミュレーションの終了時期を決定する必要があります。典型的な選択肢としては、「時刻 t で」または「n 個のイベントを処理した後」、あるいはより一般的には「統計的尺度 X が値 x に達したとき」などがあります。

Pidd (1998) は、離散イベントシミュレーションに3段階アプローチを提案した。このアプローチでは、第1段階では、次の時系列イベントにジャンプする。第2段階では、その時点で無条件に発生するすべてのイベント（Bイベントと呼ばれる）を実行する。第3段階では、その時点で条件付きで発生するすべてのイベント（Cイベントと呼ばれる）を実行する。この3段階アプローチは、同時発生するイベントをコンピュータリソースを最も効率的に利用できるように順序付けるイベントベースのアプローチを改良したものである。この3段階アプローチは、多くの商用シミュレーションソフトウェアパッケージで使用されているが、ユーザーの視点からは、その基盤となるシミュレーション方法の詳細は一般的に隠されている。

シミュレーション手法は、複雑な環境における問題の診断に特に有効です。制約理論は、システムにおけるボトルネックを理解することの重要性を示しています。ボトルネックを特定して解消することで、プロセスとシステム全体を改善できます。例えば、製造業では、過剰在庫、過剰生産、プロセスのばらつき、ルーティングやシーケンスのばらつきなどがボトルネックの原因となることがあります。シミュレーションモデルを用いてシステムを正確に文書化することで、システム全体を俯瞰的に把握することが可能になります。

システムの稼働モデルを用いることで、経営陣はパフォーマンスの要因を理解することができます。シミュレーションは、従業員の稼働率、納期遵守率、不良率、キャッシュサイクルなど、あらゆるパフォーマンス指標を組み込むように構築できます。

手術室は通常、複数の外科分野で共有されています。これらの手術の性質をよりよく理解することで、患者のスループットを向上させることができる可能性があります。^{[ 14 ]}例：心臓手術に平均4時間かかる場合、手術室のスケジュールを8時間から9時間に変更しても、患者のスループットは向上しません。一方、ヘルニア手術に平均20分かかる場合、回復室の収容能力と平均滞在時間を考慮しないと、1時間追加してもスループットの向上にはつながらない可能性があります。

多くのシステム改善アイデアは、確かな原則や実績のある手法（リーン生産方式、シックスシグマ、TQMなど）に基づいているにもかかわらず、システム全体の改善には至らない。シミュレーションモデルを用いることで、ユーザーはシステム全体の状況を踏まえて、パフォーマンス改善のアイデアを理解し、検証することができる。

シミュレーションモデリングは、潜在的な投資をモデル化するためによく用いられます。投資をモデル化することで、意思決定者は情報に基づいた意思決定を行い、潜在的な選択肢を評価することができます。

離散イベントシミュレーションは、コンピュータネットワークにおいて、実際の導入前に新しいプロトコルやさまざまなシステムアーキテクチャ（分散型、階層型、集中型、P2Pなど）をシミュレーションするために使用されます。サービス時間、帯域幅、パケット損失、リソース消費量など、さまざまな評価指標を定義することが可能です。