應用人工智慧演算法探討需多種工序的多工件開放式排程問題

Applications of Artificial Intelligence Algorithms to Explore Open-Shop Scheduling Problems for Tasks with Multiple Sequential Operations

蘇桂成(Kuei-cheng Su)

指導教授 ： 謝益智

國立虎尾科技大學/管理學院/工業工程與管理研究所/碩士(2014年)

https://doi.org/10.6827/NFU.2014.00060

摘要

本研究探討需多種工序的多工件開放式排程問題，此問題為多樣工件需要進行多種不同工序的排程問題，此類問題涵蓋與應用的範圍相當廣泛。本研究將探討三種需多種工序的多工件開放式排程問題，包括飛機維修問題、健康檢查問題、離校行政手續問題等類型進行。本研究探討的需多種工序的多工件開放式排程問題是傳統開放式排程問題(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.

並列關鍵字

Open Shop Scheduling Problem ； Genetic Algorithm ； Immune Algorithm ； Particle Swarm Optimization

參考文獻

1. 吳國賓(2004)，航機高階修護工作計畫最佳化模組之開發，國立成功大學航空太空工程學系碩博士班，碩士論文。

2. 李政儒(2010)，給定完工順序下允許中斷開放工廠排程問題之研究，朝陽科技大學工業工程與管理系碩士班，碩士論文。

3. 林信宏(2010)，粒子群演算法於多目標排程問題之研究，國立交通大學工業工程與管理學系，博士論文。

4. 李?銓(2011)，人工智慧演算法應用於藥劑噴灑最佳化問題之研究，國立虎尾科技大學工業工程與管理研究所，碩士論文。

5. 李新秋(2010)，具平衡之週期性車輛派遣問題的探討，國立虎尾科技大學工業工程與管理研究所，碩士論文。