在雲端運算的環境中，映射與簡化模型是用於實現大型叢集資料運算與處理的程式模型，在實現雲端服務的發展中，許多新興服務也由此模型延伸來提升處理的效能。結合服務組合與雲端運算的研究議題，則在陸續的發展當中。本論文在雲端運算的架構下，提出複合型服務的階層式排程機制來達到結合映射與簡化模型進行服務排程的規劃。階層式排程的目的在於將客端的服務階層與資源端的任務階層納入排程的考慮範圍來決定工作的優先權，而資源配置則會依雲端架構的基礎，考慮資源的在地性以及整體工作完成率來進行。
在執行階層式排程時，首先將複合服務拆解成多個單一服務，依照單一服務在複合服務中的地位以及服務特性來決定服務階層的優先權；然後將排序後的單一服務依照服務池特性進行分類，服務池的分類依據是以映射簡化模型的各階段歷史花費時間為主，另外還包含不能應用映射化簡模型的四種服務型態；最後則在各服務池中，依照服務池特性進行資源配置，不同服務池應用不同配置法則來達到資源利用的提升，在執行時，可用的資源要進行配置前，會根據資源在地性以及相依任務之完成率計算出任務的適用程度，來決定將服務池中最合適的任務配置到該資源上。
在本系統的模擬實驗中，建立了數組不同情境的客端複合服務要求，並將前述之排程機制納入進行驗算，將階層式排程機制和雲端運算架構(Hadoop)預設使用的先進先出排程機制(FIFO Scheduling)進行比較，結果顯示假如在不同型態的複合服務組合下，使用階層式排程機制皆能有效的改善整體複合服務的執行效率(約45%)，而在不同的複合服務組合配置下，使用此機制也能有不錯的表現，尤其是在I/O制限的服務上，能達到較好的執行效能，有效減少了硬碟溢出(Disk Spill)的發生機率。

Map and Reduce model is a programming model implemented in the data-intensive and compute-intensive cloud environment. In the development of cloud computing, many applications are based on the model to enhance the performance. The research topics combined of composition services and cloud computing are successively improved. The thesis is based on cloud framework, and had proposed a hierarchical scheduling scheme strategy for the composition services architecture to achieve planning of composition service scheduling with Map/Reduce model. The goal of hierarchical scheduling is to decide the job priority according to both service-level and task-level in the resource side. And the resources are allocated by taking the data locality and total job completion rate into account on the basis of cloud framework.
While executing hierarchical scheduling strategy, it first decomposes a composition service into several simple services. According to the relationship and characteristics of simple services in a CSP, the scheduling strategy decides the priority of service-level scheduling. Then the ranked simple services are categorized into three kinds of pools. The basis of pool classification is mainly determined by the consumption time of Map stage and Reduce stage. Besides, the pools also include another four types that could not apply the Map/Reduce model. Finally, in each pool, it applies different resource allocation methods to enhance the resource utility. At runtime, whenever there is resource available, the scheduling in task-level would compute the priority value that a task in the pool is suitable to execute on the resource or not. The priority value is decided by the data locality and dependent services’ completion rate.
In the numerical evaluation, it uses a Markov model to generate various scenarios of client requested composition services. Then it evaluates the strategy by applying the scheduling strategy mentioned above to compare with the default first-in-first-out scheduling (FIFO) of Hadoop. The simulation results show that in different types of composition services, hierarchical scheduling strategy improves the total CSPs performance. In different distribution of composition services, the proposed strategy also performs well, especially in I/O-Bound services. It achieves better performance (about 45 %) and efficiently decreases the probability of disk spill.

[AZU] Azure, Available: http://msdn.microsoft.com/en-us/windowsazure/default.aspx
[BAR09] J. Barbosa , Belmiro Moreira, "Dynamic job scheduling on heterogeneous clusters", In the Proceedings of the 8th International Symposium on Parallel and Distributed Computing, pp.3-10, 2009.
[BUY08] Rajkumar Buyya, Chee Shin Yeo, and Srikumar Venugopal, "Market-Oriented Cloud Computing: Vision, Hype, and Reality for Delivering IT Services as Computing Utilities", In Proceedings of the 10th IEEE International Conference on High Performance Computing and Communications, pp. 5-13, 2008.
[CAP] Capacity Scheduler Guide, Available: http://hadoop.apache.org/common/docs/r0.20.2/capacity_scheduler.html
[CHE08] S. Chen, S. W. Schlosser, "Map-Reduce Meets Wider Varieties of Applications", IRP-TR-08-05, Technical Report, Intel Research Pittsburgh, May, 2008.
[CHE09] Cheng-Yi Chien, "A Service Prediction Method to Enhance the Efficiency of Proactive Resource Allocation on SOA", A thesis submitted to the graduate division in partial fulfillment of the requirements for the degree of master in Institute of Computer Science and Information Engineering, National Cheng Kung University, 2009.
[DEA04] J. Dean, and S. Ghemawat, "MapReduce: Simplied Data Processing on Large Clusters", In Proceedings of 6th Symposium on Operating Systems Design and Implementation, 2004.
[DOR09] Tim Dornemann, Ernst Juhnke, Bernd Freisleben , "On-Demand Resource Provisioning for BPEL Workflows Using Amazon's Elastic Compute Cloud", In the Proceedings of the 9th IEEE/ACM International Symposium on Cluster Computing and the Grid, pp. 140-147, 2009.
[EC2] Amazon Elastic Compute Cloud (Amazon EC2), Available: http://aws.amazon.com/ec2/.
[EMR] Amazon Elastic MapReduce, Available: http://aws.amazon.com/elasticmapreduce/
[EUC] Eucalyptus, Available: http://open.eucalyptus.com/
[GAR79] M.Gary and D.Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness," Freeman, 1979.
[HAD] Apache Hadoop project, Available: http://hadoop.apache.org/.
[HDF] Apache Hadoop Distributed File System, Available: http://hadoop.apache.org/common/docs/current/hdfs_design.html
[NUT] Nutch, Available: http://nutch.apache.org/
[OWL04] Semantic Markup for Web Services, Available: http://www.w3.org/Submission/OWL-S/.
[STA06] Garrick Staples, "TORQUE resource manager", In the Proceedings of the ACM/IEEE conference on Supercomputing, No. 8, 2006.
[SUN09] Sung Ho Chin, Taeweon Suh, Heon Chang Yu, "Adaptive service scheduling for workflow applications in Service-Oriented Grid", Springer The Journal of Supercomputing, vol. 52, no. 3, pp. 253-283, 2009.
[TIA09] Chao Tian, Haojie Zhou, Yongqiang He, Li Zha, "A Dynamic MapReduce Scheduler for Heterogeneous Workloads", In the Proceedings of the 8th International Conference on Grid and Cooperative Computing, pp.218-224, 2009.
[VAI] Vaidya, Available: http://hadoop.apache.org/common/docs/current/vaidya.html.
[WU09] B. Wu, C. H. Chi, Z. Chen, et al, "Workflow-based resource allocation to optimize overall performance of composite services," Future Generation Computer System, vol. 25, no. 3, pp. 199-212, 2009.
[XU09] Meng Xu, Lizhen Cui, Haiyang Wang, Yanbing Bi , "A Multiple QoS Constrained Scheduling Strategy of Multiple Workflows for Cloud Computing", IEEE International Symposium on Parallel and Distributed Processing with Applications, pp. 629-634, 2009
[ZAH08] Matei Zaharia, Andy Konwinski, Anthony D. Joseph, Randy Katz, Ion Stoica , "Improving MapReduce Performance in Heterogeneous Environments", In Proceedings of 8th Symposium on Operating Systems Design and Implementation, 2008.
[ZAH09] Matei Zaharia, Dhruba Borthakur, Joydeep Sen Sarma, Khaled Elmeleegy, Scott Shenker and Ion Stoica, "Job Scheduling for Multi-User MapReduce Clusters", Technical Report, No. UCB/EECS-2009-55, 2009