Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mce.biophys.msu.ru/archive/doc15768/doc.pdf Дата изменения: Mon Oct 29 12:56:30 2007 Дата индексирования: Mon Oct 1 20:35:17 2012 Кодировка:

.., .. () . , . TWO SCHEDULING ALGORITHMS FOR INDEPENDENT TASK ON A UNIFORM PROCESSOR SYSTEM Asnina A.Ya., Tolmatov D.N. (Voronezh) A single-stage system with uniform parallel processors is considered. Two scheduling algorithms for system of uniform processors and independent tasks are suggested. m n . m , . . [1] . , , . . . tiL , i- L- .
89


2. (I)

Fmax (s) = max { t i (s)}, s
1 i n

, t i (s) ­ i- . iL L- i- . :
m L =1 t iL iL

= 1 , i = 1,..,n;

(1)


i =1

n

iL

Fmax, L = 1,..,m;

(2)

L =1


iL

m

iL

Fmax, i = 1,..,n;

(3) (4)



0 , i=1,..,n; L=1,..,m;

Fmax min (5 ) , .., tiL=aLti. tiL (1)
1 iL = 1, aL L = 1 a L t i t i L =1 bL = 1 / aL, ti.
iL


m
m

=

1





m

L =1


m

bL




iL

=

t

i

, Fmax = T, (1) ­ (5), :
L =1


n

bL

iL

=

t

i

, i = 1,..,n;

(6) (7)
90


i=1

iL



T

, L = 1,..,m;


.. . -- -10, 2002, .89-91


L =1
iL

m

iL

T, i = 1,..,n;

(8) (9)



0 , i=1,..,n; L=1,..,m;

T min, (10) [1], T : Tmin =

max

max 1 p m -

1

ti i =1 , p bL L =1



p

ti , i =1 m bL L =1



n

(11)

, Topt , (11)



p

t b

i

i=1 p L

, p = 1,...,m ­ 1, bL ti

: b 1 b 2 .. b m t 1 t 2 .. t n . , p p Topt. . . -, , p . p+1 m p+1 n. 1 . -, , . 2. iL I 91

L =1


2. (I)

P. TIP. TIP I ­ n, P ­ m. Tmin. Tb=(Tb1,...,Tbm) ' Tt=(Tt1,...,Ttn), T t' =( T t' 1 ,..., T tn ), Tb , Tt , , b0=0. Tb Tt T 1.
' k = min i b i T ti - T ti 0 ' s = max ( i Tti - bi T ti 0) . is ik

(

min

' , T ti =ti.

)



Tbk-

is

- = T ts b k T bk - bs

' ti

(12a)

ik

' - = T ti T tk b s . - bs bk

(12b)

2.



ik

, Tbs:=

is Tbs-

Tbs
is

. 3.



ik

Tbk, is=



is

,ik=



ik

Tbk=

:



' ' T ti = T ti - b k ik . Tbk 1.

ik >Tbk, ik= T bk , Tti = Tti - ik , .

' ' ( is > Tbs) is= T bs , Tti = Tti - is , T ti = T ti - bs is . Tbs . 1 3. I . , .. I , . 1. 1 1. i , -

92


.. . -- -10, 2002, .89-93

. I ­ , P ­ , iL. Ik ­ , Pk ­ , mk ­ Pk k- . 0. k = 1, Ik = {1, 2, ..., n}, Pk = {1, 2, ..., m}. 1. Tmin (11) i Ik L Pk, mk=|Pk|. 2. Tmin =
M
k

iI

ti /
k

LPk

bL , 3. -

Tmin =

/
t
ij

M

k

j =1

s =1

b Ls , Mk < mk, 4.

3. I = Ik, P = Pk 5. 4. I = {i1, i2, ..., iM}, P = {p1, p2, ..., pMk} 5. 5. iL i I , L P TIP. 6. Ik Pk I P , . Ik+1 = Ik \ I , Pk+1 = Pk \ P , k = k + 1 1. 2 1 , [1]. 2 1. i , . I 0 ={1,2,..,n} - ,
P0 ={1,2,..,m}- . T








p
0 min

­
p

0 min

I 0 P0 . T

=

j / bs
t
j =1
s =1

,

p < m. 0. I0 I1 =
93


2. (I)

{1,2, ...,p} I2 = {p+1, ...,n} P0 P1 = {1,2,...,p} P2 = {p+1, ..., m}. R, R = . r ­ , r = 0. 1. I1 P1 iL TIP T0 . min 2. R:= R {m ­ r}. 3. I2 P` = P2 \ R T1 min (11). 4.
0 4. T 1 min T min , r:= r + 1, R:= R {m ­ r}. 3. 5. 5. iL i I2 L P = P2 \ R {m ­ r} TIP. 2 2 , [1]. . 1. . ., . . // . . . . 8. II / . . . . ­ .: ­ , 2001, . 457 ­ 462

94