同時に実行できるジョブ数が時間とともに変わっても、締切が共通なら、完了件数の下限を数学的に保証する算法が得られた。将来のジョブ到着は未知、容量変化は既知という条件で、中断したジョブを廃棄しても、全ジョブを事前に知る最適な実行計画の11分の1以上を完了する。
変動する容量と連続実行を同時に満たす
Googleが扱うスケジューリング問題では、処理容量を各時刻に同時実行できるジョブ数の上限として表す。実行予定は、その上限をどの時刻でも超えないように組む必要がある。
各ジョブには実行可能になる時刻、締切、処理時間、完了時の価値がある。選んだジョブは許された時間帯の中で連続して完了させるため、開始時刻だけでなく、終了まで容量を確保できるかが実行条件になる。
事前に計画できれば完了件数の半分を保証
全ジョブと容量変化を事前に知るオフライン設定では、貪欲法のGreedyが最も早く終了するジョブを順に選ぶ。Googleによると、全ジョブの価値が等しい場合、この方法は最悪の条件でも最適な完了件数の2分の1以上を保証する。
この保証は、同時に1件だけ実行できる固定容量の設定と同じ水準で成立する。ジョブごとに価値が異なる場合は、主双対法を使った別の算法により、完了したジョブの価値の合計に最適値の4分の1以上を保証する。
逐次到着では中断後の扱いが保証を分ける
オンライン設定では容量変化を事前に知っていても、これから到着するジョブは分からない。性能は、全ジョブを事前に知る最適な算法と成果を比較した最悪時の比率である「競争比」で評価する。
中断したジョブを最初からやり直せるモデルでは、それまでの処理は失われるが、ジョブ自体は残る。最も早く終了するジョブを選ぶGreedyの変種は、この条件で競争比2分の1を達成する。
一方、中断したジョブを廃棄するモデルでは、締切を共通に限定しなければ、どの算法も競争比をゼロに近づけるジョブ列に直面し得る。新しい算法は、全ジョブが同じ締切を持つ条件を利用して、この問題に対応する。
共通締切を使い、短いジョブへ予定を更新する
同時に1件だけ実行する設定では、新しい算法は到着済みのジョブを重ならない時間区間へ割り当て、暫定的な予定を保つ。新着ジョブはまず空き区間へ追加し、追加できなければ、十分に短い場合に未開始のジョブと置き換える。
置換もできなければ、新着ジョブの処理時間を実行中ジョブの残り時間と比べ、短い場合に実行中のジョブを中断する。いずれも適用できない場合は新着ジョブを廃棄し、この順序で最初に適用できる操作を選ぶ。
Googleによると、この算法を任意の容量変化へ一般化すると、共通締切のもとで競争比11分の1が得られる。中断したジョブを廃棄する条件でも、最適な完了件数の11分の1以上を保証するという最悪時の下限である。