6.2 結論
本論文では,遺伝アルゴリズムを用いたジョブショップスケジューリング問題への近似解法 を提案した. 4つの表現法のうち,良い解を求めることができた作業順序法を用い,パラメー タを調整し実験を行った. 仕事数10,機械数5のような問題の規模が小さなものでは最適解 を求めることができた. 仕事数15,機械数15のような問題では最適なmakespanは得られ なかったが, 妥協範囲にはとどき,ほとんどの問題でupper boundに近い解を求めることが できた.
upper boundに近い解を求められた問題ではさらにパラメータ調整を行えば最適解にと
どく可能性がある. upper boundに近い解を求められた問題の共通点として仕事数に対して 機械数が少ないということを見つけた. 表にはないが仕事数15,機械数5や20, 5や30, 10 のような仕事数に対して機械数の割合が小さい問題では, 染色体の初期集団ですでに最適解 に近い解をもった染色体が生成されていた. 問題規模30, 20や50, 20などの仕事数に対し 機械数もそれなりにある問題は実行した結果は妥協範囲にとどくのがやっとである. 表6.2
の100, 20の問題でも規模が大きいが仕事数に対し機械数が少ないのでPMX(右固定)では
最適解に近いものを求めることができている.
仕事数に対し機械数もそれなりにある問題が妥協範囲にどどくのがやっとだった原因のひ とつは, 機械が作業をしない無駄な時間が作られやすいことであると考えられる. 図6.2に 示すように, M2 に1番目に挿入した作業が,短い時間で処理されるものだったとき(この仕 事をJ1 とする), J1 の2番目の作業をM2 に挿入したとすると図6.2の左のようになる. 2 番目の作業を挿入した機械(M1 とする)で別の仕事の1番目の作業(J2の作業とする)を挿 入するとき, J1 の2番目の作業の前には空白があり挿入できそうなスペースがあるのだが J1 の1番目の処理が短いので, 今挿入しようとしているJ2 の作業を挿入することができな い. よってM1 はJ1 の2番目の作業の次にJ2 の1番目の作業を処理しなくてはならなく なり, 図6.2の右のようにM1 の最初に無駄な時間ができてしまう. このようなことが機械 数が多い程発生しやすいのではないかと考えた.
6.2 結論
図6.2 最適解にとどかない原因
だが無駄な時間と記述したが,このような処理順序になったとき, J1 は次の3番目の作業 を早く処理を開始することができるので本当に無駄であるかどうかは, まだ処理されていな い作業で決まる. なので突然変異などの処理で染色体の順序をランダムに入れ換えるだけで なく, 染色体の順序が図6.2の場合だと 染色体= (1, 1, 2,…)となっているので, 「1, 1と 同じ数字が続いているときに2番目の1とランダムに選んだ1以外の値と入れ換える」のよ うな処理を一定の確率で発生するように追加などすれば最適解を求められる可能性が高くな ると思われる.
謝辞
本論文は著者が高知工科大学情報システム工学科在学中に, 同学科坂本研究室において 行った研究の成果を記したものである.
本論文を著すにあたり遺伝アルゴリズム,プログラミングなど御指導頂いた坂本明雄教授 に深く感謝致します.
御指導頂いた先輩方,プログラム稼働中の暇潰しにつき合ってくれた決闘者の皆様のおか げで大学へ行くことへのモチベーションを保つことができ,本論文を著することができまし た感謝致します. 著者が大学生活を有意義に過ごすことができたのは,本大学入学から卒業 の間で出会うことができた皆様のおかげです.
最後に,講義だけでなく就職活動まで御指導,御支援頂いた情報システム工学科の諸先生方 に深く感謝致します.