The Hybrid Approach of LCO and SA to Solve Job-shop Scheduling Problem

摘要

A Job-shop Scheduling Problem (JSP) is one of the combinatorial optimization problems. JSP appears as a basic scheduling problem in many situations of a manufacturing system and many methods for JSP have been invented. This study examines two effective methods, SA and LCO, for JSP and propose a hybrid method based on them. As a result of the experiments, the proposed method can find a good solution with short computational time. Summarizing this study, the proposed method is efficient in the early or middle search of the optimization.%ジヨブショップスケジユーリング問題（Job-shop Scheduling Problem; JSP)は，生産システムにおける基礎的なスケジユーリング問題を表現するものであり，これまで多くの研究がなされ，様々な解法が提案されている.JSPはNP困難な問題に分類されるため，解を求めるためには多くの計算時間を必要とする.したがつて，JSPの解法に関する研究は，ヒユーリステイクスを始めとした近似アルゴリズムに基づくものが多い.これらの近似アルゴリズムに関して，本研究では擬似焼き鈍し法（Simulated Annealing; SA)，局所クラスタリング組織化法（Local Clustering Organization; LCO)とよばれる二つの既存手法について検討する.SAは，評価値が悪化する解を確率的に受容することによって局所解への収束の回避を試みる方法であり，多くの問題で良好な解を求めることが可能である.一方で，SAの性能は適用時に設定されるパラメータの値に依存し，これらのパラメータを個々の問題に応じて適切に設定する有効な手法がない問題点が挙げられる.LCOは，巡回セールスマン問題（Traveling Salesman Problem; TSP)に対し，高速に近似解を得る方法として提案された解法であり，JSPに対しても有効な手法であることが示されている.しかし，LCOは山登り法の一種であるため，多峰性の問題では局所最適解に陥る欠点が存在する.本研究では，これら二つの方法を基礎とし，局所解への収束を回避および高速な解の探索を実現するハイブリッドアルゴリズムを提案する.また，数値計算実験を通して，提案手法の有効性を検証する.本研究の成果として，提案手法はLCOと比較して平均的に良好な評価値の解を得られること，SAと比較して解の収束が早いことが明らかとなつた.