應用人工智慧演算法於多處理器最佳化工作排程問題之研究

Artificial Intelligence Approaches for the Multiprocessor Scheduling Problem

沈峻緯(Chun-Wei Shen)

指導教授 ： 謝益智

國立虎尾科技大學/管理學院/工業管理系工業工程與管理碩士班/碩士(2017年)

摘要

本研究探討多處理器最佳化工作排程問題(Multiprocessor Scheduling Problem, MSP)，此問題相似於一般生產排程問題，已是一個困難的NP-hard問題，然而卻有更多的工作先後順序關係之限制條件。此問題的目的是在給定多處理器(Multiprocessor)數量、工作(tasks)數量、各工作於各處理器上的工作時間、通訊時間及工作存在先後順序的情況下，在多個處理器上進行工作排程，如何有效地分配每項工作於處理器中，在每項工作不衝突下，使總工作時間最少。本研究設計了一個新的編碼方式，得出多處理器排程問題的可行排程路徑，並結合不同的人工智慧演算法來使總工作時間最少，以使工作效率達到最大化。
本研究應用四種演算法，分別為基因演算法(Genetic Algorithm, GA)、免疫演算法(Immune Algorithm, IA)、粒子群演算法(Particle Swarm Optimization, PSO)及模擬退火演算法(Simulated Annealing, SA)於本研究所提出的簡易編碼方式解決此問題。測試問題分為兩部分，第一部分為自行設計具有已知最佳解之測試問題，第二部分以過去學者部分資料庫問題做為測試問題。本研究將比較四種演算法對此多處理器最佳化工作排程問題的表現。由數值結果顯示，不論於求解速度或是求解品質上，模擬退火演算法皆優於其餘三種演算法。

關鍵字

多處理器排程問題 ； 基因演算法 ； 免疫演算法 ； 粒子群演算法 ； 模擬退火演算法

並列摘要

This thesis explores Multiprocessor Scheduling Problem (MSP) which is similar to the general production scheduling problem, and it is a difficult NP-hard problem. However, there are more restrictions of task precedence for the MSP. The purpose of this problem is to effectively minimize the total completion time of all tasks such that the precedence constraint of task is satisfied when the number of multiprocessors, the number of tasks, the amount of work time spent on each processor, and the communication time between processors are given. In this thesis, a new coding scheme was proposed to convert any permutation of random integers into a feasible scheduling for the MSP, and then embedded it into different artificial intelligence algorithms to minimize the total completion of all tasks.
This thesis applies four different artificial intelligence algorithms, including Genetic Algorithm (GA), Immune Algorithm (IA), Particle Swarm Optimization (PSO) and Simulated Annealing (SA) for solving this MSP problem. There are two parts in the test problem. The first part of test problems is the designed test problem with known best solution. The second part of test problems is generated based upon some test problems in the database created by the the other scholars. This thesis compares the performance of four algorithms for the MSP. The numerical results show that SA is superior to the other three algorithms in terms of solution speed and quality of solution.

並列關鍵字

Multiprocessor Scheduling Problem ； Genetic Algorithm ； Immune Algorithm ； Particle Swarm Optimization ； Simulated Annealing

參考文獻

5.李維平、王雅賢、江正文(2008)。粒子群最佳化演算法改良之研究。工程與技術學刊，4(2)，51-62。

8.徐志明、陳子安、李漢宗(2011)。以基因規劃和人工免疫演算法最佳化薄型晶圓片切割參數。明新學報，37(2)，165-183。

10.陳惠國、余彥儒(2013)。圖書館書籍通閱移送之車輛途程問題-巨集啟發式演算法之應用。運輸學刊，25(1)，1-29。

11.葉進儀、林軒仲(2014)。結合基因演算法與模擬退火法於多重 DNA 序列之比對。品質學報，21(5)，305-328。

9.張志平、劉孝先(2014)。應用柔性演算法於航太鋁合金銲接參數最佳化之研究。品質學報，21(3)，205-216。