劉邦鋒臺灣大學:資訊工程學研究所周揚儒Chou, Yang-RuYang-RuChou2010-06-092018-07-052010-06-092018-07-052009U0001-0508200910200300http://ntur.lib.ntu.edu.tw//handle/246246/185441這篇論文主要討論在異質環境中週期性工作的排程問題。系統中總共有m台異質的處理器及n個一樣的工作。每隔一段固定時間會釋出一個工作，每一個工作要排到一台處理器上執行，並且不能被中途中斷。這個問題的目標是讓所有工作完成時間的總和為最小。們借用Dessouky等人所提出的演算法，證明了它對於我們所討論的問題而言，是個近似演算法，我們進而導出，它的近似比例跟最快的處理器處理工作所需的時間相關。This paper considers a scheduling problem for periodic jobs in a heterogeneous environment. There are m heterogeneous processors and n identical jobs. Jobs are released one at a time periodically. Each job is assigned to a processor for execution. Preemption is not allowed. The goal is to minimize the summation of completion time ofll the jobs.e borrow the idea from Dessouky et al. to propose an approximation algorithm for scheduling identical and periodic jobs to heterogeneous processors. We show that there is a competetive ratio related to the processing time of the fastest processor in this problem.Acknowledgement ihinese Abstract iibstract iii Introduction 1 RelatedWork 4 Model 6 Approximation Algorithm 9.1 Optimal-makespan Algorithm 9.1.1 Early Completion-time First 9.1.2 Match and Delay 10.2 Theoretical Lower Bound 10.3 Approximation Ratio 14 Performance Evaluation 21.1 Dynamic Programming 21.1.1 Experimental Setting 22.1.2 Experimental Results 22.2 Uniform-distributed Processing Time 24.2.1 Experimental Setting 24.2.2 Experimental Results 25.3 Two-hump-distributed Processing Time 27.3.1 Experimental Setting 28.3.2 Experimental Results 28 Conclusion 30ibliography 31555678 bytesapplication/pdfen-US週期性工作排程最佳化異質環境近似演算法動態規劃Periodic jobsscheduling optimizationheterogeneous environmentsapproximation algorithmdynamic programmingthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/185441/1/ntu-98-R96922054-1.pdf