請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43833完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 劉邦鋒 | |
| dc.contributor.author | Hung-Jui Chang | en |
| dc.contributor.author | 張紘睿 | zh_TW |
| dc.date.accessioned | 2021-06-15T02:29:59Z | - |
| dc.date.available | 2009-08-20 | |
| dc.date.copyright | 2009-08-20 | |
| dc.date.issued | 2009 | |
| dc.date.submitted | 2009-08-15 | |
| dc.identifier.citation | [1] LCG: LHC Computing Grid. http://lcg.web.cern.ch/LCG/.
[2] BIRN: The Biomedical Informatics Research Network. http://www.nbirn.net/. [3] J. D. Ullman. Np-complete scheduling problems. Journal of Computer and System Sciences, 10(3):384–393, 1975. [4] 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. [5] C. Chekuri, R. Motwani, B. Natarajan, and C. Stien. Approximation techniques for average completion time scheduling. In SODA, pages 609–618, 1997. [6] L. A. Hall, D. B. Shmoys, and J. Wein. Scheduling to minimize average completion time: Off-line and on-line algorithms. In SODA, pages 142–151, 1996. [7] Y. Guan,W. Xiao, R. K. Cheung, and C. Li. A multiprocessor task schedulingmodel for berth allocation: heuristic and worst-case analysis. Operations Research Letters, 30(5):343–350, 2002. [8] S. Albers. Better bounds for online scheduling. In STOC, pages 130–139, 1997. [9] M. Dell’Amico,M. Iori, and S. Martello. Heuristic algorithms and scatter search for the cardinality constrained p | |
| dc.identifier.citation | cmax problem. Journal of Heuristics, 10(2):169–204,
2004. [10] M. R. Garey and R. L. Graham. Bounds for multiprocessor scheduling with resource constraints. SIAM Journal on Computing, 4(2):187–200, 1975. [11] E. Naroska and U. Schwiegelshohn. On an on-line scheduling problem for parallel jobs. Information Processing Letters, 81(6):297–304, 2002. [12] R. Yahyapour U. Schwiegelshohn, A. Tchernykh. Online scheduling in grids. In 22nd IEEE International Symposium on Parallel and Distributed Processing, pages 1–10, 2008. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43833 | - |
| dc.description.abstract | 本篇論文提出了將進入系統時間，執行時間及所需處理器皆相異的工作指派到不同處理器基數上的排程演算法。我們證明了這是一個NP完備的問題，並提出了動態規劃的方法求得最佳解。由於動態規劃需要大量的時間計算，我們還提出了有效的加速法來改善我們的動態規劃。我們還提出了快速的啟發示算法來解個個問題。實驗結果說明了部份啟發示算法不僅是執行時間快速，也能提供相當良好的解答。 | zh_TW |
| dc.description.abstract | This paper proposes scheduling algorithms for assigning jobs with different release time and execution time, to machines with heterogeneous processor cardinality. We show that this scheduling problem is NP-complete, and propose dynamic programming to find the optimal schedules. Since the dynamic programming is time-consuming we propose techniques that improve the efficiency of the dynamic programming. We also propose heuristic algorithms for this scheduling problem. Experimental results suggest that some of the heuristics not only compute the answer efficiently but also provide good solution. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T02:29:59Z (GMT). No. of bitstreams: 1 ntu-98-R96922136-1.pdf: 3600929 bytes, checksum: 2478b4dc5f48787775395ecd91fe3db4 (MD5) Previous issue date: 2009 | en |
| dc.description.tableofcontents | Acknowledgement i
Chinese Abstract ii Abstract iii 1 Introduction 1 2 Related Works 3 3 Model and Problem Definition 5 3.1 Grid System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.2 Job Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.3 A Schedule Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.4 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 4 Algorithms 8 4.1 NP-completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4.2 Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4.3 Dynamic Programing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.3.1 Table Element Definition . . . . . . . . . . . . . . . . . . . . . . 9 4.3.2 Recursive Formula . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.3.3 Time complexity . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.4 Improvements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.5 Heuristic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.6 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5 Experimental Results 18 5.1 Environment Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5.2 All-Zero-Release-Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5.3 Non-Zero-Release-Time . . . . . . . . . . . . . . . . . . . . . . . . . . 20 6 Conclusion 24 Bibliography 25 | |
| dc.language.iso | en | |
| dc.subject | 分散式系統 | zh_TW |
| dc.subject | 排程 | zh_TW |
| dc.subject | 完工時間 | zh_TW |
| dc.subject | 動態規劃 | zh_TW |
| dc.subject | NP完備 | zh_TW |
| dc.subject | 處理器基數 | zh_TW |
| dc.subject | NP-complete | en |
| dc.subject | makespan | en |
| dc.subject | schedule | en |
| dc.subject | distributed system | en |
| dc.subject | Processor cardinality | en |
| dc.subject | dynamic programing | en |
| dc.title | 異質處理器基數的分散式系統中的排程技巧 | zh_TW |
| dc.title | Job Scheduling Techniques for Distributed Systems with Heterogeneous Processor Cardinality | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 97-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 王大為,薛智文 | |
| dc.subject.keyword | 處理器基數,分散式系統,排程,完工時間,動態規劃,NP完備, | zh_TW |
| dc.subject.keyword | Processor cardinality,distributed system,schedule,makespan,dynamic programing,NP-complete, | en |
| dc.relation.page | 26 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2009-08-17 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-98-1.pdf 未授權公開取用 | 3.52 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。