跳到主要內容

臺灣博碩士論文加值系統

(34.226.244.254) 您好!臺灣時間:2021/08/03 03:26
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張家翔
研究生(外文):Chia-Hsiang Chang
論文名稱:基於Hadoop平台之蟻群最佳化排程機制
論文名稱(外文):The Ant Colony Optimization Scheduler Based on Hadoop Platform
指導教授:郭忠義郭忠義引用關係
口試委員:范姜永益馬尚彬薛念林劉建宏
口試日期:2012-01-18
學位類別:碩士
校院名稱:國立臺北科技大學
系所名稱:電資碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2011
畢業學年度:100
語文別:中文
論文頁數:48
中文關鍵詞:Map/ReduceHadoopShort-Job-First蟻群最佳化演算法費洛蒙
外文關鍵詞:Map/ReduceHadoopShort-Job-FirstAnt Colony OptimizationPheromone
相關次數:
  • 被引用被引用:1
  • 點閱點閱:452
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
Map/Reduce近來已經成為大型運算系統的重要開發模型。同時,Hadoop[1]是一個以Map/Reduce為主的開放式原始碼架構,並廣泛地被應用在以大量資料運算為主的雲端計算上。而在雲端架構裡,通常會使用虛擬機器(VM)來做為其運作的平台,因虛擬平台較容易於管理與維護。
蟻群最佳化演算法(Ant Colony Optimization)[2]最初是用來解決旅行業務員(Traveling Salesman Problem, TSP )的問題,其演算法的核心在於模仿螞蟻尋找食物的過程,螞蟻會在尋找食物的時候,沿途分泌一種被稱為費洛蒙(pheromone)的化學物質,而費洛蒙的氣味可以提供給其他螞蟻做為尋找食物與自己回到巢穴的依據。
本論文主要利用蟻群最佳化演算法套用在Hadoop雲端系統排程上,希望透過訓練大量的雲端運算過程來找出最佳的排程,使系統除能具有學習的成效外並且在短時間內優先處理工作量較短的工作,使排程能夠達成類似最短工作優先(Short-Job-First)處理的方式。


Map/ Reduce has recently become an important large-scale computing systems development model. The same time, Hadoop is a Map/ Reduce-based open source framework and widely applied to large amounts of data in the cloud computing-based calculation. In the cloud architectures, usually using the virtual machine (VM) to do its operation platform, the virtual platform for the management and maintenance easier.
Ant Colony Optimization (ACO) originally used to solve the Traveling Salesman Problem(TSP), the algorithm is the core of imitation the ants foraging, when ants search of food, it along the way what is called pheromone secretion of chemical substances, and the smell of pheromones can provided to other ants to find food and as a basis for their return to nest.
This thesis is to discuss how I optimize the resource scheduler of the Hadoop Cloud Computing System by applying Ant Colony Optimization algorithm.by mass training, my method can find the optimized sequence so that the system can learn from previous works and finish up more lighter jobs within a short period of time.thus, my method works in a “Short-Job-First” manner for the scheduler.


摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
表目錄 v
圖目錄 vi
第一章 緒論 1
1.1研究背景與動機 1
1.2研究目的 1
1.3研究方法 2
1.4論文組織與架構 2
第二章 文獻探討 4
2.1Hadoop架構概述 4
2.2Map/Reduce運作模式 8
2.3Fair Scheduler 14
2.4蟻群最佳化演算法(Ant Colony Optimization ACO) 15
第三章 蟻群最佳化理論與方法 18
3.1排程問題模式 18
3.2演算法架構 19
3.3系統架構 23
第四章 案例研究 28
4.1問題描述 28
4.2實驗方法 28
4.3系統環境配置 29
4.4實驗結果與分析 30
4.5相關研究比較 37
4.6實驗結果與討論 38
第五章 結論和未來研究 40
參考文獻 41
附錄 46


[1] Applications Powered By Hadoop: http://wiki.apache.org/hadoop/PoweredBy.
[2] A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed optimization by ant
colonies,” Proceedings of the 1st European Conference on Artificial Life, pp.
134-142, Paris, 1991.
[3] Sanjay, Hgobioff, and Shuntak, “The Google File System,” 19th ACM Symposium on Operating Systems Principles, Lake George, NY, 2003.
[4] Map/Reduce Tutorial,
http://hadoop.apache.org/common/docs/r0.20.2/mapred_tutorial.html.
[5] F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, T. Chandra, A. Fikes, and R. E. Gruber, “Bigtable: A Distributed Storage System for Structured Data,” 7th USENIX Symposium on Operating Systems Design and Implementation, pp. 205-218, 2006.
[6] K. R. Lee, M. H. Fu and Y. H. Kuo, “A Hierarchical Scheduling Strategy for the Composition Services Architecture Based on Cloud Computing,” The 2nd International Conference on Next Generation Information Technology, pp.163-169, 2011.
[7] Apache , http://www.apache.org/.
[8] G. Daoxiong and R. Xiaogang, “A hybrid approach of GA and ACO for TSP,” Proceedings of the World Congress on Intelligent Control and Automation , vol. 3, pp. 2068-2072, 2004.
[9] J. L. Liu, “Rank-based ant colony optimization applied to dynamic traveling salesman problems,” Engineering Optimization, vol. 37, no. 8, pp. 831-847, 2005.
[10] H. H. Zuo and F. L. Xiong, “Novel ant colony algorithm based on local optima clustering and its application in Chinese traveling salesman problem,” Tongji Daxue Xuebao/Journal of Tongji University, vol. 32, pp. 142-144, 2004.
[11] Chekuri, Chandra and P. Martin, “An O(log n) approximation ratio for the asymmetric traveling salesman path problem,” Lecture Notes in Computer Science, vol. 4110 LNCS, pp. 95-103, 2006.
[12] A. Giorgio, B. Vincenzo and L. Luigi, “The on-line asymmetric traveling salesman problem,” Lecture Notes in Computer Science, vol. 3608, pp. 306-317, 2005.
[13] Hadoop Fair Scheduler,
http://hadoop.apache.org/common/docs/current/fair_scheduler.html
[14] M. Zaharia, D. Borthakur, J. S. Sarma, K. Elmeleegy, S. Shenker, and I. Stoica, “Job scheduling for multi-user mapreduce clusters,” EECS Department, University of California, Berkeley, Tech. Rep., 2009.
[15] G. Daoxiong and R. Xiaogang, “A hybrid approach of GA and ACO for TSP,” Proceedings of the World Congress on Intelligent Control and Automation, vol. 3, pp. 2068-2072, Jun. 2004.
[16] Dorigo, M. Gambardella, L.M. IRIDIA and U. V. Brussels “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 53-66, 1997.
[17] A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed optimization by ant colonies,” Proceedings of the 1st European Conference on Artificial Life, pp. 134-142, Paris, 1991.
[18] F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Burrows, T. Chandra, A. Fikes, and R. E. Gruber, “Bigtable: A Distributed Storage System for Structured Data”, 7th USENIX Symposium on Operating Systems Design and Implementation, pp. 205-218, 2006.
[19] P. C.Tsai and W. Chen Huang, “The structure of the CloudGene based on Hadoop platform” Ph.D. Thesis, National Kaohsiung First University of School and Technology, Kaohsiung, Taiwan, 2010.
[20] C. Y. Tseng and Y. L. Chen, "Dynamic Dispatching Tasks Management for H.264 Encoder on Heterogeneous Dual-Core Embedded System," Proceedings of 2010 International Conference on Communications and Mobile Computing, pp. 253-257, 2010.
[21] M. Dorigo and C. Blum, “Ant colony optimization theory: A survey,” Theoretical Computer Science, vol. 344, no. 2-3, pp. 243-278, 2005.
[22] G. D and R. X, “A hybrid approach of GA and ACO for TSP,” Proceedings of the World Congress on Intelligent Control and Automation, vol. 3, pp. 2068-2072, 2004.
[23] A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed optimization by ant colonies,” Proceedings of the 1st European Conference on Artificial Life, pp. 134-142, Paris, 1991.
[24] M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutilonary Computation, no. 1, pp. 53-66, 1997.
[25] J. L. Liu, “Rank-based ant colony optimization applied to dynamic traveling salesman problems,” Engineering Optimization, vol. 37, no. 8, pp. 831-847, 2005.
[26] Z. H. Hao and X. F. Lun, “Novel ant colony algorithm based on local optima clustering and its application in Chinese traveling salesman problem,” Tongji Daxue Xuebao/Journal of Tongji University, vol. 32, pp. 142-144, 2004.
[27] R. W. Conway, “Priority Dispatching and Work-in-Process inventory in a Job Shop,” Journal of Industrial Engineering, vol. 16, pp. 123-130, 1965.
[28] B. Bullnheimer, R.F.Hartl and C. Strauss, “An improved ant system algorithm for vehicle routing problem,” Sixth Viennese workshop on Optimal Control, Dynamic Games, Nonlinear Dynamics and Adaptive Systems, Vienna (Austria), 1999.
[29] Pour, H. Davoud and Nosraty, Mostafa, “Solving the facility and layout and location problem by ant-colony optimization-meta heuristic,” Journal of Production Research, vol. 44, no. 23, pp. 5187-5196, 2006.
[30] Sim, K. Mong and Sun, W. Hong, “Ant colony optimization for routing and load-balancing: Survey and new directions,” IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans, vol. 33, no.5, pp. 560-572, 2003.
[31] L. S. Yong, K. E. Kyoung and Yun, H. Gun, “DNA computing adopting DNA coding method for Hamiltonian path problem,” Proceedings of the International Conference on Artificial Intelligence, vol. 1, pp. 154-157, 2003.
[32] L. F. Perrone, F. P. Wieland, J. Liu, B. G. Lawson, D. M. Nicol, and R. M. Fujimoto, eds “A Bee Colony Optimization Algorithm To Job Shop Scheduling,” Proceedings of the Winter Simulation Conference, pp. 1954-1961, 2006.
[33] J. Adams, E. Balas and D. Zawack, “The shifting bottleneck procedure for job shop scheduling,” Management Science, vol. 34, no. 1, pp. 391-401, 1988.
[34] E. Balas and A. Vazacopoulos, “Guided local search with shifting bottleneck for job shop scheduling,” Management Science, vol. 44, no. 2, pp. 262-275, 1998.
[35] J. Blazewicz, W. Domschke and E. Pesch, “The job shop scheduling problem: conventional and new solution techniques,” European Journal of Operational Research, vol. 93, no. 1, pp. 1-33, 1996.
[36] A. Colorni, M. Dorigo, V. Maniezzo and M. Trubian, “Ant System for Job-Shop Scheduling,” Journal of Operations Research, vol. 34, pp. 39-53, 1994.
[37] T. Yongcai, Z. Qing, S. Lei and C. Pinhua, " Job Scheduling Optimization for Multi-user MapReduce Clusters," International Symposium on Parallel Architectures, Algorithms and Programming, pp. 213-217, 2011.
[38] B. Roy and B. Sussmann, “Les problems d’ordonnancement avec contraintes disjunctives,” Notes DS N. 9 Bis, SEMA, Montrouge, 1964.
[39] Simulated. Annealing, http://www.im.isu.edu.tw/faculty/pwu/heuristic/SA_1.ppt
[40] Tabu Search, http://upwen.ie.nthu.edu.tw/IP/Tabu%20Search.pdf
[41] S.Ibrahim, H. Jin, B. Cheng, H. Cao and S. Wu, “CLOUDLET: Towards MapReduce Implementation on Virtual Machines,” Proceedings of the 18th ACM international symposium on High performance distributed computing, pp. 65-66, 2009.
[42] S. Ibrahim, H. Jin, L. Lu, L. Qi, S. Wu, and X. Shi, “Evaluating MapReduce on Virtual Machines: The Hadoop Case,” Proceedings of the 1st International Conference on Cloud Computing, pp. 519-528, 2009.
[43] T. C. Yang, “A RBAC Based Authorization Mechanism for Private Cloud Computing Environment,” Master Thesis, University of Shih Hsin, Taipei, Taiwan, 2010.
[44] Y. Ge, G. Wei, 2010, “GA-Based Task Scheduler for the Cloud Computing Systems,” International Conference on Web Information Systems and Mining, pp. 181-186, 2010.


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top