請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/25469
標題: | 異質環境之週期性工作排程 Periodic Job Scheduling in Heterogeneous Environments |
作者: | Ho-Hsuan Lee 李龢軒 |
指導教授: | 劉邦鋒(Pangfeng Liu) |
關鍵字: | 週期性工作,同質工作,排程,異質處理器,最佳解, periodic job,identical job,scheduling,heterogeneous processors,optimal, |
出版年 : | 2007 |
學位: | 碩士 |
摘要: | 這篇論文在討論一個異質環境之週期性工作排程的問題, 問題的簡述如下, 現在有m 個處理器跟n個相同的工作, 工作是週期性地被取得, 每個工作一但可取得之後就必須送到處理器上面, 我們的目的是要使的所有工作的完成時間的總和是最小的.
對於這個異質環境之週期性工作排程的問題, 我們提出一個名字是Minimum-Completion-First (MCF)的演算法, 在所有工作中最後產生的時間小於最快處理器執行時間的條件底下, 我們證明出MCF是最佳解, 另外在一般的情形下, 我們使用實驗模擬的方式展現出MCF會產生出極佳的解. This paper consider a scheduling problem for periodic jobs in a heterogeneous environment. There are m heterogeneous processors and n identical jobs. Jobs are available one at a time periodically. Each job is assigned to a processor. The goal is to minimizes the summation of completion time of all jobs. We propose a Minimum-Completion-First (MCF) for scheduling identical and periodic jobs to heterogeneous processors. We show that MCF is optimal under the restriction that the number of jobs is smaller than the amount of time unit for a fastest processor to process a job. We also conduct experiments to illustrate that MCF produces excellent schedules in general cases. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/25469 |
全文授權: | 未授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-96-1.pdf 目前未授權公開取用 | 178.42 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。