請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9059完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 劉邦鋒 | |
| dc.contributor.author | Ping-Yi Lin | en |
| dc.contributor.author | 林秉毅 | zh_TW |
| dc.date.accessioned | 2021-05-20T20:07:57Z | - |
| dc.date.available | 2009-08-20 | |
| dc.date.available | 2021-05-20T20:07:57Z | - |
| dc.date.copyright | 2009-08-20 | |
| dc.date.issued | 2009 | |
| dc.date.submitted | 2009-08-05 | |
| dc.identifier.citation | [1] Jianzhong Du, Joseph Y-T. Leung, and Gilbert H. Young. Scheduling chainstructured
tasks to minimize makespan and mean flow time. Inf. Comput., 92(2):219–236, 1991. [2] J. D. Ullman. Np-complete scheduling problems. Journal of Computer and System Sciences, 10(3):384–393, 1975. [3] M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman and Co. New York, NY, USA., 1979. [4] T. Braun, H. Siegel, N. Beck, L. Boloni, M. Maheswaran, A. Reuther, J. Robertson, M. Theys, B. Yao, D. Hensgen, and R. Freund. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing, 61(6):810–837, 2001. [5] Rashid Al-Ali Kaizar, Rashid J. Al-ali, Kaizar Amin, Gregor Von Laszewski, Omer F, DavidW.Walker,Mihael Hategan, and Nestor Zaluzec. Analysis and provision of qos for distributed grid applications. Journal of Grid Computing, 2:163–182, 2004. [6] Klaus Krauter, Rajkumar Buyya, and Muthucumaru Maheswaran. A taxonomy and survey of grid resource management systems. Software Practice and Experience, 32:135–164, 2002. [7] Warren Smith, Ian Foster, and Valerie Taylor. Scheduling with advanced reservations. In In Proceedings of IPDPS00, pages 127–132, 2000. [8] Anthony Sulistio and Rajkumar Buyya. A grid simulation infrastructure supporting advance reservation, 2004. [9] Andrew Stephen Mcgough, Ali Afzal, John Darlington, Nathalie Furmento, Anthony Mayer, and Laurie Young. Making the grid predictable through reservations and performance modelling. Comput. J., 48(3):358–368, 2005. [10] M. Wieczorek, M. Siddiqui, A. Villazon, R. Prodan, and T. Fahringer. Applying advance reservation to increase predictability of workflow execution on the grid. pages 82–82, 2006. [11] C. Castillo, G.N. Rouskas, and K. Harfoush. On the design of online scheduling algorithms for advance reservations and qos in grids. pages 1–10, 2007. [12] C. Castillo, G.N. Rouskas, and K. Harfoush. Efficient resource management using advance reservations for heterogeneous grids. pages 1–12, 2008. [13] Gurmeet Singh, Carl Kesselman, and Ewa Deelman. A provisioning model and its comparison with best-effort for performance-cost optimization in grids. In HPDC ’07: Proceedings of the 16th international symposium on High performance distributed computing, pages 117–126, New York, NY, USA, 2007. ACM. [14] Holly Dail, Otto Sievert, Fran Berman, Henri Casanova, Asim Yarkhan, Sathish Vadhiyar, Jack Dongarra, Chuang Liu, Lingyun Yang, Dave Angulo, and Ian Foster. Scheduling in the grid application development software project, 2003. [15] Jia Yu, Rajkumar Buyya, and Kotagiri Ramamohanarao. Workflow scheduling algorithms for grid computing. In Studies in Computational Intelligence. Springer, 2008. [16] Peter Brucker. Scheduling Algorithms. Springer, 2007. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9059 | - |
| dc.description.abstract | 這篇論文介紹了將具有順序限制的工作排程到可使用時間被分割成一段段的處理器上的方法。我們討論了兩種順序限制的狀況─樹狀及鏈狀。我們證明在樹狀限制下的工作排程是一個NPC的問題，接著我們對於線性順序的工作排程提出動態規劃演算法取得最佳解。該動態規劃演算法可以被推廣到異質環境中，亦可推廣以解決似樹狀結構的工作排程問題。而為了減少排程的時間，我們提出了三種不同的演算法。實驗結果顯示，我們的三種演算法即使與以動態規劃取得的最
佳解比較，仍然可以得到近似最佳的排程。 | zh_TW |
| dc.description.abstract | This paper introduces techniques in scheduling jobs with dependency constraint to processors whose available time are fragmented into time slots. We discuss two job dependency patterns – tree and chains. We show that it is NP-complete to schedule jobs with a tree dependency pattern. Then we propose a dynamic programming algorithm to get the optimal schedule for assigning jobs with linear dependency. The dynamic programming can be generalized to heterogeneous environment and tree-like dependency structure. In order to reduce the time of scheduling we also propose three different heuristics. Experimental results indicate that these heuristics do provide near optimal schedules even when compared against the optimal solution found by the dynamic programming. | en |
| dc.description.provenance | Made available in DSpace on 2021-05-20T20:07:57Z (GMT). No. of bitstreams: 1 ntu-98-R96922123-1.pdf: 346705 bytes, checksum: bf7a8a861d27b2a74daba89b40c9b71d (MD5) Previous issue date: 2009 | en |
| dc.description.tableofcontents | Acknowledgement i
Chinese Abstract ii Abstract iii 1 Introduction 1 2 RelatedWorks 4 3 Problem Description 6 3.1 Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4 Dynamic Programming 10 4.1 Dynamic Programming Algorithm . . . . . . . . . . . . . . . . . . . . . 10 4.1.1 Table Element Definition . . . . . . . . . . . . . . . . . . . . . . 11 4.1.2 Recursive Formula . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.1.3 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.1.4 Generalization . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5 Heuristics 17 5.1 The Chain Ordering Heuristic . . . . . . . . . . . . . . . . . . . . . . . 17 5.1.1 Average Execution Time . . . . . . . . . . . . . . . . . . . . . . 17 5.1.2 Expected Makespan . . . . . . . . . . . . . . . . . . . . . . . . 18 5.2 Longest Job First Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . 19 6 Experiments 21 6.1 Environment Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 6.2 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 7 Conclusion 24 Bibliography 25 | |
| dc.language.iso | en | |
| dc.title | 網格系統中時間限制的工作排程 | zh_TW |
| dc.title | Job Scheduling Techniques for Grid Systems with
Temporal Constraints | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 97-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 王大為,薛智文 | |
| dc.subject.keyword | 時間限制,工作順序,動態規劃, | zh_TW |
| dc.subject.keyword | Temporal constraints,Job dependency,dynamic programming., | en |
| dc.relation.page | 26 | |
| dc.rights.note | 同意授權(全球公開) | |
| dc.date.accepted | 2009-08-05 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-98-1.pdf | 338.58 kB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。