在此篇論文中，我們成功提出一個支援網格運用的組合式批次工作排程器。此排程器主要有兩個特色。第一個特色是此排程器採用批次處理，因此此排程器能夠配置一組趨近最佳組合的資源給工作。另一個特色是當分配資源給工作時，此排程器設計為兩階段式的考量。第一個階段著重於單一網域的計算，此階段的優點在於沒有額外跨網域間的通訊成本。因此當分配資源時，此排程器能夠專注考量該如何提升資源使用率。第二個階段著重於結合多個網域的計算。此階段的優點在於由於能夠彈性分配資源，但是經常需要付出額外的通訊成本。因此當分配資源時，此排程器同時考量該如何提升資源使用率以及縮減跨網域間的通訊成本。由於上述的特點，此排程器能夠有效的縮短工作執行時間以及提升資源的使用率。實驗的結果顯示使用此排程器能夠成功的比其他排程器減少64%的執行時間以及增加98%的資源使用率。

In this paper, we have proposed a combinational batch job scheduler for computational grids. There are two main characteristics of our scheduler. The first feature is our scheduler adopts the batch mode. The scheduler is able to select the approaching optimal allocation without missing it. Another feature is our scheduler is designed as the two-phase scheduling. The first phase focuses on the single-site computing. The advantage of the first phase is no extra communication overhead in the inter-site network. The scheduler is able to concentrate its attention on packing a set of jobs into a single site tightly. The second phase focuses on the multi-site computing. The scheduler not only takes the high packing potential into account, but also makes many efforts on reducing the inter-site communication overhead. Therefore, our scheduler is able to reduce the turnaround time and increase the resource utilization efficiently. The experiments show that our scheduler succeeds in reducing the turnaround time about 64 % and increasing the resource utilization about 98 % than other scheduler.

1. Foster I, K.C. “The Grid: Blueprint for a Future Computing Infrastructure”, Morgan Kaufmnn: San Francisco, CA, 1999.
2. Mark Baker, R.B. & Laforenza. “Grids and Grid Technologies for Wide-Area-Distributed Computing”, International Journal of Software: Practive and Experience (SPE) 32, Issue 15, pp.1437-1466, 2002.
3. Dumitrescu, C. & Foster, I. “Usage Policy-based CPU Sharing in Virtual Organizations”, Grid Computing, 2004, pp.53-60, 2004.
4. Elmroth, E. & Gardfjll, P. “Design and Evaluation of a Decentralized System for Grid-wide Fairshare Scheduling”, First IEEE Conference on e-Science and Grid Computing, pp. 221-229, 2005.
5. James Frey, T.T. & Tuecke, S. “Condor-G: A Computation Management Agent for Multi-Institutional Grids”, the Tenth IEEE Symposium on High Performance Distributed Computing (HPDC), pp. 7-9, 2001.
6. Fran German, R.W. & Shao, G. “Application-Level Scheduling on Distributed Heterogeneous Networks”, Supercomputing '96, 1996.
7. Ligang He, S.A.J. & Nudd, G.R. “Dynamic Scheduling of Parallel Jobs with QoS Demands in Multiclusters and Grids”, Grid Computing, pp.402 – 409, 2004.
8. Shmueli, E. & Feitelson, D.G. “Backfilling with Lookahead to Optimize the Performance of Parallel Job Scheduling”, Job Scheduling Strategies for Parallel Processing, pp. 228-251, 2003.
9. D. P Spooner, S.A.J. & Nudd, G.R. “Local Grid Scheduling Techniques Using Performance Prediction”, Computers and Digital Techniques, IEE Proceedings 150, pp. 89-96, 2003.
10. William M. Jones, W.B.L.I. & Pang, L.W. “Characterization of Bandwidth-Aware Meta-Schedulers for Co-Allocating Jobs Across Multiple Clusters”, The Journal of Supercomputing, pp. 135-163, 2005.
11. Carsten Ernemann, V.H. & Yahapour, R. “Enhanced Algorithms for Multi-Site Scheduling”, Grid Computing, pp. 219-231, 2002.
12. Tyng-Yeu Liang, Chun-Yi Wu, Jyh-Biau Chang, Ce-Kuen Shieh and Pei-Hsin Fan. “Enabling Software DSM System for Grid Computing”, ISPA 2005, 2005.
13. Li, K. “IVY: A Shared Virtual Memory System for Parallel Computing”, In Proceddings of the 1988 International Conference on Parallel Processing (ICPP' 88), pp. 94-101, 1998.
14. Buyya, R. & Murshed, M. “GridSim: A Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for Grid Computing”, The Journal of Concurrency and Computation: Practice and Experience 14, 2002.
15. Casanova, H. “SimGrid: A Toolkit for the Simulation of Application Scheduling”, Proceedings of the First IEEE/ACM International Symposium on Cluster Computing and the Grid, 2001.
16. Takefusa, A. “Bricks: A Performance Evaluation System for Scheduling Algorithms on the Grids”, JSPS Workshop on Applied Information Technology for Science, 2001.
17. Houda Lamehamedi, Z.S. & Deelman, E. “Simulation of Dynamic Data Replication Strategies in Data Grids”, Proceeding of 12th Heterogeneous Computing Workshop, 2003.
18. R.Buyya, M. Murshed, D. Abramson. “A deadline and budget constrained cost-time optimization algorithm for scheduling task farming applications on global Grids”, In 2002 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2002), Las Vegas, 2002.
19. H. Casanova, G. Obertelli, Francine Berman and Rich Wolski, “The AppLeS parameter sweep template: User-level middleware for the Grid”, Proc. The Super Computing Conference (SC 2000), Texas, 2000.
20. Rejesh Raman, Miron Livny and Marvin Solomon, “Resource Management through Multilateral Matchmaking”, Proceedings of the Ninth IEEE Symposium on High Performance Distributed Computing (HPDC9), Pittsburgh, Pennsylvania, pp. 290-291, August 2000.
21. Sudharshan Vazhkudai, Steven Tuecke and Ian Foster, “Replica Selection in the Globus Data Grid”, Proc. Of the First IEEE/ACM International Conference on Cluster Computing and the Grid (CCGRID 2001), IEEE computer Society Press, pp. 106-113, May 2001.
22. Songnian Zhou, Xiaohu Zheng, Jingwen Wang and Pierre Delisle, “Utopia: a Load Sharing Facility for Large, Heterogeneous Distributed Computer Systems”, Software—Practice & Experience, pp.1305-1336, 1993.
23. Jennifer M. Schopf, “A General Architecture for Scheduling on the Grid”, special issue of JPDC on Grid Computing, April 2002.
24. Jarek Nabrzyski, “Knowledge-based Scheduling Method for Globus”, Globus Retreat, Redondo Beach, 1999.
25. Sukanya Suranauwarat, Hideo Taniguchi, “The Design, Implementation and Initial Evaluation of an Advanced Knowledge-based Process Scheduler”, ACM SIGOPS Operating System, pp. 61-81, 2001.
26. OpenPBS. http://www.openpbs.org.
27. Nicolas Capit, Georges Da Costa, Yiannis Georgiou, Guillaume Huard, Cyrille Martin, Gregory Mounie, Pierre Neyron, Olivier Richard, “A Batch Scheduler with High Level Components”, Cluster computing and Grid 2005 (CCGrid05), 2005.
28. D.R. Ghormley, D. Petrou, S. H. Rodrigues, A. M. Vahdat, “GLUnix: A Global Layer Unix for a network of workstation”, Software Practice and Experience, 1998.
29. IBM Corporation. “Using and Administering LoadLeveler – Release 3.0”, Document Number SC23-3989-00, August 1996.
30. Silver, http://www.supercluster.org/projects/silver/.
31. Maui Scheduler, http://www.supercluster.org/maui/.
32. Carl Albing. “Cray NQS: Production Batch for a Distributed Computing Work”, In Proceedings of the 11th Sun User Group Conference and Exhibition, pp. 302-309, December 1993.
33. Rajkumar Buyya, David Abramson, Jonathan Giddy, “Nimrod/G: An Architectrue for a Resource Management and Scheduling System in a Global Computational Grid”, HPC ASIA 2000, IEEE CS Press, USA 2000.
34. Mitshisa Sato, Hidemoto Nakada, Satoshi Sekiguchi, Stoshi Matsuoka, Umpei Nagashima, Hiromitsu Takagi, “Ninf: A Network based Information Library for Global World-Wide Computing Infrastructure”, In Proceedings of HPCN’97, pp. 491-502, 1997.
35. Casanova H., Dongarra, J., “NetSove: A Network Server for Solving Computational Science Problems”, International Journal of Supercomputer Applications and High Performance Computing, pp. 212-223, 1997.