蟻拓優化演算法應用於多型態零工式生產排程問題

Abstract

本研究承襲零工式生產排程問題並定義一全新「多型態零工式生產排程問題」(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.