next up previous
: 巡回セールスマン問題(TSP) : 近似アルゴリズムでよく取り扱われる問題(代表的なものの一部) : 近似アルゴリズムでよく取り扱われる問題(代表的なものの一部)

スケジューリング問題

機械がm台あり, 処理しなければならない仕事がn個あるとする. どの仕事もどの機械でも処理でき, その処理時間は機械に依存せずに一定であると 仮定する.しかし仕事が異なれば処理時間も異なる可能性があることに注意. このとき, どの機械にどのような順番で仕事を処理させれば, 全体の処理時間を 一番短くできるか? 例えば, 以下の図のように仕事が7個あり, うまくスケジュール すると左側の様に短い時間ですむが, へたなスケジューリングをすると右側の 様に長く時間がかかってしまう場合がある.



Koichi Yamazaki 平成12年3月15日