分割アルゴリズム (スケジューリングの)

【ぶんかつあるごりずむ (decomposition algorithm for scheduling)】

大規模なスケジューリング問題を小さな部分問題に分割し, そのそれぞれを解いて得られる解を総合して原問題の解を求める分割法に基づくアルゴリズムをいう. 例えば, 一機械総納期遅れ最小化問題に対して, 納期順に並べた仕事列の中で最大の処理時間をもつ仕事を$k$番目に処理するとしたとき, 所定の条件を満たすならばその前後の2個の仕事群に分割することができることが知られており, これを用いたダイナミックプログラミングによる効率的解法が報告されている.