請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/61200
標題: | 蟻拓優化演算法應用於多型態零工式生產排程問題 Ant Colony Optimization Algorithm for Polymorphic Job Shop Scheduling Problems |
作者: | Guan-Cing Jiang 江冠慶 |
指導教授: | 楊烽正(Feng-Cheng Yang) |
關鍵字: | 蟻拓優化演算法,零工式生產排程,多型態零工式生產排程,軟體測試, Ant Colony Optimization Algorithm,Job Shop Scheduling Problem,Polymorphic Job Shop Scheduling Problem,Software Testing, |
出版年 : | 2013 |
學位: | 碩士 |
摘要: | 本研究承襲零工式生產排程問題並定義一全新「多型態零工式生產排程問題」(Polymorphic Job Shop Scheduling Problem),並運用「蟻拓優化演算法」(Ant Colony Optimization Algorithm),提出「蟻拓優化演算法應用於多型態零工式生產排程問題」(Ant Colony Optimization Algorithm for Polymorphic Job Shop Scheduling Problem, ACO4PJSP)。隨著時代的進步,典型的零工式生產排程問題已經不符合實際排程上的需求,雖然近年來不斷的有學者提出零工式生產排程的相關變型問題,但無法涵蓋到所有可能的排程情況,本研究定義PJSP問題,考慮許多實際排程上可能面臨的情況,並代入軟體測試公司的實際排程案例,以驗證PJSP的可行性與合理性。由於典型的JSP與PJSP皆為一NP-Hard問題,所以本研究利用「蟻拓優化演算法」,可在短時間內得到不錯的解以提供排程的決策。研究結果顯示,ACO4PJSP不但可針對不同的狀況選擇不同的求解目標,亦可求解軟體測試公司的實際排程案例。證明ACO4PJSP是適合求解複雜情況下的排程問題。 This research defines a scheduling problem called “Polymorphic Job Shop Scheduling Problem” (PJSP). PJSP is a new problem originated from “Job Shop Scheduling Problem” (JSP). Different from JSP, many real world scheduling conditions are considered in PJSP. Though our literature survey shows none of the transformed JSP problems developed in recent studies are similar to PJSP, both JSP and PJSP are NP hard problems. In this research, a method based on “Ant Colony Optimization Algorithm” (ACO) to solve PJSP is developed and named as “Ant Colony Optimization Algorithm for Polymorphic Job Shop Scheduling Problem” (ACO4PJSP). In this study, two scheduling examples from software testing companies are tested by ACO4PJSP, proving that our developed ACO4PJSP is capable for solving two different scheduling examples based on different objectives and many scheduling conditions. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/61200 |
全文授權: | 有償授權 |
顯示於系所單位: | 工業工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-102-1.pdf 目前未授權公開取用 | 4.18 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。