本研究探討需多種工序的多工件開放式排程問題,此問題為多樣工件需要進行多種不同工序的排程問題,此類問題涵蓋與應用的範圍相當廣泛。本研究將探討三種需多種工序的多工件開放式排程問題,包括飛機維修問題、健康檢查問題、離校行政手續問題等類型進行。本研究探討的需多種工序的多工件開放式排程問題是傳統開放式排程問題(Open Shop Scheduling Problem)的延伸問題,因為傳統開放式排程問題屬於NP-hard問題,本研究探討的需多種工序的多工件開放式排程問題亦為NP-hard問題,因此若使用傳統的方法來求解此問題,需要耗費大量的時間,且無法確保求解的品質優劣。一般而言,人工智慧演算法是目前求解複雜問題的可行方法之一,雖不能保證求出問題的最佳解,但能有效的求出近似最佳解且求解速度快速,因此本研究嘗試以人工智慧演算法來做為需多種工序的多工件開放式排程問題的求解工具。 本研究應用三種人工智慧演算法,包含基因演算法(Genetic Algorithms, GA)、免疫演算法(Immune Algorithms, IA)與粒子群最佳化演算法(Particle Swarm Optimization, PSO),分別探討三種不同類型的需多種工序的多工件開放式排程問題,此三個問題的目標均為最小化完工時間。本研究分別對此三種演算法的演算結果進行分析與比較,實驗數值結果顯示,免疫演算法的求解品質優於其他兩種演算法,然而基因演算法的求解速度優於其他兩種演算法。
In this thesis, we investigate the open-shop scheduling problem for tasks with multiple sequential operations in which a variety of tasks need to be processed and scheduled. There are many applications for the considered problem. In this thesis, we will explore three types of open-shop scheduling problems for tasks with multiple sequential operations, including aircraft maintenance scheduling problem, physical examination scheduling problem and administrative procedure scheduling problem. The considered open-shop scheduling problem for tasks with multiple sequential operations is an extension of the typical open-shop scheduling problems. Since typical open-shop scheduling problem is an NP-hard problem, the considered scheduling problem is also an NP-hard problem. As known, typical approaches require much of time for solving the considered problem, and they cannot guarantee the quality of solutions. Generally, artificial intelligence algorithms can be used to solve for the solutions of considered problem. Though they cannot guarantee the global optimal solutions, they can provide effective solutions within a reasonable CPU time. In this thesis, we attempt to adopt artificial intelligence algorithms to solve the considered problem. In this thesis, three artificial intelligence algorithms, including genetic algorithm, immune algorithm and particle swarm optimization algorithm, are applied for solving the considered problem. The objective of the considered problem is to minimize the completion time. In this study, numerical results by these three algorithms are reported, compared and analyzed. Experimental results show that immune algorithm is superior to the other two algorithms in solution quality. However, genetic algorithm is more efficienct than the other two algorithms.