スケジューリング問題

スケジューリング問題とは,多くの仕事を限られた資源を用いて処理しなければならないという状況で,効率的な資源の割り当て方を求め,最適なスケジュールを導き出す問題です.このため,生産計画や配送など,現実世界における多くの問題はスケジューリング問題として表すことができます.こうしたスケジューリング問題を速く効率的に解くことのできる方法は,多くの分野で作業の効率化につながるため,盛んに研究が行われている分野でもあります.しかし,現実世界の問題はそれぞれに異なる複雑な制約を持ち,ある問題に対する効率的な解法が必ずしも別の問題に適用可能とは限りません.
 
このため,一般的なスケジューリング問題に対する研究は,現実のスケジューリング問題で共通する要素をもとに,ジョブショップスケジューリング問題 (JSP) と呼ばれるモデルを設定し,JSPの効率的な解法を探るといった方法で行われています.JSPにおいては,仕事は複数の作業工程から構成され,それぞれの仕事のなかでは作業工程をあらかじめ定められた順番に処理しなければなりません.また,作業工程は処理することのできる機械はあらかじめただひとつに定められており,それぞれの機械は同時には1つの作業工程のみを処理することができます.このとき,JSPの目的は作業工程の処理の順序を並べ替えることで,すべての仕事の総所要時間が小さいスケジュールを得ることとなります.たとえば,下図は3仕事3機械のJSPとそれに対する総所要時間が13のスケジュール例を示しています.
 
図3
 
一般的に,JSPを解く場合には,あるスケジュールを探索の開始点として,1つの作業工程について作業順序を変更するなどの微小な変更を加え,より総所要時間の短いスケジュールへの更新を繰り返すという方法がとられます.こうした方法は局所探索法と呼ばれ,次の動画のような探索を行います.
 

 
このほかには,同じ機械で複数の作業工程が処理可能となるとき,残りの作業量が多い作業工程を優先するなど,一定の割付規則にしたがってスケジュールを構築する方法が挙げられます.こうした方法は,有効な割付規則を用いることができれば,短時間で効率的なスケジュールを生成することができますが,実際には,与えられる問題によって有効な割付規則は異なります.さらに,同じスケジュールの中でも,前半と後半では別の規則を利用すべきといった状況も考えられるため,割付規則による解法で,局所探索法よりも良いスケジュールを求めることは困難です.
 
そこで,われわれは割付規則を部分的に適用することにより,スケジュールの改善を可能とし,局所探索法と割付規則の双方を取り入れた解法を研究しています.具体的には,割付規則を適用する範囲を時間窓という形で決定し,その内側についてのみ順序の変更を行うことで新しいスケジュールを生成します.また,このときに用いる時間窓や規則の内容については,遺伝的アルゴリズムにより最適な値を求めています.こうした方法を用いることで,下の動画のとおり,大幅にスケジュールを変更しつつ探索を行うことが可能となり,より効率的に良いスケジュールを求めることが可能となりました.
 
図2