💻 computer science

Machine Learning-Based Waiting Time Prediction for Priority Queues with Preemptive and Non-Preemptive Service Rules

本論文は、リカレントニューラルネットワークをはじめとする機械学習モデルが、待ち行列の長さと顧客の優先度のみを用いて、複雑で時変的な優先度付き待ち行列システムにおける待ち時間を正確に予測できることを示しており、非割り込み型および様々な割り込み型のサービス規則において、決定木ベースの手法を凌駕している。

原著者： Sahil Singh Bhandari, T.G. Deepak

公開日 2026-06-29

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Sahil Singh Bhandari, T.G. Deepak

原論文は CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたは、テーマパークの混雑した列に並んでいるところを想像してください。通常、ルールは「先着順」です。しかし、この論文で著者たちが取り上げているのは、もっと複雑な列です。そこには、VIP（優先度1）と一般ゲスト（優先度2）が存在します。VIPが割り込むことで、他の人たちの待ち時間が変化します。

大きな問いとして、著者たちはこう尋ねました。「コンピュータプログラム（機械学習）を使って、たとえVIPが次々と割り込んでくる混沌とした状況であっても、ある人の待ち時間を正確に予測できるだろうか？」

以下に、彼らが何を行い、何を見出したのかを、日常的な例えを用いて分かりやすく解説します。

列の3つのルール

著者たちは、列の仕組みにおける3つの異なる「交通ルール」の下で、コンピュータプログラムをテストしました。

「中断なし」ルール（非割り込み型 / Non-Preemptive）: 理容師が客の髪を切っている場面を想像してください。たとえVIPがやってきても、理容師は現在のカットを終えてから切り替えます。椅子に座っている人はそのままの状態です。
「やり直し」ルール（割り込み・リセット型 / Preemptive-Repeat）: シェフがステーキを焼いている場面を想像してください。もしVIPが到着したら、シェフは一般客のステーキの調理を止め、それを捨てて、VIPのために新しいステーキをゼロから作り直します。VIPが終わった後、一般客は最初からステーキを作り直さなければなりません。
「再開」ルール（割り込み・再開型 / Preemptive-Resume）: ビデオゲームのキャラクターがボスと戦っている場面を想像してください。もしVIPが到着したら、戦いは一時停止します。一般客の「体力ゲージ」は、元の位置のまま維持されます。VIPが去った後、戦いは中断した箇所から再び始まります。

データ：200日間のシミュレーション

実際に200日間も列に並んでテストすることはできないため、彼らはデジタル・シミュレーションを構築しました。彼らは以下のような架空の世界を作り出しました。

人々はランダムなタイミングで到着する（列が空いていることもあれば、人で溢れかえることもある）。
人々には2つのタイプがある：VIPと一般客。
彼らは、誰がどれくらい待つかについての膨大なデータを生成するために、このシミュレーションを200「日」間実行しました。

コンテスト：5つのコンピュータ・ブレイン

彼らは、待ち時間の予測においてどのモデルが最も優れているかを決めるため、5種類の異なる「コンピュータの脳（機械学習モデル）」を戦わせました。

「決定木」系の脳 (GBM & Random Forest): これは、一連の「はい／いいえ」の質問を投げかける探偵チームのようなものです。「列は長いか？」「その人はVIPか？」といった具合です。彼らは意思決定ツリーを構築して待ち時間を推測します。また、探偵たちに「VIP用」と「一般客用」の2つの別々のチームに分かれるよう強制するバージョンもテストし、それが効果的かどうかを確認しました。
「タイムトラベラー」の脳 (RNN): これはリカレントニューラルネットワーク（RNN）です。これは、列の「物語」を記憶する脳だと考えてください。単に「今この瞬間」を見るのではなく、直前にどのような人々が到着したかという「順序」を記憶します。例えば、「長い一般客の列の直後にVIPが到着した」ことが、どのような波及効果を生むのかを理解します。

大きな発見

1. 「タイムトラベラー」の脳がレースに勝利
RNN（イベントの順序を記憶するもの）が明確な勝者でした。割り込みが発生する「やり直し」ルールや「再開」ルールにおいて、RNNは最も正確に待ち時間を予測できました。

なぜか？ 優先順位のある列での待ち時間は、単に「今何が起きているか」だけではなく、「直前に何が起きたか」、そして「次に何が起きるか」が重要だからです。RNNはその「物語」を読み取ることに長けています。

2. 「決定木」系の脳は優秀だが、完璧ではない
決定木モデル（GBMとRandom Forest）はまずまずの成績を収めましたが、RNNほど鋭くはありませんでした。割り込みが頻繁に発生する場合、彼らは少し苦戦しました。

3. チームを分けることはあまり役に立たなかった
著者たちは、決定木モデルに対して、VIPと一般客で別々のチームを持たせる（「強制優先度分割」）という試みを行いました。これにより、モデルがより集中して学習できると考えていました。

結果： ほとんど差はありませんでした。標準的なモデルは、すでに自分自身でVIPと一般客の違いを判別できるほど賢かったのです。これは、一人の優れたシェフが両方のメニューをこなせるのに、わざわざ二人のシェフを雇うようなものです。

4. 「魔法の2つの入力」
これが最も驚くべき部分です。通常、待ち時間を完璧に予測するには、到着率、サービス速度、時刻など、あらゆる詳細なデータを知る必要があります。

発見： 著者たちは、モデルがわずか2つの情報だけで、非常に正確に待ち時間を予測できることを発見しました。
1. 現在、列に何人いるか？（待ち人数）
2. その人はVIPか、一般客か？（優先度）
時刻や、人々が通常どのくらいの速さで到着するかといった情報がなくても、現在の混雑状況とその人のステータスを知るだけで、コンピュータは素晴らしい推測を行うことができたのです。

まとめ

この論文は、優先順位のある列の待ち時間を予測するために、超複雑なシステムや膨大なデータポイントは必要ないということを示しています。

もし最高の精度を求めるなら、イベントの順序を記憶できるモデル（RNNなど）を使用してください。
もしシンプルさを求めるなら、列にいる人数を数え、優先度バッジを確認するだけで、驚くほど良い結果を得ることができます。

これは、病院やコールセンターのような実世界のシステムにとって素晴らしいニュースです。なぜなら、それらのシステムは到着率に関する完璧なデータを持っていないことが多いですが、「何人が待っているか」と「誰が重要か」については把握しているからです。これらを用いることで、正確な待ち時間の予測を提供できるようになります。

技術要約：優先度付き待ち行列における機械学習を用いた待ち時間予測

問題提起

本論文は、時変条件下で動作するマルチクラス優先度付き待ち行列システムにおける、過渡的な待ち時間の予測という課題に取り組んでいる。古典的な待ち行列理論は、単純かつ定常なシステムに対して正確な解析解を提供するが、現実世界のアプリケーション（例：医療、コールセンター、物流）では、非定常な到着率、複雑なサービス時間分布、およびプリエンプション（中断・再開）ルールが含まれることが多い。このような環境下では、顧客の待ち時間は現在のキューの状態だけでなく、将来の高優先度到着にも依存するため、解析的な予測は困難となる。

本研究では、限られた運用上の観測データ（具体的には、到着時のキューの長さと顧客の優先度クラス）を用いて、機械学習（ML）モデルが待ち時間を正確に予測できるかどうかを具体的に調査している。この際、基礎となる到着率関数やサービス時間分布の詳細な知識を必要としないことが重要である。

手法

データ生成

著者らは、時変環境下における2クラス優先度付き待ち行列（ $G(t)/G/1$ ）をシミュレートした合成データセット（200日分）を生成した。

到着プロセス： 非定常な到着は、単純な指数分布の仮定を超えた変動性を捉えるために、位相型（PH）分布を用いた区分的に均質な区間を用いてモデル化された。
サービス規律： 以下の3つの異なるサービスルールをシミュレートした：
1. 非プリエンプティブ（Non-Preemptive）： サービス開始後、中断なく継続される。
2. プリエンプティブ・リピート（Preemptive-Repeat）： 高優先度の到着により低優先度のジョブが中断され、再開時にジョブは最初からやり直しとなる。
3. プリエンプティブ・レジューム（Preemptive-Resume）： 高優先度の到着により低優先度のジョブが中断されるが、中断した時点から再開される。
特徴量： 2つの特徴量構成をテストした：
1. 4特徴量セット： 到着時刻、到着間隔、優先度クラス、および到着時のキューの長さ。
2. 2特徴量セット： 優先度クラスおよび到着時のキューの長さのみ。

評価されたモデル

以下の5つの機械学習モデルを比較した：

勾配ブースティング決定木（GBM）： 標準的な決定木のアンサンブル。
強制優先度分割GBM（FS-GBM）： 学習前にデータセットを優先度クラスごとに強制的に分割するバリアント。
ランダムフォレスト（RF）： 標準的な非相関決定木のアンサンブル。
強制優先度分割RF（FS-RF）： 各優先度クラスに対して個別のRFモデルを学習させるバリアント。
リカレントニューラルネットワーク（RNN）： 1日の中での顧客到着のシーケンスにおける時間的依存関係を捉えるために設計されたLSTMベースのアーキテクチャ。

性能評価には、平均絶対誤差（MAE）、平均二乗誤差（MSE）、平方根平均二乗誤差（RMSE）、および決定係数（ $R^2$ ）を用いた。

主な貢献

統一フレームワーク： 本研究は、非プリエンプティブ、プリエンプティブ・リピート、およびプリエンプティブ・レジュームの各規律において、時変到着を用いる非定常データを生成するための統一されたシミュレーションフレームワークを提供している。
優先度を考慮した構造の評価： 優先度を単なる特徴量として扱う標準的なモデルと比較して、データを優先度クラスによってハードスプリットすること（FS-GBM, FS-RF）が予測を改善するかどうかを明示的に検証している。
最小限の情報による実現可能性： 2つの入力（キューの長さと優先度）のみを使用して正確な待ち時間予測が可能であることを示し、データ駆動型のアプローチには詳細なシステムパラメータが必要であるという仮定に疑問を投げかけている。
比較分析： 優先度付き待ち行列の文脈において、決定木ベースのアンサンブル学習とシーケンスベースのディープラーニングモデルとの包括的な比較を行っている。

結果

モデル性能

RNNの優位性： リカレントニューラルネットワーク（LSTM）は、3つのサービス規律および両方の特徴量設定において、一貫して最も高い精度を達成した。これは、特にサービスの中断が複雑な依存関係を生み出すプリエンプティブな設定において、複雑な時間的ダイナミクスをモデル化する能力を示している。
- 非プリエンプティブの設定（4特徴量）では、RNNは0.987の $R^2$ を達成し、決定木ベースのモデルの約0.94と比較して高い値を示した。
- 最も複雑なシナリオであるプリエンプティブ・レジュームの設定において、RNNは0.987の $R^2$ を維持したが、決定木ベースのモデルは約0.927に低下した。
決定木の安定性： GBMおよびランダムフォレストモデルは、特に非プリエンプティブの設定において、安定かつ競争力のある性能を提供した。しかし、プリエンプティブなシナリオではRNNと比較して精度が低下した。
強制分割の非効率性： 「強制優先度分割」バリアント（FS-GBMおよびFS-RF）は、標準的なモデルと比較して、わずかな、あるいは一貫性のない改善しか示さなかった。著者らは、標準的な決定木モデルは、優先度が入力特徴量として含まれている場合、優先度固有の非線形性を暗黙的に学習する能力が既に備わっており、明示的なハードスプリットは不要であると結論付けている。

特徴量の削減

入力特徴量を4つから2つに削減（到着時刻と到着間隔を削除）しても、性能の低下は緩やかであった。

RNNは最小限の入力を用いても強力な予測力を維持し、非プリエンプティブの場合で $R^2=0.974$ 、プリエンプティブ・レジュームの場合で $R^2=0.972$ を達成した。
決定木モデルも安定しており、キューの長さと優先度が予測に必要な情報の大部分をエンコードしていることを示唆している。

意義と主張

本論文は、機械学習、特にRNNのようなシーケンスベースのモデルが、優先度付きサービスシステムにおけるリアルタイムの待ち時間予測において、伝統的な解析手法に代わる実用的かつ強力な選択肢となることを主張している。

実用的な展開可能性： キューの長さと優先度のみを使用して正確な予測が可能であるという発見は、大きな実用的利点として強調されている。多くの現実世界のシステム（病院、コールセンターなど）では、詳細な到着率関数やサービス分布は未知であるか、推定が困難であるが、キューの長さと優先度は容易に観測可能である。
プリエンプションへの対応： 本研究は、MLモデルが中断のロジックを明示的にモデル化することなく、プリエンプション（リピートおよびレジュームの両方）の複雑な影響を効果的に捉えられることを示している。これは解析的に困難なタスクである。
モデル選択： RNNは時間的ダイナミクスを捉える上で最も効果的であると特定されたが、決定木モデルも、解釈性やより単純なアーキテクチャが好まれる場合には、信頼性が高く安定した代替手段として提示されている。
構造的変更の限界： 本論文は、明示的に優先度分割を強制しても性能は大幅には向上しないと控えめに結論付けており、現代的なアンサンブル手法は、標準的な特徴量として含めることで優先度の不均一性を処理するのに十分に堅牢であることを示唆している。

著者らは、本研究が古典的な待ち行列理論と現代のデータ駆動型予測の架け橋となり、限られたデータ利用可能性と動的な動作条件を備えたシステムに適したフレームワークを提供することを強調している。