スケジューリング問題
一般に、スケジューリング問題は、処理すべき仕事と機会が与えられたとき、納期や完了時間などを最小化する規範が
与えられる問題のことをいい、生産ラインにおいてはもちろんのこと、人員配置、コンピュータ(CPU)のジョブ処理など、
様々な分野での応用が期待されている。
しかしながら、現実に直面する問題をそのまま
定式化しようとすると
制約式や
目的関数が
複雑になり、実用上解けない場合が多く、たとえ定式化できたとしてもコンピュータサイエンスの用語でいうところの「
NP完全/NP困難」となってしまう問題も少なくない。
スケジューリング問題は、
工場等での仕事のスケジュール
建設工事等のプロジェクトのスケジュール
バス・列車・航空機等のダイヤと乗員のスケジュール
要員（工場の作業者，病院の医師・看護婦等）のスケジュール
宅急便・郵便・ごみ等の集配スケジュール
大学・予備校等の時間割／教室割スケジュール
等、様々な分野で発生する。