異質環境之週期性工作排程

Periodic Job Scheduling in Heterogeneous Environments

李龢軒(Ho-Hsuan Lee)

指導教授 ： 劉邦鋒

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2007年)

https://doi.org/10.6342/NTU.2007.10588

摘要

這篇論文在討論一個異質環境之週期性工作排程的問題, 問題的簡述如下, 現在有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.

並列關鍵字

periodic job ； identical job ； scheduling ； heterogeneous processors ； optimal

參考文獻

[1] C.L. Shih S. Su. Modeling an emergency medical services system using computer simulation. Interational Journal of Medical Informatics, 72:57– 72, 2003.

[2] P. Holub L. Hejtmanek. Uniform job scheduling model for distributed processing environment with distributed storage. Technical Report 9, CESNET, 2004.

[4] R.L. Graham. Bounds for certain multi-processing anomalies. Bell System Tech-nical Journal, 45:1563– 1581, 1966.

[6] J. Xu and D. Parnas. Scheduling processes with release times, deadlines, precedence and exclusion relations. IEEE Transactions on Software Engineering, 16(3):360–369, 1990.

[10] A. Thesen. Design and evaluation of tabu search algorithms formultiprocessor scheduling. Journal of Heuristics, 4(2):141–160, 1998.