楊烽正2006-07-252018-06-292006-07-252018-06-292003http://ntur.lib.ntu.edu.tw//handle/246246/4200「分群優化問題」是實務應用及作業研究中時常見到的 NP-hard 問題。本研究 以「將一堆物件分群」的角度來建構數學模式並開發蟻拓啟發式求解法。蟻拓尋 優技術雖已廣泛運用於求解物件排列組合問題，但缺乏於物件分群相關的運用。 據此，本研究主要在開發蟻拓尋優技術為基的物件分群優化演算法。開發方法係 以物件導向技術建模並萃取設計樣型（design pattern），以確保此啟發式演算法 能應用於各式物件分群優化問題。 系統實作上，本研究開發蟻拓物件分群尋優軟體礎架（software framework），並 實作包含教務單位入學考試科目時間安排問題分群處理的數種求解系統，以驗證 本研究所開發系統的求解能力及擴充性。結果顯示本軟體礎架確實可有效提供實 務工作者在面臨物件分群優化問題時，繼承此礎架內的類別並自行開發以ACO 演算法為求解核心的決策支援工具。Object grouping optimization problems, known as NP-hard problems, are frequently encountered in operation research areas and industrial fields. Traditionally, these problems are modeled as set partitioning problems. In this research, viewpoint of group allocation for a set of objects is adopted to construct mathematical models for object grouping optimization problems. This research then focuses on developing an object grouping technique based ACO (Ant Colony Optimization) method to solve this kind of problems. Design patterns of using ACO approaches to solve object grouping optimization problems are discussed. General procedures are postulated for further applications of solving this kind of problems. To implement the proposed method, this research develops an ACO based software framework, including core software classes, to solve object grouping optimization problems. These classes are dedicated to using ACO techniques to solve object grouping problems. Based on this framework, applications of solving exam timetabling problems and other grouping problems (including graph coloring problems, node number balanced graph coloring problems, and bin packing problems) are also implemented to verify the functionalities and expandability of the framework. The framework this research proposed is a complete decision making tool for discrete optimization problems.application/pdf586781 bytesapplication/pdfzh-TW國立臺灣大學工業工程學研究所蟻拓尋優法物件分群優化設計樣型ant colony optimizationobject grouping optimizationdesign patternreporthttp://ntur.lib.ntu.edu.tw/bitstream/246246/4200/1/912213E002115.pdf