(3.215.183.251) 您好!臺灣時間:2021/04/22 22:53
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:沈峻緯
研究生(外文):Chun-Wei Shen
論文名稱:應用人工智慧演算法於多處理器最佳化工作排程問題之研究
論文名稱(外文):Artificial Intelligence Approaches for the Multiprocessor Scheduling Problem
指導教授:謝益智謝益智引用關係
指導教授(外文):Yi-Chih Hsieh
學位類別:碩士
校院名稱:國立虎尾科技大學
系所名稱:工業管理系工業工程與管理碩士班
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2017
畢業學年度:106
語文別:中文
論文頁數:111
中文關鍵詞:多處理器排程問題基因演算法免疫演算法粒子群演算法模擬退火演算法
外文關鍵詞:Multiprocessor Scheduling ProblemGenetic AlgorithmImmune AlgorithmParticle Swarm OptimizationSimulated Annealing
相關次數:
  • 被引用被引用:2
  • 點閱點閱:430
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:99
  • 收藏至我的研究室書目清單書目收藏:2
本研究探討多處理器最佳化工作排程問題(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.
摘要..............i
Abstract..............ii
誌謝..............iv
目錄..............v
表目錄..............viii
圖目錄..............x
第一章 緒論..............1
1.1研究背景與動機..............1
1.2研究目的..............1
1.3研究方法與流程..............1
1.4論文架構..............2
第二章 文獻探討..............4
2.1多處理器最佳排程問題..............4
2.1.1多處理器排程問題概述..............4
2.1.2多處理器排程問題相關文獻..............4
2.2基因演算法..............6
2.2.1基因演算法介紹..............6
2.2.2基因演算法步驟..............6
2.3免疫演算法..............10
2.3.1免疫演算法介紹..............10
2.3.2免疫演算法步驟..............11
2.4粒子群演算法..............12
2.4.1粒子群演算法介紹..............12
2.4.2粒子群演算法步驟..............13
2.5模擬退火演算法..............14
2.5.1模擬退火演算法介紹..............14
2.5.2模擬退火演算法步驟..............15
2.6田口方法..............17
2.6.1品質損失..............17
2.6.2直交表..............18
2.6.3信號雜訊比分析..............19
第三章 研究問題與研究方法..............21
3.1研究問題..............21
3.1.1問題描述..............21
3.2.2問題假設..............22
3.2編解碼方式..............22
3.3問題參數設定..............26
3.4基因演算法及免疫演算法參數分析..............27
3.4.1基因演算法及免疫演算法之參數設定..............27
3.4.2基因演算法及免疫演算法之田口實驗結果..............28
3.5粒子群演算法參數分析..............29
3.5.1粒子群演算法之參數設定..............29
3.5.2粒子群演算法之田口實驗結果..............30
3.6模擬退火演算法參數分析..............31
3.6.1模擬退火演算法參數設定..............31
3.6.2模擬退火演算法田口實驗結果..............31
第四章 測試問題與結果討論..............33
4.1設備環境及參數設定..............33
4.2測試問題..............33
4.2.1第一部分測試問題(自設問題2題)..............33
4.2.2第二部分測試問題 (資料庫問題8題)..............36
4.3測試結果..............50
4.3.1自設測試問題結果討論..............50
4.3.2資料庫測試問題結果討論..............51
4.3.3自設測試問題最佳解..............56
4.3.4資料庫測試問題最佳解..............60
4.4統計檢定..............80
第五章 結論..............84
5.1結論..............84
5.2未來研究方向..............85
參考文獻..............86
附錄A..............90
附錄B..............100
Extended Abstract..............106
簡歷..............111
1.方志鵬、張陽郎、梁文耀、林鈞傑(2007)。一個對於高光譜影像的二維模擬退火波段選擇方法。航測及遙測學刊,12(4),303-317。
2.吳達彥(2014)。應用人工免疫演算法求解集群路線車輛規劃問題-以機場接送服務為例。國立成功大學交通管理科學系。
3.宋裕祺、王俊穎(2015)。結合粒子群演算法與遺傳演算法於斜張橋鋼索預力之最佳化設計。中國土木水利工程學刊,27(1),1-10。
4.李福星、王建欽(2015)。應用模擬退火法於自動化配電系統中饋線末端設備之時間電流協調曲線最佳設定。技術學刊,30(4),351-361。
5.李維平、王雅賢、江正文(2008)。粒子群最佳化演算法改良之研究。工程與技術學刊,4(2),51-62。
6.李輝煌(2011)。田口方法-品質設計的原理與實務(第四版)。新北市:高立圖書。
7.林李旺(2013)。突破品質水準-實驗設計與田口方法之實際應用。臺北市:全華圖書股份有限公司。
8.徐志明、陳子安、李漢宗(2011)。以基因規劃和人工免疫演算法最佳化薄型晶圓片切割參數。明新學報,37(2),165-183。
9.張志平、劉孝先(2014)。應用柔性演算法於航太鋁合金銲接參數最佳化之研究。品質學報,21(3),205-216。
10.陳惠國、余彥儒(2013)。圖書館書籍通閱移送之車輛途程問題-巨集啟發式演算法之應用。運輸學刊,25(1),1-29。
11.葉進儀、林軒仲(2014)。結合基因演算法與模擬退火法於多重 DNA 序列之比對。品質學報,21(5),305-328。
12.葉雙福、張燕鐸、卓延穎、林明德(2009)。應用禁忌搜尋法與模擬退火法作為污水下水道設計之輔助工具-以中興大學為例。中國土木水利工程學刊,21(2),193-206。
13.詹曉苓(2006)。運用混合演算法於田口動態特性之參數設計最佳化。國立交通大學工業工程與管理系所博士論文。
14.廖國清(2005)。最佳演算法應用於負載預測及機組排程問題。國立臺北科技大學自動化科技研究所博士論文。
15.鄭金林(2015)。整合基因演算法與灰預測模型於室內溫度預測之研究。國立臺北科技大學自動化科技研究所碩士論文。
16.蘇朝墩(2006)。品質工程。臺北市:三民書局。
17.Aguirre, P. E. R., Pedro, F. P., & de Guadalupe Cota Ortiz, M. (2015). Multi-objective optimization using bat algorithm to solve multiprocessor scheduling and workload allocation problem. Computer Science, 2(2), 41-51.
18.Ahmad, I., & Dhodhi, M. K. (1996). Multiprocessor scheduling in a genetic paradigm. Parallel Computing, 22(3), 395-406.
19.Bao, L., Cai, X., & Ding, Y. (2017, May). An improved immune algorithm for optimization of irrigational water distribution. In Control And Decision Conference (CCDC), 2017 29th Chinese (pp. 1523-1528). IEEE.
20.Chun, J. S., Kim, M. K., Jung, H. K., & Hong, S. K. (1997). Shape optimization of electromagnetic devices using immune algorithm. IEEE transactions on magnetics, 33(2), 1876-1879.
21.De Castro, L. N., & Von Zuben, F. J. (2002). Learning and optimization using the clonal selection principle. IEEE transactions on evolutionary computation, 6(3), 239-251.
22.Eberhart, R., & Kennedy, J. (1995, October). A new optimizer using particle swarm theory. In Micro Machine and Human Science, 1995. MHS''95., Proceedings of the Sixth International Symposium on (pp. 39-43). IEEE.
23.França, P. M., Gendreau, M., Laporte, G., & Müller, F. M. (1996). A tabu search heuristic for the multiprocessor scheduling problem with sequence dependent setup times. International Journal of Production Economics, 43(2-3), 79-89.
24.Fujita, S., & Nakagawa, T. (1999). Lower bounding techniques for the multiprocessor scheduling problem with communication delay. In Parallel Architectures and Compilation Techniques, 1999. Proceedings. 1999 International Conference on (pp. 212-220). IEEE.
25.Goksal, F. P., Karaoglan, I., & Altiparmak, F. (2013). A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery. Computers & Industrial Engineering, 65(1), 39-53.
26.Gupta, S., Agarwal, G., & Kumar, V. (2013). An Efficient and Robust Genetic Algorithm for Multiprocessor Task Scheduling. International Journal of Computer Theory and Engineering, 5(2), 377.
27.Holland, J. H. (1992). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. The MIT Press.
28.Hou, E. S., Ansari, N., & Ren, H. (1994). A genetic algorithm for multiprocessor scheduling. IEEE Transactions on Parallel and Distributed systems, 5(2), 113-120.
29.Houshmand, M., Soleymanpour, E., Salami, H., Amerian, M., & Deldari, H. (2010, April). Efficient scheduling of task graphs to multiprocessors using a combination of modified simulated annealing and list based scheduling. In Intelligent Information Technology and Security Informatics (IITSI), 2010 Third International Symposium on (pp. 350-354). IEEE.
30.Kellerer, H. (1998). Algorithms for multiprocessor scheduling with machine release times. IIE transactions, 30(11), 991-999.
31.Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.
32.Kuila, P., & Jana, P. K. (2014). Energy efficient clustering and routing algorithms for wireless sensor networks: Particle swarm optimization approach. Engineering Applications of Artificial Intelligence, 33, 127-140.
33.Lo, S. T., Chen, R. M., Huang, Y. M., & Wu, C. L. (2008). Multiprocessor system scheduling with precedence and resource constraints using an enhanced ant colony system. Expert Systems with Applications, 34(3), 2071-2081.
34.Mitchell, M. (1995). Genetic algorithms: An overview. Complexity, 1(1), 31-39.
35.Padmavathi, D. G., & Vijayalakshmi, M. (2010). Multiprocessor scheduling for tasks with priority using GA. International Journal of Computer Science and Information Security, 6(3), 93-100.
36.Ren, C., An, N., Wang, J., Li, L., Hu, B., & Shang, D. (2014). Optimal parameters selection for BP neural network based on particle swarm optimization: A case study of wind speed forecasting. Knowledge-Based Systems, 56, 226-239.
37.Scholl, A., Fliedner, M., & Boysen, N. (2010). Absalom: Balancing assembly lines with assignment restrictions. European Journal of Operational Research, 200(3), 688-701.
38.Shachnai, H., & Tamir, T. (2002). Multiprocessor scheduling with machine allotment and parallelism constraints. Algorithmica, 32(4), 651-678.
39.Stone, H. S. (1977). Multiprocessor scheduling with the aid of network flow algorithms. IEEE transactions on Software Engineering, (1), 85-93.
40.Taher, S. A., & Afsari, S. A. (2014). Optimal location and sizing of DSTATCOM in distribution systems by immune algorithm. International Journal of Electrical Power & Energy Systems, 60, 34-44.
41.Tsuchiya, T., Osada, T., & Kikuno, T. (1998). Genetics-based multiprocessor scheduling using task duplication. Microprocessors and Microsystems, 22(3), 197-207.
42.Vincent, F. Y., & Lin, S. Y. (2015). A simulated annealing heuristic for the open location-routing problem. Computers & Operations Research, 62, 184-196.
43.Yang, J., Xu, H., Pan, L., Jia, P., Long, F., & Jie, M. (2011). Task scheduling using Bayesian optimization algorithm for heterogeneous computing environments. Applied Soft Computing, 11(4), 3297-3310.
44.Yuan, J., Zhao, Z., Chen, B., Li, C., Wang, J., Tian, C., & Chen, Y. (2015). An immune-algorithm-based dead-time elimination PWM control strategy in a single-phase inverter. IEEE Transactions on Power Electronics, 30(7), 3964-3975.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔