隨著雲端服務的蓬勃發展，許多學者投入提升雲端叢集的運算效率與工作資源分配的研究。目前為止的研究多針對CPU核心的運算，也有一些是針對不同的需求或限制條件下的工作排程研究，專注於多使用者狀況或提升資源利用度的機制，但極少數討論工作時間需求，更少有研究將工作分配和資料的分散儲存性質共同考慮，資料的分散儲存性質也是叢集運行效能很重要的一個關鍵。
本篇論文提出一個使工作在需求時間內完成的分配機制，此機制分成兩個主要部分，計算需求的運算資源數量及提高資料的局部性。本機制考慮多工作情況、工作的運算需求、輸入資料的分佈等因素。本機制致力於使工作符合時間需求，並且執行時具有高的資料在地性，提升雲端叢集整體的效能。
實驗結果顯示本篇論文提出的方法能夠有效提高取得在地資料的比例，並透過使用提出的計算運算資源需求量，使多重工作在期望的時間內完成。

Recently, there are many researchers investigate about improving system utilization and job scheduling method for cloud computing. Current researches are mostly focusing on computing with CPU core. There were many researchers interested in improving the MapReduce scheduling and allocation method in different goals or requirements. There were few works discuss about real-time jobs with time requirements, much less consider data locality issue which is crucial for performance in large cluster. This thesis proposed a job allocation method that allocate jobs to meet their deadlines. This allocation method include two parts, calculating required number of computing resource and resource assignment mechanism.
This allocation method consider multiple jobs, requirement of jobs and data locality issue in GPU-based cluster. This mechanism focus on allocate jobs meet their completion time goals and improving data locality ratio. The experimental results showed that the allocation method we proposed could increase the ratio of fetching local data. Through calculating required number of computing resource could let jobs meet their deadlines.

[1] B. He, W. Fang, Nang K. Govindaraju, Q. Luo and T. Wang, “Mars: A MapReduce Framework on Graphics Processors,” Proceedings of the 17th international conference on Parallel architectures and compilation techniques, pp. 260-269, 2008.
[2] M. Zaharia, D. Borthakur, J. Sen Sarma, K. Elmeleegy, S. Shenker and I. Stoica, “Job Scheduling for Multi-User MapReduce Cluster,” Technical Report No. UCB/EECS-2009-55, 2009.
[3] M. Zaharia, D. Borthakur, J. Sen Sarma, K. Elmeleegy, S. Shenker and I. Stoica, “Delay Scheduling: A Simple Technique for Achieving Locality and Fairness in Cluster Scheduling,” Proceedings of the 5th European conference on Computer systems, pp. 265-278, 2010.
[4] J. Polo, D. Carrera, Y. Becerra, M. Steinder, and I. Whalley, “Performance-driven task co-scheduling for mapreduce environments,” In Network Operations and Management Symposium (NOMS), pages 373 –380, 19-23, 2010.
[5] D. Yoo, K. Mong Sim, “A Comparative Review of Job Scheduling for MapReduce,” 2011 IEEE International Conference on Cloud Computing and Intelligence Systems (CCIS), pp. 353-358, 2011.
[6] B. Thirumala Rao, L. S. S. Reddy, “Survey on Improved Scheduling in Hadoop MapReduce in Cloud Environments,” International Journal of Computer Applications. Vol. 34, p28, 2011
[7] X. Lin, Y. Lu, J. Deogun, and S. Goddard., “Real-time divisible load scheduling for cluster computing,” In Real Time and Embedded Technology and Applications Symposium, pages 303 –314, 2007.
[8] Jeffrey Dean and Sanjay Ghemawat., “Mapreduce: simplified data processing on large clusters,” In OSDI’04: Proceedings of the 6th conference on Symposium on
Opearting Systems Design & Implementation, pages 10–10, 2004.
[9] Fei Teng, Frédéric Magoulès, Lei Yu, Tianrui Li, “A novel real-time scheduling algorithm and performance analysis of a MapReduce-based cloud,” The Journal of Supercomputing, Springer Science Business Media New York 2014,
[10] K. Kc, K. Anyanwu, “Scheduling Hadoop Jobs to Meet Deadlines,” IEEE Second International Conference on Cloud Computing Technology and Science (CloudCom), pp. 388-392, 2010.
[11] A. Bezerra, P. Hernández, A. Espinosa, J. Carlos Moure, “Job Scheduling for Optimizing Data Locality in Hadoop Clusters,” Proceedings of the 20th European MPI Users' Group Meeting, pp. 271-276, 2013.
[12] Y. Zhao, W. Wang, D. Meng, Y. C. Lv, S. Zhang, J. Li, “TDWS: a Job Scheduling Algorithm based on MapReduce,” Proceedings of IEEE 7th International Conference on Networking, Architecture, and Storage. pp. 313-319, 2012
[13] Rodrigo N. Calheiros, Rajiv Ranjan, Anton Beloglazov, Cesar A. F. De Rose, and Rajkumar Buyya, “CloudSim: A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms,” In Proceedings of Software: Practice and Experience (SPE), Volume 41, Number 1, Pages: 23-50, 2011.
[14] Apache Hadoop, http://hadoop.apache.org/
[15] Hadoop Fair Scheduler, http://hadoop.apache.org/docs/r1.2.1/fair_scheduler.html