「分割アルゴリズム (スケジューリングの)」の版間の差分
ナビゲーションに移動
検索に移動
Albeit-Kun (トーク | 投稿記録) |
|||
| (2人の利用者による、間の2版が非表示) | |||
| 1行目: | 1行目: | ||
| − | 【ぶんかつあるごりずむ (decomposition algorithm for scheduling)】 | + | '''【ぶんかつあるごりずむ (decomposition algorithm for scheduling)】''' |
大規模なスケジューリング問題を小さな部分問題に分割し, そのそれぞれを解いて得られる解を総合して原問題の解を求める分割法に基づくアルゴリズムをいう. 例えば, 一機械総納期遅れ最小化問題に対して, 納期順に並べた仕事列の中で最大の処理時間をもつ仕事を<math>k\,</math>番目に処理するとしたとき, 所定の条件を満たすならばその前後の2個の仕事群に分割することができることが知られており, これを用いたダイナミックプログラミングによる効率的解法が報告されている. | 大規模なスケジューリング問題を小さな部分問題に分割し, そのそれぞれを解いて得られる解を総合して原問題の解を求める分割法に基づくアルゴリズムをいう. 例えば, 一機械総納期遅れ最小化問題に対して, 納期順に並べた仕事列の中で最大の処理時間をもつ仕事を<math>k\,</math>番目に処理するとしたとき, 所定の条件を満たすならばその前後の2個の仕事群に分割することができることが知られており, これを用いたダイナミックプログラミングによる効率的解法が報告されている. | ||
| + | |||
| + | [[Category:スケジューリング|ぶんかつあるごりずむ]] | ||
2008年11月13日 (木) 15:50時点における最新版
【ぶんかつあるごりずむ (decomposition algorithm for scheduling)】
大規模なスケジューリング問題を小さな部分問題に分割し, そのそれぞれを解いて得られる解を総合して原問題の解を求める分割法に基づくアルゴリズムをいう. 例えば, 一機械総納期遅れ最小化問題に対して, 納期順に並べた仕事列の中で最大の処理時間をもつ仕事を番目に処理するとしたとき, 所定の条件を満たすならばその前後の2個の仕事群に分割することができることが知られており, これを用いたダイナミックプログラミングによる効率的解法が報告されている.
