遺伝的局所探索法によるジョブショップスケジューリング問題の解法

情報処理学会 Web Site 被引用文献11件 参考文献32件

書誌事項

タイトル別名
  • イデンテキ キョクショ タンサクホウ ニヨル ジョブショップ スケジューリング
  • Job - Shop Scheduling by Genetic Local Search
  • 人工知識と認知科学

この論文をさがす

説明

ジョブショップスケジューリング問題（JSSP）はNP?困難な組合せ最適化問題の中でも特に難しい問題の1つとされている．本論文では，JSSPの近似解法として，局所近傍探索と遺伝的アルゴリズム（GA）との組合せによる多段階探索交叉GA (MSXF?GA）を提案する．MSXF?GAは，アクティブスケジュールのクリティカルブロック（CB）上の作業の移動に基づく近傍であるアクティブCB近傍に基づく近傍探索と，問題空間の距離と近傍構造に基づく交叉である多段階探索交叉（MSXF）を用いたGAから構成される．さらに，アクティブスケジュールに対し「スケジュールの反転」という概念を導入し，与えられた問題に適した方向を適応的に選択する機構を取り入れて，解法の高速化を図る．MSXF?GAを含むいくつかの解法をジョブショップスケジューリング問題（JSSP）のベンチマーク問題に適用したところ，高品質の解が高速かつ安定して求まるという，MSXF?GAの優れた性能が明らかになった．

The job-shop scheduling problem(JSSP) is one of the most difficult NP-hard combinatorial optimization problems.In this paper,an approximation method for JSSP called MSXF-GA is proposed using local neighborhood search and evolutionary computation,especially Genetic Algorithms(GA).MSXF-GA is composed by a neighborhood search that uses active CB neighborhood based on an active scheduler and operation permutations on the critical path,and Multi-Step Grossover Fusion(MSXF) that utilizes a neighborhood structure and a distance measure in the search space.The "reversal of the direction" of an active schedule is also introduced and MSXF-GA can adaptively select an appropriate direction for a given problem.Experimental results showed such a promising performance of MSXF-GA that it quickly found near optimal schedules in most cases.

収録刊行物

被引用文献 (11)*注記

もっと見る

参考文献 (32)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ