フィード・バックのある最適なジョブ・スケジューリング:割り引かれた場合

概要

論文の詳細を見る
いくつかのジョブより構成されているM/GI/1待ち行列を考える。サービス中のジョブは他のジョブによって割り込まれることはないとする(nonpreemptive)。待ち行列へのジョブの到着は、外からのポアソン到着以外に、ジョブのサービス終了時における多重フィード-バックを許すことにする。目的は、割り引かれた無限期計画の利益を最大にする最適なジョブ・スケジューリングを求めることである。通常の待ち行列理論における平均待ち時間最小の問題にも容易に変換することが出来る。このモデルはbandit problemとして定式化され、Harrisonの巧妙な手法が用いられる。最適政策は優先順位の方式(priority rule)により達成され、それぞれのクラスの優先順位はindexにより計算される。このモデルの応用として、preemptiveなM/GI/1待ち行列の離散近似を考える。各クラスのジョブは量子時間nonpreemptiveなサービスを行い、サービスが終了しなければ、次のクラスにフィードーバックするとすればpreemptiveな待ち行列の近似となる。それでジョブがシステムから出る確率P_kが単調増加、単調減少、または一山型の3つの場合について、最適政策の優先順位を求めた。