異質環境中週期性工作的排程技巧

Scheduling Techniques for Periodic Jobs in a Heterogeneous Environment

周揚儒(Yang-Ru Chou)

指導教授 ： 劉邦鋒

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

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

摘要

這篇論文主要討論在異質環境中週期性工作的排程問題。系統中總共有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 of
all the jobs.

We 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.

並列關鍵字

Periodic jobs ； scheduling optimization ； heterogeneous environments ； approximation algorithm ； dynamic programming

參考文獻

[1] M.I. Dessouky, B.J. Lageweg, J.K. Lenstra, and S.L. Velde. Scheduling identical jobs on uniform parallel machines. In Statistica Neerlandica, volume 44, pages 115 -123, 1990.

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

[3] R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Ronnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. In Discrete Optimization II, pages 287– 326, 1977.

[5] Peter Brucker. Scheduling Algorithms. Springer, 2007.

[7] Cynthia Phillips, Clifford Stein, and Joel Wein. Task scheduling in networks, 1996.