Near-optimal scheduling with general service times and IHR abandonment times

忙しいコーヒーショップを想像してみてください。客が飲み物を求めて列を作っていますが、そこにはある仕掛けがあります。すべての客には秘密のタイマーが備わっているのです。もし待ち時間が長すぎると、彼らは苛立ち、何も買わずに店を去ってしまいます。バリスタ（サーバー）たちは、次に誰を接客すべきかを決めなければなりません。最も長く待っている人を優先すべきでしょうか？ それとも、エスプレッソ一杯ですぐに終わる人を優先すべきでしょうか？ あるいは、今にも諦めて立ち去ろうとしている人を優先すべきでしょうか？ これこそが「スケジューリング」と呼ばれる問題の核心であり、リソースが限られ、時間が刻々と経過していく中で、タスクを最適に整理する方法を解き明かす数学およびコンピュータサイエンスの一分野です。

スケジューリングの世界では、考慮すべきコストが主に2種類あります。第一に、「保持コスト（holding cost）」です。これは、客が列の中で待っている間に失われるエネルギーや忍耐力のようなものです。第二に、「放棄ペナルティ（abandonment penalty）」です。これは、客が怒って去ってしまうことによる売上の損失と、評判の低下です。何十年もの間、数学者たちはこのパズルを解こうと試みてきましたが、彼らは通常、大きな簡略化を行ってきました。つまり、サービス時間（飲み物を作るのにかかる時間）と忍耐時間（客が待てる時間）が、「指数分布」と呼ばれる単純で予測可能なパターンに従うと仮定してきたのです。これは、コイン投げがすべて完全にランダムで独立していると仮定するようなものです。この仮定は数学的には扱いやすくしますが、現実の世界とは異なります。現実には、非常に長い時間がかかるタスクもあれば、非常に忍耐強い人もいれば、非常に短気な人もいます。

Samuli Aalto氏によるこの論文は、このより複雑で現実的なバージョンの問題に取り組んでいます。著者は、単純で予測可能なパターンを想定する代わりに、あらゆる種類のサービス時間（例えば、非常に時間がかかる複雑なラテなど）を許容し、「IHR（増加ハザード率）」と呼ばれる特定のタイプの短気さを扱っています。IHRとは、待ち時間が長くなるにつれて、人がうんざりして去ってしまう確率が高まるという、より人間らしい振る舞いを表す高度な概念です。この論文では、人々を接客する最適な順番を見つけ出すために、「ウィトル指数（Whittle index）」という巧妙な数学的ツールを使用しています。主な知見は、この新しい手法が、現実世界の複雑なシナリオを扱うことで、従来の標準的な経験則（$c\mu/\theta$ルールと呼ばれるもの）を一貫して上回るという点です。著者は、簡略化されたバージョンの問題に対して、この新しい数式が数学的に健全であることを証明し、その後、シミュレーションを通じて、この新しい方法が従来の最善策よりも多くの費用を節約し、より多くの顧客を満足させられることを示しました。

不機嫌な列の物語

混沌とした空港の保安検査場の様子を思い浮かべてください。そこにはセキュリティ・オフィサー（サーバー）のチームと、旅行者（顧客）の流れがあります。各旅行者には、2つの目に見えない時計が動いています。1つ目の時計は、彼らのサービス時間（バッグをスキャンし、IDを確認するのにかかる時間）をカウントダウンしています。もう1つの時計は、彼らの忍耐時間（飛行機に乗るのを諦めて帰宅するまでに、どれだけの時間待てるか）をカウントダウンしています。

昔の数学者がこの列をモデル化していたときは、両方の時計が非常に特定の「無記憶的（memoryless）」な方法でカウントダウンすると仮定していました。それは、どれだけ長くそこに立っていたとしても、次の1分間に立ち去る確率が到着した瞬間と全く同じであると述べるようなものです。これが「指数的」な仮定です。これは数学的には便利なトリックですが、現実の人間はこれほど単純ではありません。実際には、20分間待たされた後では、到着した直後の時点よりも、次の1分間に立ち去ってしまうリスクははるかに高くなります。これが、論文でIHR（増加ハザード率）と呼ばれているものです。つまり、待ち時間が長くなるほど、辞めてしまうリスクが高まるということです。

また、著者は、現実のサービス時間は常に単純ではないことにも気づきました。バッグのスキャンが瞬時に終わることもあれば、スーツケースの変なロックのせいで永遠に時間がかかることもあります。この論文では、一般的なサービス時間を許容しており、数学的に、待ち時間の形状（素早いものから複雑で長いものまで）を扱うことができます。

魔法の数式：ウィトル指数

では、どのようにして誰を接客するかを決めるのでしょうか？ 論文では、列にいる一人ひとりのスコアカードとして「ウィトル指数」を導入しています。このスコアは単に「誰が一番長く待っているか」だけではありません。それは以下の要素を考慮した複雑な計算です。

1. すでにどれくらい待ったか ($x$)
2. すでにどれくらいのサービスを受けたか ($y$)
3. 客を待たせるためのコスト（保持コスト）
4. 客が去った場合のコスト（放棄ペナルティ）

著者は、この問題の簡略化されたバージョン（新しい人が到着しない「閉じた」システム）において、このスコアカードが数学的に完璧であることを証明しています。これは「インデクサブル（indexable）」であり、これは「今すぐ接客すべき！」から「もう少し待てる」まで、人々をランク付けできることを意味します。

その後、論文はこのスコアカードを、人々が絶えず到着する現実の連続的な世界に適応させています。導き出された数式 $W_k(x, y)$ は、一見すると威圧的な見た目をしていますが、本質的には次のように問いかけています。「もし私がこの人をほんの少しの時間だけ接客したら、その人が去ってしまうリスクと比較して、どれほどの金額を節約できるだろうか？」

対決：新 vs 旧

この新しい「ウィトル指数ポリシー（WHI）」が実際に機能するかどうかを確認するため、著者は数千回のコンピュータ・シミュレーションを実行しました。仮想の空港を設定し、2種類の旅行者を登場させました。

• クラス1： 短い作業（素早いスキャン）だが、忍耐レベルは様々。
• クラス2： 長い作業（複雑なスキャン）だが、忍耐レベルは様々。

彼らは、サービス時間の種類（一様分布、あるいは一部の人が「永遠に」かかることを意味するパレート分布など）と、放棄コスト（客を失うことが安い場合もあれば、大きな損失となる場合もある）を組み合わせて、4つの異なるシナリオをテストしました。

結果は明白でした。新しいウィトル指数ポリシーは、従来の標準である $c\mu/\theta$ ルールを体系的に上回りました。

• 「一様ー一様（Uniform-Uniform）」のシナリオ（全員がある程度予測可能である場合）では、新しいポリシーは従来のルールよりも約**12%から19%**多くコストを節約しました。
• 「一様ーパレート（Uniform-Pareto）」のシナリオ（一部の人に非常に長く予測不可能なサービス時間がかかる場合）では、その差は広がりました。新しいポリシーは、従来のルールよりも**33%から42%**多くコストを節約しました。
• 最も困難なシナリオにおいても、新しいポリシーは一貫して優れており、時には最大**52%**もの差をつけて勝利しました。

また、論文ではこの新しい手法を、「先入れ先出し（First-Come-First-Served：最も古い人を優先する）」や「プロセッサ・シェアリング（Processor-sharing：サーバーの時間を全員に均等に分配する）」といった他の一般的な戦略とも比較しました。結果として、ウィトル指数はそれらすべてを打ち破りました。

なぜこれが重要なのか

重要な教訓は、「完全にランダムである」という仮定を捨て、人々が実際にどのように不機嫌になるかという「厄介な現実」を受け入れることで、より優れたシステムを構築できるということです。コーヒーショップであれ、コールセンターであれ、あるいはデータを処理するコンピュータネットワークであれ、この新しい数式を使用することは、より少ない怒れる顧客の離脱、より少ない時間の浪費、そしてより多くの節約を意味します。著者は単に推測したのではなく、簡略化されたバージョンで数学が機能することを証明し、さらに厳格なシミュレーションを通じて、それが複雑な現実世界において驚異的な効果を発揮することを証明しました。これは、時には「世界はもっと単純である」と決めつけるのをやめることが、問題を解決するための最善の方法であるということを思い出させてくれます。