イグナル・スクラジのアルゴリズム - じゅんじゅんのメモ帳@ ウィキ

3工程編成のジョブの集合で、すべてのジョブの加工工程順が同一の場面に適用するスケジューリング法を言う。

提唱者：E.Ignall ＆ L.Schrage

このアルゴリズムは「ブランチアンドバウンド法(Branch and Bound Method)」を適応させたものであり、すべての可能性から最適順序付けを求めるのではなく、可能性の部分集合を系統的に順次吟味することによって最適解を求めようとするものである。
すなわち、全ジョブを対象に分岐操作〔branching〕と限界操作〔bounding〕を繰り返し、総所要時間(総生産リードタイム)最小が予見できる部分集合から最適解を求める方法である。
このとき、部分集合のもつ可能解を、目的関数(最短リードタイム)に対する下界〔Lower Bound〕:LBとし、分岐・限界操作時の優先度を決定する尺度とする。
総所要時間最少を目的関数とすることから、最小下界をもつ部分集合が選択され、順次全ジョブの加工順序が決定されることになる。

〔LB〕算定式

Xr	第r番目の分割によって得たジョブの集合
#bar{X}r	第r番目の分割によって得たXr以外のジョブの集合
Ｔk(Xr)	機械ｋにおけるジョブXrを全て加工したときの完了時間
tik	機械ｋにおけるジョブiの加工時間計
LB(Xr)	ジョブXrの下界

としたとき、ジョブの部分集合：Xrの下界：LB(Xr)を次式により求める。

LB(Xr)=	MAX	T1(Xr) + ∑{iε#bar{X}r}{ti,1} + Min{iε#bar{X}r}∑{q=2}^{3}{ti,q} .......〔1-1〕
		T2(Xr) + ∑{iε#bar{X}r}{ti,2} + Min[iε#bar{X}r]ti,3 .......〔1-2〕
		T3(Xr) + ∑{iε#bar{X}r}{ti,3} .......〔1-3〕

〔1-1〕式は、機械M1(第１工程)を基準とした総所要時間最少を期待するものである。
〔1-2〕式は、機械M2(第２工程)を基準とした総所要時間最少を期待するものである。
〔1-3〕式は、機械M3(第３工程)を基準とした総所要時間最少を期待するものである。

基準とした各機械の期待する総所要時間最少の値が異なるとき、順序付け該当ジョブ(部分集合):Xrとして期待する総所要時間最小値は、これらのジョブXrを遂行するのに費やす必要加工時間ととらえることから、最大値を採用することとなる。この最大値を該当ジョブ:Xrの下界:LBとする。

手順

1. 第１番目に順序付けるジョブを見出すために、各ジョブのそれぞれの機械(工程)における完了時間〔Tk(Xr)〕を求める。
2. 第1番目に順序付けようとするジョブの予想総所要時間を下界〔LB(Xr)〕算定式により求める。
3. 最少LB値をもつジョブが２つ以上あったときには、それぞれを第１番目とした順序計画を展開する。
4. 決定された１番目のジョブに次ぐ２番目のジョブを見出すために、１番目のジョブとの組み合わせによる機械ごとの完了時間を求める。
5. １番目と２番目のジョブによる下界を求め、その最小値を総所要時間最小が期待できるものとして第２番目のジョブを決定する。

これらの手順を順序付け対象ジョブ(ｎ個)について、ｎ－１番目まで繰り返し、全ジョブの順序付けを終了する。
ｎ－１番目時の下界値が最終的な製造リードタイムとなり、対象ジョブを生産するに最も短いリードタイムとなる。

編集途中