Comparison of Two Genetic Algorithms in Solving Tough Job Shop Scheduling Problems

• Shi Guoyong

  Kyoto Institute of Technology

• Iima Hitoshi

  Kyoto Institute of Technology

• Sannomiya Nobuo

  Kyoto Institute of Technology

Bibliographic Information

Other Title

• Comparison of Two Genetic Algorithms in

Abstract

In order to solve job shop scheduling problems (JSSPs) by a genetic algorithm (GA), one should first design an encoding scheme, on which a search space is constructed. This paper proposes two encoding formats; one is a string code format that leads to the redundancy of the code space, and the other is a matrix code format that overcomes the redundancy but only insures an approximate representation. Two corresponding genetic algorithms (GAs) are designed for investigating the encoding effectiveness. Complex problems like the JSSPs usually require complicated code structures, which in turn call for delicate design of genetic operations such as crossover. The code structures of the two encoding formats are analyzed and compared. Test-runs of the two GAs on several tough JSSP benchmarks are performed for a demonstration of the validation of the proposed methods.

Journal

• IEEJ Transactions on Electronics, Information and Systems

  IEEJ Transactions on Electronics, Information and Systems 117 (7), 856-864, 1997

  The Institute of Electrical Engineers of Japan

Keywords

• job shop scheduling problems
• genetic algorithms
• encoding
• active schedule
• suboptimum solution

Details

• CRID: 1390001204608075520
• NII Article ID: 130006843834
• NII Article ID: 10002810694
• NII Book ID: AN10065950
• DOI: 10.1541/ieejeiss1987.117.7_856
• ISSN: 13488155
• ISSN: 03854221
• NDL BIB ID: 4248147
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I4248147
• Web Site: https://www.jstage.jst.go.jp/article/ieejeiss1987/117/7/117_7_856/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • NDL
  • Crossref
  • CiNii Articles
• Abstract License Flag: Disallowed