遺伝的アルゴリズムによるスケジューリング問題の解法 Genetic Algorithms for a Job-Shop Scheduling Problem

この論文にアクセスする

この論文をさがす

著者

抄録

遺伝的アルゴリズムを用いてジョブショップスケジューリング問題を解く際に, 個体集団内の遺伝子の状況判断や工程の特性判断のアルゴリズムを加えることで, 限られた情報から効率よく好適解を得ることのできる遺伝的アルゴリズムを開発することを目的とし, (1) 中域的な探索能力の向上を目的に, 適応度の高い個体から優良な遺伝子を抽出する優良遺伝子抽出法と, (2) 局所的な探索能力向上を目的とした, 優秀な個体の近傍の解空間を探索するエリート近傍探索法と, (3) 状況に応じて, 良いスケジュールを生成しそうな可能性のみを検討するオーバール-ルの3方法を提案した.<BR>これらの方法をMuthとThompsonのジョブショップスケジューリング問題に適用してその効果の検討を行い, 今回提案した3方法の特徴を活かして組み合わせた遺伝的アルゴリズムを用いることで, 比較的大きなジョブショップスケジューリング問題に対しても実用的な好適解が得られることを明らかにした.

We propose the following genetic algorithms (GA) to effectively solve job-shop scheduling problems by introducing the following judgments of the present status of the genes in the population and characteristics of the task sequence : (1) Extracting excellent genes, i.e., the effective part in the string from individuals with good fitness ; (2) Exploiting local search around an elite by checking all probable mutation within one Hamming distance ; (3) Introducing an overrule to examine only the cases which seem to give good results.<BR>These algorithms are tested by applying them to the Muth-Thompson Job-Shop Scheduling Problems (1963), and we prove that the application of GA with combined use of these algorithms can generate practically good schedules even for job-shop scheduling problems of relatively large scale.

収録刊行物

  • 化学工学論文集  

    化学工学論文集 23(2), 175-180, 1997-03-10 

    The Society of Chemical Engineers, Japan

参考文献:  6件

参考文献を見るにはログインが必要です。ユーザIDをお持ちでない方は新規登録してください。

各種コード

  • NII論文ID(NAID)
    10002767181
  • NII書誌ID(NCID)
    AN00037234
  • 本文言語コード
    JPN
  • 資料種別
    ART
  • ISSN
    0386216X
  • NDL 記事登録ID
    4161075
  • NDL 雑誌分類
    ZP5(科学技術--化学・化学工業--化学工学)
  • NDL 請求記号
    Z17-725
  • データ提供元
    CJP書誌  NDL  J-STAGE 
ページトップへ