遺伝的アルゴリズムを用いた最適スケジューリング

概要:

スケジューリング問題は組合最適化問題の中でも特に難問とされており、列挙 法に基づく従来の厳密解法には限界がある。そこで自然淘汰と遺伝の仕組みを 計算モデルにした遺伝的アルゴリズム(GA)を用いた近似的な最適化法に基づく究極 のスケジューリング技術の確立を目指す。

GAによる最適スケジューリング

我々は、GAによるJSSP解法の初期研究として、ビット列表現を用いた方法、ア クティブスケジュールを用いた、より直接的な解表現による方法などを提案し てきた[1]。その後、交叉オペレータに局所探索を取り入れた 多段階探索交叉(MSXF)を考案し、ジョブショップ問題、フローショップ問題な どに適用し、良好な結果を得た[2,3,4]。通常の交 叉とは異なりMSXF では一方の親を出発点とする局所探索を実行する。その際 他方の親を参照点として用い、探索の方向がその親に近づく方向を優先させる 誘導型探索を行う。その結果、従来のGAを用いた場合や、複数の個体が独立に探 索する場合に比べて効率的な探索が可能となる(図1)。MSXF は解空間の近傍 構造と距離の性質に基づいており、さまざまな組合せ最適化問題に適用でき 非常に汎用的である。また、スケジューリング問題の解空間には「大谷構造」 と呼ばれる大局的な構造が存在し、これがMSXF法の高性能の主要因になってい ることを明らかにした[4]。

  

図 1: 従来の交叉と多段階探索交叉

CASTへの適用

情報案内オペレータ配置支援システム(CAST)を開発中のNTTコミュニケーショ ンウェアKK (信越支社)からの依頼により、本技術をオペレータ配置問題に適 用、短時間に良質の解を求めることに成功した(図2)[5]。CASTシス テムは1998年春から全国規模(100事業所)で導入の予定。

  

図 2: オペレータ配置問題の準最適解

今後の予定

今後はさまざまなタイプのスケジューリング問題へと適用範囲を広げ, また、より問題に適した解法探求のため 解空間の構造の解析をさらにすすめる予定である。

連絡先：山田 武士, Email: yamada@cslab.kecl.ntt.co.jp

参考文献

1

Yamada, T. and Nakano, R.: Chapter 7: Job Shop Scheduling, in A.M.S. Zalzala and P.J.Fleming (Ed.) Genetic Algorithms in Engineering Systems,
The Institution of Electrical Engineers, London, UK, pp. 134-160 (1997).

1

山田武士, 中野良平: 遺伝的局所探索法によるジョブショップスケジューリング問題の解法, 情報処理学会論文誌, Vol. 38, No. 6, pp. 1126-1138 (1997).

3

Yamada, T. and Reeves, C.R.: Permutation flowshop scheduling by genetic local search, Proc. of the 2nd IEE/IEEE International Conference on Genetic ALgorithms in Engineering Systems (GALESIA '97), pp. 232-238 (1997).

4

Yamada, T. and Reeves, C.R.: Solving the Csum Permutation Flowshop Scheduling Problem by Genetic Local Search, Proc. of 1998 IEEE International Conference on Evolutionary Computation (ICEC'98), pp. 230-234, 1998.

5

Yoshimura, K. and Nakano, R.: Genetic Algorithm for Information Operator Scheduling, ibid., pp. 277-282, 1998.