一種更快的作業(yè)排序算法

從帶有限期的作業(yè)排序貪心算法可以看到:當找到下一個要插入隊列中的作業(yè)的位置后,

需要將隊列中位于它后面的所有作業(yè)均向后移動一個位置，算法中有許多時間浪費在移動作

業(yè)的位置上。如果能一次找準下一個要插入到隊列中的作業(yè)的位置，則可避免隊列中作業(yè)位

置的移動，為算法節(jié)省不少時間,這是算法值得改進的地方。為了給后繼作業(yè)留下盡可能大的

選擇空間，在考慮作業(yè)i時，將/0、、2],[dj-1,di]中最大的空閑時間區(qū)間

分配給作業(yè)i。

通過使用不相交集合的UNION與FIND算法以及使用一個不同的方法來確定部分解的

可行性，可以把JS的計算時間由OS?)降低到數量級相當接近于0(")。如果J是作業(yè)的可

行子集，那么可以使用下述規(guī)則來確定這些作業(yè)中的每一個作業(yè)的處理時間：若還沒給作業(yè)

i分配處理時間，則分配給它時間片a],其中a應盡量取大且時間片[a—1,a]是空

的。此規(guī)則就是盡可能推遲對作業(yè)i的處理。于是，在將作業(yè)一個一個地裝配到J中時,

就不必為接納新作業(yè)而去移動J中那些已分配了時間片的作業(yè)。如果正被考慮的新作業(yè)不存

在像上面那樣定義的a,這個作業(yè)就不能計入J。

例5.3設n=5,(p1,...,p5)=(20,15,10,5,1),(d1,...,d5)=(2,2,1,3,3)?

J已分配時間片正被考慮作業(yè)動作

0無1分配口2

{1}[1,2]2分配[0,1]

{1,2}[0,1],[1,2]3不適合，舍棄

{1,2}[0,1],[1,2]4分配12,3]

{1,2,4}[0,1],[1,2],[2,3]5舍棄

最優(yōu)解是1={1,2,4}

由于只有n個作業(yè)且每個作業(yè)花費一個單位時間，因此只需考慮這樣一些時間片

[i-l,i]A<i<b,其中》=min{〃,max{句}}。為簡便起見，用i來表示時間片/一1,/]。

實現上述調度規(guī)則的一種方法是把這b個期限值分成一些集合。對于任一期限值i,設“是

使得〃,Yi的最大整數且是空的時間片。為避免極端情況，引進一個虛構的期限值0和時間

片[一1,0]。當且僅當〃,=〃,，期限值i和j在同一個集合中，即所要處理的作業(yè)的期限值如

果是i或j,則當前可分配的最接近的時間片是〃，…顯然，若i<j,則i,i+l,i+2,…"都

在同一個集合中。因此，上述方法就是作出一些以期限值為元素的集合，且使同一集合中的

元素都有一個當前共同可用的最接近的空時間片。對于每個期限值當前最接近

的空時間片可用線性表元素尸⑴表示，即/(，)=々。使用集合表示法，把每一個集合表示

成一棵樹。根節(jié)點就認為是這個集合。最初，這b+1個期限值最接近的空時間片是

F(i)^i,O<i<b,并且有b+1個集合與b+1個期限值相對應。用P⑺把期限值i鏈接到

它的集合樹上。開始時P⑺=-1,0??〈人。如果要調度具有期限d的作業(yè)，就需要去尋找

包含期限值min{〃,d}的那個根。如果這個根是j且只要尸(/)。0,則尸(J)是最接近的空

時間片。在使用了這一時間片后，其根為j的集合應與包含期限值尸(/)-1的集合合并。

過程FJS描述了這個更快的算法。易于看出它的計算時間是0(9(2/,〃))。它用于F

和P的空間至多為2n個字節(jié)。

算法5.5作業(yè)排序的一個更快算法

lineprocedureFJS(D,n,b,J,k)

〃假定P\-PiPn'b=min{〃,max{48〃

〃J是最優(yōu)解，D是期限值?！?/p>

integerb,D(n),J(n),F(O:b),P(O:b)

fori-0tondo

F(i)-i；P(i)—1〃將樹置初值〃

repeat

k-0

fori-1tondo

j-FIND(min(n,D(i)))

ifF(j)#Othenk—k+l;J(k)-i〃選擇作業(yè)i的判斷條件〃

L-FIND(F(j)-l);callUNION(L,j)

F(j)-F(L)

endif

repeat

endFJS

例5.4設〃=7,(p],…，P)=(35,30,25,20,15,10,5)和(用…,4)=(4,2,4,3,4,8,3)。

利用算法FJS求解上述作業(yè)排序問題的最優(yōu)解。

考

慮

F(0)F⑴F(2)F(3)F(4)F⑸F(6)F(7)樹J

作

'Ik

01234567

無012345670

@@@)@@@@

0123567

F(0)F(DF(2)F⑶F(4)F⑸F(6)F(7)

-1-1-1-2-1-1-1

11

012335674

567

F(0)F(DF(2)F⑶F(4)F(5)F⑹F(7)01：

-1-21-1-1-1

，L4

21,2

2?4Q

01133567

F(0)F(l)F⑵F(3)F(4)F(5)F(6)F⑺O1567

-1-4-1-1-1

3一1,2,3

41

01113567

1

F(0)F⑴FQ)F(3)F(4)F⑸F(6)F⑺567

(-5-1-1-1

41,2,3,4

。/1

43

00113567

1567

F(0)F⑴FQ)F(3)F(4)F⑸F(6)F⑺

511-

舍1,2,3,4

°Y?

棄

00113567

156

F(0)F(DF(2)F⑶F(4)F(5)F(6)F⑺

0@

60\411,2,3,4,6

00113566中2①3①