加入分割觀念的超級排程

Super Sequence with Decomposition

程鈺翔(Chun Shain Cheng)

指導教授 ： 黃士殷

元智大學/工程學院/電機與資訊工程研究所/碩士(1997年)

摘要

隨著電腦界迅速的發展與進步，即時系統在現代是扮演著越來越重要
的角色，比如核能控制、飛行導航，甚至工廠流程管理均可見到即時性系
統應用，而這些都需即時系統的嚴密控制以避免出錯；因為這些工作沒達
成將會對財產或生命造成嚴重損害，故即時系統的正確性是非常重要的。
即時系統上工作的『正確性』是以工作能否在其所訂的期限前完成為準則
。我們的系統是架構在單一處理器上， 工作性質有幾點：工作執行時不
可中途插入其他工作，以及依照時間的特性來進行排程，由這些時間特性
會產生如同行事曆的排程，指出工作何時該開始與結束。

本篇研究所討論的是能在完成最多工作的前提下，花費時間為最少的
最佳工作排程 。若一排程是total ordering，則可應用dynamic
programming技巧在 求出；若非total ordering則此問題是NP-complete
[3]。可是過去研究的Heuristic approaches卻沒辦法保證一定能產生
feasible schedule，這可由它們需拒絕掉不少工作可得知，另一種產生
目錄方式（例如Branch-and-bound搜尋法）卻會花許多時間，都有其缺點
。

為了能更快求得optimal schedule，在此篇我們提出一個演算法，分
三個步驟，第一是將工作集以preceding relation關係作分割以降低搜尋
空間，第二是採用super sequence [18] 來減少測試工作集中合適的序列
個數，第三再對各序列排程，找出個別的最佳排程，將個別序列的最佳排
程比較以獲得整體最好的工作集排程。

關鍵字

即時系統 ； 超級序列 ； 最佳排程

並列摘要

With the fast development of computer technology, real-time
computing systems play a more and more important role in many
contemporary applications, such as flight control, control of
nuclear reactors, and flow-control management in factory. A
fault in such an application may be life-threatening, and highly
expensive, so the "correctness" of real-time system is very
important. "Correctness" of real-time system depends on the task
which can finish before their deadline. Our system is based on
uniprocessor , and the task property is non-preemptive and of
equal weight. A time based scheduler generates as an output a
calendar which specifies the time instants at which the tasks
start and finish.
In this paper, we discuss how to derive a schedule in which
the number of finished tasks is maximized, and the finish time
of the whole schedule is minimized. Even a total ordering, this
can be done in time by dynamic programming technique, where n
is the size of the tasks. If the restriction of the total
ordering is released, it is known to be NP-complete[3], On one
hand, Heuristic approaches can*t guarantee that a optimal
schedule can be generated. One he other hand, Branch-and-Bound
search will spend much time on producing the search catalog.

In order to compute, the optimal schedule, in a faster way
we propose an algorithm in three steps. In the first step, we
decompose the task set using preceding relations[18] to reduce
the search space, In the second step, we use the super sequence
[21] which is proved to be useful in reducing the search space
for testing the feasibility of subset , In last step, we compute
the optimal schedule for all tasks through the combination of
the optimal scheduled generated for each subset.

並列關鍵字

real time systems ； super sequence ； dynamic programming ； preceding relation ； Non-Preemption ； NP-complete

參考文獻

concept in scheduling n jobs on a single machine with ready times and

due dates. Operations Research, 31(1):114-127, Jan. 1983.

[3] M. R. Garey and D. S. Johnson. Computers and Intractability, a Guide to the Theory of NP-Completeness. W. H. Freeman Company,

[4] D. W. Gillies and J. W-S. Liu. Greed in resource scheduling. In

[5] O. Gudmundsson, D. Mosee, K.T. Ko, A.K. Agrawala, and S.K.