標題: | 基因-禁忌演算法搭配新染色體表達法求解彈性零工式排程問題 A GA-Tabu Algorithm Based on a New Chromosome Representation for Scheduling Flexible Job Shops |
作者: | 徐千雯 Hsu, Chien-Wen 巫木誠 Wu, Muh-Cherng 工業工程與管理學系 |
關鍵字: | 彈性零工式生產;解表達法;禁忌搜尋法;基因演算法;啟發式演算法;Flexible Job Shop Scheduling;Solution Representation;Tabu Search;genetic algorithm;Meta-Heuristic |
公開日期: | 2011 |
摘要: | 本論文為探討彈性零工式排程問題(flexible job-shop scheduling problem, FJSP),此問題包括兩項子決策,分別為(1)作業指派(operation-to-machine assignment),(2)作業排序(Operation Sequencing for Each Machine)。FJSP複雜度為NP-hard,過去研究發展各種不同巨集啟發式演算法(Meta-heuristic Algorithms)來求解。本論文採用基因-禁忌演算法的架構搭配一個新染色體表達法(簡稱Sop),發展出一演算法(稱為GA-Tabu_Sop)來求解FJSP問題,並以最大完工時間(Makespan)為目標函數。所謂染色體表達法是指解的表達法,Sop表達法表示作業排序;亦即一個染色體就是一個特定的作業排序(A Particular Sequence of Operations)。給定某一染色體(作業排序),本研究發展數種啟發式演算法(Heuristic Methods),可藉此導出此染色體相對應的作業指派子決策。 This research is concerned with the scheduling of a flexible job-shop problem (called FJSP), which involves two sub-decisions: (1) assignment of each operation to an appropriate machine, and (2) sequencing all operations assigned to each machine. Most prior studies proposed meta-heuristic algorithms for the FJSP problem. This research proposes a new solution representation (called Sop), which is intended to model a particular sequence for all operations. Given a particular Sop, by proposed heuristic rule, we can obtain its two corresponding sub-decisions; which in turn represents a particular scheduling solution. Based on the Sop representation, this research adopts the architecture of genetic algorithms and Tabu search, and develops a meta-heuristic algorithm (called GA-Tabu_ Sop). Experiment results indicate that GA-Tabu _ Sop performance decline slightly from prior meta-heuristic algorithms in FJSP. |
URI: | http://140.113.39.130/cdrfb3/record/nctu/#GT079933546 http://hdl.handle.net/11536/50111 |
顯示於類別: | 畢業論文 |