應用人工智慧演算法探討健康檢查之排程問題

Using Artificial Intelligence Algorithms for the Health Examination Scheduling Problems

程秉逢(Bing-Feng Cheng)

指導教授 ： 謝益智

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

摘要

近年來隨著預防勝於治療的觀念普與生活水平的改善，國人已普遍接受健康檢查，以進一步掌握自己的健康狀況，預防重大疾病的發生。為了讓健康檢查中心能夠更精準的掌握健康檢查受檢人的檢驗狀況並且讓受檢人得到舒適貼切的服務，使得受檢人完成總檢查的時間縮到最短，即為本研究探討的健康檢查排程問題。此問題屬於傳統開放式排程問題的延伸問題，因為傳統開放式排程問題屬於NP-hard問題，因此本研究所探討的健康檢查排程問題亦為NP-hard問題，若使用傳統的方法求解此問題，需要耗費大量時間，且又無法確保求解品質優劣。一般而言，人工智慧演算法是目前求解複雜問題的可行方法之一，雖不能保證求出問題的最佳解，但能有效的求出近似解且求解速度也較快，因此本研究嘗試以人工智慧演算法來求解此健康檢查排程問題。
本研究應用三種人工智慧演算法包含基因演算法(GA)、免疫演算法(IA)與粒子群最佳化演算法(PSO)分別探討健康檢查排程問題，以求出最小化完成時間。實驗數值結果顯示，免疫演算法的求解品質優於其他兩種演算法，然而粒子群最佳化演算法的求解速度優於其他兩種演算法。

關鍵字

開放式排程問題 ； 基因演算法 ； 免疫演算法 ； 粒子群最佳化演算法

並列摘要

In recent years, along with concept of “prevention is better than cure” for health, more people will take health examination every year. It is an important issue for health examination center to arrange the health examination schedule for all customers such that the makespan (i.e., total time in the health examination center) is minimized.
This health examination scheduling problem is an extension of the typical open shop scheduling problem. Since the typical open shop scheduling problem is an NP-hard problem, therefore this considered health examination scheduling problem is also an NP-hard problem. It means that it is time consuming to solve when the traditional methods are used for the larger health examination scheduling problem. Generally speaking, artificial intelligence algorithm is one of the useful methods to solve the complicated problem currently. Although artificial intelligence algorithm cannot promise to obtain the optimal solution of the health examination scheduling problem but it can find near optimal solution effectively. Therefore, in this thesis we attempt to adopt artificial intelligence algorithms to solve the health examination scheduling problem.
This research applies three artificial intelligence algorithms, include genetic algorithm, immune algorithm and particle swarm optimization algorithm, to solve the health examination scheduling problem for the minimizing the makespan. Numerical results of test problems show that immune algorithm is more effective than the other two algorithms, and particle swarm optimization algorithm is faster than the other two algorithms.

並列關鍵字

open shop scheduling problems ； genetic algorithm ； immune algorithm ； particle swarm optimization

參考文獻

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

5. 林豐澤(2005)，「演化式計算下篇：基因演算法以及三種應用實例」，智慧科技與影應用統計學報，3卷，1期，頁29-56。

6. 張冠群(2010)，醫療健檢排程問題及其遺傳演算優化法，臺灣大學工業工程學研究所，碩士論文。

22. 蘇桂成(2014)，應用人工智慧演算法探討需多種工序的多工件開放式排程問題，國立虎尾科技大學工業工程與管理研究所，碩士論文。

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