階乗進数を使った順列表現とフローショップスケジューリング問題への応用

概要

論文の詳細を見る
本研究の第1の目的は,フローショップスケジューリング問題において古典的なヒューリスティックスであるNEHの探索方法を,遺伝的アルゴリズムの中に取り入れ,探索能力の改善を図ることである.この目的のために,順列を階乗進数を使って表現した.階乗進数による染色体表現は,順列と1対1に対応するので,冗長性もない.また,交叉によって致死遺伝子を生じることがないので,1点交叉や2点交叉のみならず,一様交叉も適用できる.更に,順列と階乗進数を対応させるときに使われる基準順列として,総作業時間の小さい順にη個の仕事を並べることによって,NEHの考え方を,遺伝的アルゴリズムの探索過程に無理なく導入できることがわかった.また,階乗進数を使うことにより,ある種の制約条件を容易に表現できる.本研究の第2の目的は,順序制約付き順列の探索において,階乗進数表現の有効性を確認することであった.このため,数値実験を行ったが,従来の方法より優れた結果を得ることができた.
社団法人電子情報通信学会の論文
2002-05-01