整数計画アプローチ (スケジューリング問題の)

【せいすうけいかくあぷろーち (integer programming approach to scheduling problem)】

スケジューリング問題は0-1変数を用いて整数計画問題として定式化することができる. 1つの仕事あるいは作業はある時点においてある1台の機械でしか処理できず, また機械はある時点において1つの作業しか処理できないことをはじめとするスケジュールに対する各種の条件を, 0-1変数を含む数式によって表現する. 例えば, 一機械問題の場合には, 仕事$i$を$j$番目に処理するとき$x_{ij}=1$とし, その他の場合を$0$とする.