タイトル：リエントラントフローショップ問題に対する局所探索法を用いたスケジューリング

所属：田村研究室 90140055 小山 裕

以下より本文

1. はじめに

近年, 半導体生産は少品種大量生産から多品種少量生産へと移行しており, また納期の短縮が求められるなど, 効率の良い生産システムを作ることが必要とされている. このためよりよいスケジュールを生成することが重要である.

本研究では, 半導体生産ラインをモデル化したリエントラントフローショップ問題に対し, 局所探索法を用いて, 滞留時間が短くなるようなスケジュールを作成することを目的とする.

2. リエントラントフローショップ

リエントラントフローショップ問題の特徴は, 各ロットはある機械で何らかの工程を行った後, 他の機械でいくつかの処理をし, 再び同じ機械へと戻ってくることである. このように, リエントラントフローショップは各ロットが同じ工程をたどるという点においてはフローショップ問題と似ているが, 各工程を処理する機械の割り当てについてはジョブショップ問題の要素を含む複雑な問題である.

3. 近傍探索

スケジューリングを行うことは, ロットの各工程に対し, 機械の割り当てを決めることと,各機械ごとの処理順序を決めることである. ここではある機械においてロットiの工程jを行った後ロットkの工程lを行う, といったことを各機械に対し決定しそれをロットの機械の割り当てに反映させる.

本研究では二つの機械の工程を入れ換えるswap, 一つの機械の工程を別の工程に割り込ませるmove, 二つの機械の連続した工程を入れ換えるswap-2という3つの近傍探索を使う. ここではそれらを単独で使用するのではなく, swap→move→swap-2という順で探索を行い解が改善されればswapに戻る方法1と, swap→move→swap-2→swapという順に探索を行うが, 解が改善されれば各近傍の最初に(moveで改善されればmoveに)戻る方法2を用いてスケジューリングを行った.

ここで制約をつけず近傍探索を行うと, 生成される解の9割近くが実行不能解となる. そこで各機械の工程に対し制約をかけるなどして実行不能解の発生を抑え, スケジューリングにかかる時間の短縮をはかった.

4. 結果

得られた結果を見るとFIFOで得られた滞留時間よりも本研究で得られた滞留時間のほうが大幅によいことが分かった. 方法1と方法2を比較すると, 方法1の方が滞留時間が短い. しかし方法2も方法1に近い結果を, 約半分の計算時間で求めていることが分かった.

5. おわりに

リエントラントフローショップ問題に対しswap, move, swap-2の3つの近傍探索を組み合わせた方法を用いたスケジュールを行いよい結果を得た. 今後はより現実に近い問題, 例えばあるベイである工程aが機械bで加工されたとき, 再びそのベイに戻って来て似たような工程a'を行うときは必ず機械bで加工されなければならないという制約（全ての工程ではないがその中のほんの一部の工程）を付け加えたスケジューリングを行いたい.