解開放式工廠排程問題之兩層式基因區域搜尋法

Abstract

開放式工廠排程問題(open shop scheduling problem)為作業研究中典型的組合最佳化問題，此問題是NP-hard，本研究將在排程作業不可中斷(non-preemptive)的情況下，求總時程(makespan)最小化的解。 本研究整合基因演算法(Genetic Algorithms, GA)與區域搜尋法(Local Search)為基因區域搜尋法(Genetic Local Search Algorithm)，並導入兩層式基因區域搜尋法(Two Layered Genetic Local Search Algorithm)，先作全域性的搜尋，再作區域性搜尋，來解開放式工廠排程問題，並以Taillard與Brucker共一百一十二題的標準實例為本研究的測試標準，透過實驗証明兩層式基因區域搜尋法在解決開放式工廠排程問題上有很顯著的成效，以Taillard的標準實例而言，除了有一題解到目前已知最好的解之外，其餘全都達到目標最佳解，在Brucker的標準實例中，平均求解品質也不錯，其中更有一題突破上限值(Upper Bound)，亦即比目前最好的解還好。 關鍵字：開放式工廠排程問題，基因演算法，區域搜尋法，兩層式基因區域搜尋法。

The open shop scheduling problem is an NP-hard combinational problem and has long attracted much attention. In this thesis, we propose a two layered genetic local search algorithm for this problem. The first layer acts as the global search and the second layer acts as the local search. We also study the neighborhood structure of a solution and design two kinds of effective local search methods. Combining the genetic algorithm with these local search methods results in our genetic local search algorithm. We test our method on Taillard's instances and Brucker's instances. On Taillard's instances, our method had found the optimal solutions for all instances except one of them. And for this exception, the solution found by our method is the same as the best solution found thus far. On Brucker's instances, the quality of solutions found is also good and our method had improved the upper bound of one instance. Key words: Open Shop Scheduling Problem; Genetic Algorithm; Local Search; Two Layered Genetic Local Search Algorithm