一种更快的作业排序算法

一种更快的作业排序算法

从带有限期的作业排序贪心算法可以看到:当找到下一个要插入队列中的作业的位置后,

需要将队列中位于它后面的所有作业均向后移动一个位置，算法中有许多时间浪费在移动作

业的位置上。如果能一次找准下一个要插入到队列中的作业的位置，则可避免队列中作业位

置的移动，为算法节省不少时间,这是算法值得改进的地方。为了给后继作业留下尽可能大的

选择空间，在考虑作业i时，将/0、、2],[dj-1,di]中最大的空闲时间区间

分配给作业i。

通过使用不相交集合的UNION与FIND算法以及使用一个不同的方法来确定部分解的

可行性，可以把JS的计算时间由OS?)降低到数量级相当接近于0(")。如果J是作业的可

行子集，那么可以使用下述规则来确定这些作业中的每一个作业的处理时间：若还没给作业

i分配处理时间，则分配给它时间片a],其中a应尽量取大且时间片[a—1,a]是空

的。此规则就是尽可能推迟对作业i的处理。于是，在将作业一个一个地装配到J中时,

就不必为接纳新作业而去移动J中那些已分配了时间片的作业。如果正被考虑的新作业不存

在像上面那样定义的a,这个作业就不能计入J。

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

J已分配时间片正被考虑作业动作

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舍弃

最优解是1={1,2,4}

由于只有n个作业且每个作业花费一个单位时间，因此只需考虑这样一些时间片

[i-l,i]A<i<b,其中》=min{〃,max{句}}。为简便起见，用i来表示时间片/一1,/]。

实现上述调度规则的一种方法是把这b个期限值分成一些集合。对于任一期限值i,设“是

使得〃,Yi的最大整数且是空的时间片。为避免极端情况，引进一个虚构的期限值0和时间

片[一1,0]。当且仅当〃,=〃,，期限值i和j在同一个集合中，即所要处理的作业的期限值如

果是i或j,则当前可分配的最接近的时间片是〃，…显然，若i<j,则i,i+l,i+2,…"都

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

元素都有一个当前共同可用的最接近的空时间片。对于每个期限值当前最接近

的空时间片可用线性表元素尸⑴表示，即/(，)=々。使用集合表示法，把每一个集合表示

成一棵树。根节点就认为是这个集合。最初，这b+1个期限值最接近的空时间片是

F(i)^i,O<i<b,并且有b+1个集合与b+1个期限值相对应。用P⑺把期限值i链接到

它的集合树上。开始时P⑺=-1,0«»〈人。如果要调度具有期限d的作业，就需要去寻找

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

时间片。在使用了这一时间片后，其根为j的集合应与包含期限值尸(/)-1的集合合并。

过程FJS描述了这个更快的算法。易于看出它的计算时间是0(9(2/,〃))。它用于F

和P的空间至多为2n个字节。

算法5.5作业排序的一个更快算法

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

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

〃J是最优解，D是期限值。〃

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〃选择作业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求解上述作业排序问题的最优解。

考

虑

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①