研究成果 > アルゴリズムのデモ > 資源制約付スケジューリング問題

資源制約付スケジューリング問題とは

複数の作業が与えられたとき，各作業をいつ開始するかを決定する問題です．ただし，各作業には，処理時間と 処理に必要な資源（機械や人など）が与えられていて，同時に使用できる資源の量は限られています（つまり， 同時に処理できる作業は限られている）．また，作業 i が完了しないと作業 j を開始できない，といった制約 （先行制約と呼ばれます）もあります．目的は，これらの制約の下で，すべての作業をできるだけ早く完了する ことです．

ここでは簡単のため，資源制約付スケジューリング問題の特殊な場合である，「ジョブショップ問題」を例に説 明します．

ジョブショップ問題では，n個のジョブと，m台の機械が与えられています．各ジョブは，それぞれ m個の作業 （第 1段階〜第 m段階）で構成されていて，ジョブを終えるためには，すべての作業を与えられた順番にしたがっ て処理していかなくてはなりません．（例えば，第1段階の作業が終わらないと第2段階の作業を始めることはで きない．これは「先行制約」と考えられます．）また，各作業には，それを処理することにできる機械が決まっ ていて，1台の機械で，複数の仕事を同時に処理することはできません．（ジョブショップを資源制約付スケジュー リングと捉えた場合，各機械は，使用可能量が常に 1 である資源，と考えられます．）

以下に，4ジョブ（Job-A, B, C, D）3機械（machine X, Y, Z）の例を示します．

第1段階 第2段階 第3段階
Job-A machine X, 5時間 machine Y, 8時間 machine Z, 2時間
Job-B machine Z, 7時間 machine X, 3時間 machine Y, 9時間
Job-C machine X, 1時間 machine Z, 7時間 machine Y, 10時間
Job-D machine Y, 4時間 machine Z, 11時間 machine X, 7時間

この例では，Job-A を終えるためには，機械 X 上で，5時間かけて第1段階の作業を終えた後，機械 Y 上で，8 時間かけて第2段階を行い，最後に，機械 Z 上で，2時間かけて第3段階の作業を行う必要があります．

各段階においてどのジョブの作業をいつ開始するかによってすべての作業が完了する時刻が変わってきます．例 えば，この問題例に対するスケジュールの一例として次のような作業の開始・終了時刻のスケジュールを立てる とすべての作業を完了するのに 33時間を要します．

第1段階 第2段階 第3段階
Job-A 0 - 5 5 - 13 25 - 27
Job-B 0 - 7 7 - 10 24 - 33
Job-C 5 - 6 7 - 14 14 - 24
Job-D 0 - 4 14 - 25 25 - 32

デモでは，ガントチャートと呼ばれるスケジュール表が表示されます．ガントチャートでは，各長方形が作業に 対応し，横軸は時間を表します（よって，各長方形の幅は処理時間に対応します）．表の上半分には，各ジョブ ごとのスケジュールが，下半分には，機械ごとのスケジュールが表示されています．各ジョブに対し第1段階， 第2段階，第3段階の三つの作業があります（それぞれオレンジ色，茶色，こげ茶色で表示されています）．これ らの作業が決められた順序で処理されていることを確認して下さい．

デモの説明

4ジョブ（Job-A, B, C, D）3機械（machine X, Y, Z）のジョブショップ問題をメタヒューリスティクスと呼ば れる手法で解く様子を表示します．この方法は，スケジュールの変更を繰り返し行うもので，変更により，全体 の完了時刻が早くなる場合もあれば，逆に遅くなる場合もあるのが特徴です．スケジュールの改善と改悪を繰り 返しながら，より良いスケジュールを探索する様子をご覧下さい．

ガントチャート中，「best solution till now」と書かれた白い縦線が，計算過程で求まった最も早い完了時刻 を示しており，スケジュールが更新される度に更新されます．また，ガントチャート左端中央の Step は，修正 回数を表しています．

遊び方

このデモでは，各作業に対し，使用する機械や処理時間を変更することができます． 「この条件で解く」をクリックすると，条件変更がガントチャートに反映されます．