はじめに
平野廣美氏による1995年の論文クラスタ平均法を組み込んだ遺伝的アルゴリズムによるジョブショップスケジューリング問題の解法に記載の方法をPythonのDEAPモジュールを使用して実装した。
今回実装を5章に分けて紹介する。この記事は最初の章である。
- ジョブショップスケジューリング問題について（←この記事）
- ジョブショップスケジューリング問題の解表現
- ジョブショップスケジューリング問題向きの遺伝的操作
- DEAPライブラリ
- メイン処理、実行結果とまとめ
なおソースコード全体は以下に置いてある。
なお、論文補足のため同氏による2000年初版の書籍 遺伝的アルゴリズムと遺伝的プログラミング オブジェクト指向フレームワークによる構成と応用 での記述および付属ソースコードを参考にしている。ただしクラス構成などはオリジナルとは異なる。オリジナルは洗練されており参照してほしい。
ジョブショップスケジューリング問題について
ひとことで言えば最適なガントチャートを求める問題である。頭文字をとってJSPとかJSSPと呼ぶらしい。
詳細は上述の論文や書籍を確認してほしい。以下の論文（(1) スケジュール問題と計算の複雑さ）も参考になると思う。
簡単な例として、何種類かの製品を製造する工場での製造スケジュールを考えてみる（この例は上述の書籍に記載のものを参考にしている）。
目的の製品を「なるべく早く」製造するスケジュールを得たいとする（目的関数：最大完了時刻（メイクスパン）の最小化）。ほかにも目的関数としては、最大納期遅れの最小化などもある。
この工場では製品A, B, Cを機械a, b, c, dを使って製造しているとする。
例えば製品Bは、以下の順番で製造する。
- 機械b（2時間加工）
- 機械d（2時間加工）
- 機械c（1時間加工）
- 機械a（3時間加工）
これを他の製品についてもまとめると以下の表になる。
| - | 最初の工程 | 2番目の工程 | 3番目の工程 | 最後の工程 |
|---|---|---|---|---|
| 製品A | 機械a, 加工3時間 | 機械b, 加工2時間 | 機械c, 加工4時間 | 機械d, 加工1時間 |
| 製品B | 機械b, 加工2時間 | 機械d, 加工2時間 | 機械c, 加工1時間 | 機械a, 加工3時間 |
| 製品C | 機械a, 加工2時間 | 機械c, 加工2時間 | 機械b, 加工1時間 | 機械d, 加工2時間 |
ここで、製品A, B, Cの製造をジョブ1, 2, 3、機械a, b, c, dを機械1, 2, 3, 4と読みかえ上述の表の列を機械1, 2, 3, 4、セル値を( 機械番号、加工時間 ) とすると以下の表になる。
| - | 工程1 | 工程2 | 工程3 | 工程4 |
|---|---|---|---|---|
| ジョブ1 | ( 1, 3 ) | ( 2, 2 ) | ( 3, 4 ) | ( 4, 1 ) |
| ジョブ2 | ( 2, 2 ) | ( 4, 2 ) | ( 3, 1 ) | ( 1, 3 ) |
| ジョブ3 | ( 1, 2 ) | ( 3, 2 ) | ( 2, 1 ) | ( 4, 2 ) |
このようなシンプルな例であっても厳密解を得るための効率の良い計算方法は知られていない。スケジュールの取り方は (ジョブ数 x 工程数)! = 12! = 479,001,600 ≒ 4.8億通りとなり一般にはNP困難であると考えられてる。そのため厳密解ではなく、近似解や準最適解を求めることが多い。（なお1機械のみのスケジューリング問題ならば解くこともできる。）
ここでは、有名な問題としてMuth & Thompsonによるジョブ数10、機械数10 (MT10x10)を対象とする。なおこの厳密解は930であることが証明されている。
| - | 工程1 | 工程2 | 工程3 | 工程4 | 工程5 | 工程6 | 工程7 | 工程8 | 工程9 | 工程10 |
|---|---|---|---|---|---|---|---|---|---|---|
| ジョブ1 | (1, 29) | (2, 78) | (3, 9) | (4, 36) | (5, 49) | (6, 11) | (7, 62) | (8, 56) | (9, 44) | (10, 21) |
| ジョブ2 | (1, 43) | (3, 90) | (5, 75) | (10, 11) | (4, 69) | (2, 28) | (7, 46) | (6, 46) | (8, 72) | (9, 30) |
| ジョブ3 | (2, 91) | (1, 85) | (4, 39) | (3, 74) | (9, 90) | (6, 10) | (8, 12) | (7, 89) | (10, 45) | (5, 33) |
| ジョブ4 | (2, 81) | (3, 95) | (1, 71) | (5, 99) | (7, 9) | (9, 52) | (8, 85) | (4, 98) | (10, 22) | (6, 43) |
| ジョブ5 | (3, 14) | (1, 6) | (2, 22) | (6, 61) | (4, 26) | (5, 69) | (9, 21) | (8, 49) | (10, 72) | (7, 53) |
| ジョブ6 | (3, 84) | (2, 2) | (6, 52) | (4, 95) | (9, 48) | (10, 72) | (1, 47) | (7, 65) | (5, 6) | (8, 25) |
| ジョブ7 | (2, 46) | (1, 37) | (4, 61) | (3, 13) | (7, 32) | (6, 21) | (10, 32) | (9, 89) | (8, 30) | (5, 55) |
| ジョブ8 | (3, 31) | (1, 86) | (2, 46) | (6, 74) | (5, 32) | (7, 88) | (9, 19) | (10, 48) | (8, 36) | (4, 79) |
| ジョブ9 | (1, 76) | (2, 69) | (4, 76) | (6, 51) | (3, 85) | (10, 11) | (7, 40) | (8, 89) | (5, 26) | (9, 74) |
| ジョブ10 | (2, 85) | (1, 13) | (3, 61) | (7, 7) | (9, 64) | (10, 76) | (6, 47) | (4, 52) | (5, 90) | (8, 45) |
実装
今回、JobMachineTableモジュールを作成し問題に対するジョブと工程とを管理する。JobMachineTableBaseを基底クラスとし、問題別にMT10_10のように派生クラスを作成する。
class JobMachineTableBase :
""" Job x Machine データを格納する基底クラス """
def __init__ ( self ) :
self._mTable, self._ptTable = self._initTables()
def _initTables ( self ) :
"""問題ごとに派生クラスでオーバーライドする"""
return None, None
JobMachineTableBaseでは、インスタンス作成時にジョブ番号別に加工に使用する機械番号を工程順に格納したself._mTableおよび、ジョブ番号別に機械の加工時間を工程順に格納したself._ptTableを用意する。
派生クラスでは、self._initTables()をそれぞれの問題向けにオーバーライドし実際の機械番号テーブルや加工時間テーブルを戻すように実装する。
また、ジョブ数と工程数（機械数）とを取得するゲッターを用意する。
def getJobsCount ( self ) :
""" ジョブ数を取得 """
return len ( self._mTable )
def getMachinesCount ( self ) :
""" ジョブの工程数（機械数）を取得 """
return len ( self._mTable [ 0 ] )
さらにジョブ番号と工程番号とを指定したときの機械番号あるいは加工時間を取得するメソッドを用意する。
def getMachine ( self, job_num, process_index ) :
""" job_numジョブのprocess_index工程のMachine番号を取得 """
return self._mTable [ job_num ][ process_index ]
def getProcessTime( self, job_num, process_index ) :
""" job_numジョブのprocess_index工程の処理時間を取得 """
return self._ptTable [ job_num ][ process_index ]
この基底クラスをまとめて以下に記載する。
class JobMachineTableBase :
""" Job x Machine データを格納する基底クラス """
def __init__ ( self ) :
self._mTable, self._ptTable = self._initTables()
def _initTables ( self ) :
"""問題ごとに派生クラスでオーバーライドする"""
return None, None
def getJobsCount ( self ) :
""" ジョブ数を取得 """
return len ( self._mTable )
def getMachinesCount ( self ) :
""" ジョブの工程数（機械数）を取得 """
return len ( self._mTable [ 0 ] )
def getMachine ( self, job_num, process_index ) :
""" job_numジョブのprocess_index工程のMachine番号を取得 """
return self._mTable [ job_num ][ process_index ]
def getProcessTime( self, job_num, process_index ) :
""" job_numジョブのprocess_index工程の処理時間を取得 """
return self._ptTable [ job_num ][ process_index ]
例えばMT10_10クラスはJobMachineTableBaseを継承して以下のように記載する。
なお機械番号は書籍などと整合を取るため定義では1から開始しているが、便利のためゼロ開始に変換している。
class MT10_10 ( JobMachineTableBase ) :
""" MT10x10問題 """
def _initTables ( self ) :
"""MT10x10のテーブルを取得"""
jmTable = [
[ [1,29], [2,78], [3,9], [4,36], [5,49], [6,11], [7,62], [8,56], [9,44], [10,21] ]
, [ [1,43], [3,90], [5,75], [10,11], [4,69], [2,28], [7,46], [6,46], [8,72], [9,30] ]
, [ [2,91], [1,85], [4,39], [3,74], [9,90], [6,10], [8,12], [7,89], [10,45], [5,33] ]
, [ [2,81], [3,95], [1,71], [5,99], [7,9], [9,52], [8,85], [4,98], [10,22], [6,43] ]
, [ [3,14], [1,6], [2,22], [6,61], [4,26], [5,69], [9,21], [8,49], [10,72], [7,53] ]
, [ [3,84], [2,2], [6,52], [4,95], [9,48], [10,72], [1,47], [7,65], [5,6], [8,25] ]
, [ [2,46], [1,37], [4,61], [3,13], [7,32], [6,21], [10,32], [9,89], [8,30], [5,55] ]
, [ [3,31], [1,86], [2,46], [6,74], [5,32], [7,88], [9,19], [10,48], [8,36], [4,79] ]
, [ [1,76], [2,69], [4,76], [6,51], [3,85], [10,11], [7,40], [8,89], [5,26], [9,74] ]
, [ [2,85], [1,13], [3,61], [7,7], [9,64], [10,76], [6,47], [4,52], [5,90], [8,45] ]
]
# 機械番号をゼロ開始に変更しつつ機械番号用のテーブルと加工時間用のテーブルに分けて格納
mTable, ptTable = [], []
for row in jmTable :
machines, pt_list = [], []
for m, p in row :
machines.append ( m-1 )
pt_list.append ( p )
mTable.append ( machines )
ptTable.append ( pt_list )
return mTable, ptTable
なお今回紹介したJobMachineTableモジュールは以下に全体がある。なおこのモジュールには次章で紹介する機能も含まれている。
(つづく）
次の章「ジョブショップスケジューリング問題の解表現」はこちら