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

• Item type: Journal(1)
• 公開日: 1997-06-15
• タイトル: 遺伝的局所探索法によるジョブショップスケジューリング問題の解法
• タイトル / 言語: en
• タイトル: Job - Shop Scheduling by Genetic Local Search
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 人工知識と認知科学
• 著者所属: NTTコミュニケーション科学研究所
• 著者所属: NTTコミュニケーション科学研究所
• 著者所属(英): en
• 著者所属(英): NTT Communication Science Laboratories
• 著者所属(英): en
• 著者所属(英): NTT Communication Science Laboratories
• 著者名: 山田, 武士; 中野, 良平
• 著者名(英): Takeshi, Yamada; Ryohei, Nakano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ジョブショップスケジューリング問題（JSSP）はNP?困難な組合せ最適化問題の中でも特に難しい問題の1つとされている．本論文では，JSSPの近似解法として，局所近傍探索と遺伝的アルゴリズム（GA）との組合せによる多段階探索交叉GA (MSXF?GA）を提案する．MSXF?GAは，アクティブスケジュールのクリティカルブロック（CB）上の作業の移動に基づく近傍であるアクティブCB近傍に基づく近傍探索と，問題空間の距離と近傍構造に基づく交叉である多段階探索交叉（MSXF）を用いたGAから構成される．さらに，アクティブスケジュールに対し「スケジュールの反転」という概念を導入し，与えられた問題に適した方向を適応的に選択する機構を取り入れて，解法の高速化を図る．MSXF?GAを含むいくつかの解法をジョブショップスケジューリング問題（JSSP）のベンチマーク問題に適用したところ，高品質の解が高速かつ安定して求まるという，MSXF?GAの優れた性能が明らかになった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 38, 号 6, p. 1126-1138, 発行日 1997-06-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764