遺伝的アルゴリズムによるスケジューリング問題の解法

• 中神 匡人

  東京工業大学資源化学研究所

• 石田 愈

  東京工業大学資源化学研究所

書誌事項

タイトル別名

• Genetic Algorithms for a Job-Shop Scheduling Problem.
• イデンテキ アルゴリズム ニヨル スケジューリング モンダイ ノ カイホウ

抄録

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

  公益社団法人 化学工学会

キーワード

• Genetic Algorithms
• Job-shop Scheduling Problem
• Extracting Excellent Gene
• Elite Neighborhood Search
• Overrule

詳細情報

• CRID: 1390001204509633920
• NII論文ID: 10002767181
• NII書誌ID: AN00037234
• DOI: 10.1252/kakoronbunshu.23.175
• ISSN: 13499203
• ISSN: 0386216X
• NDL書誌ID: 4161075
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I4161075
• Web Site: http://www.jstage.jst.go.jp/article/kakoronbunshu1975/23/2/23_2_175/_pdf
• 本文言語コード: ja
• データソース種別:
  • JaLC
  • NDL
  • Crossref
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可