本研究探討多處理器最佳化工作排程問題(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.