close

Вход

Забыли?

вход по аккаунту

?

Градиентный метод составления статических расписаний для конвейерных систем основывающийся на жадных стратегиях.

код для вставкиСкачать
??? 004: 519.854
?. B. ??????
??????????????? ??????????????? ???????????
??. ???????????????, 33, ???????????, 299053, ??????
krotov_k1@mail.ru
??????????? ?????
??????????? ??????????? ?????????? ??? ??????????? ??????,
?????????????? ?? ?????? ??????????
?????????????? ?????? ??????????? ?????????? ????????? ?????? ? ??????????? ???????? ? ????? ?????????? ??????????? ??????????, ?????????????? ?? ?????? ??????????.
???????? ?????: ?????????????? ??????????? ???????, ?????????? ?????????? ???????? ????????? ??????,
??????????? ?????, ?????? ????????.
????????
??????????? ??????? ????????? ?????????????????? ?????????? ???????? ???
????????? ?????? ??????? ? ?????????????? ?????????????? ????????? ? ??????????????
?????????????? ?????? ? GRID-??????. ????????? ?????????????????? ?????????? ???????? ??????? ? ?? ???????????? ??????????? ? ??????? ???????? ???? ? ??????????????
??????????? ? GRID-????????. ????? ?? ????????? ???????? ????????? ?????????????????? ?????????? ???????? ????????? ?????? ? ??????? ???????? ???????? ?? (????????)
?????????????? ?. ?. ????????? ?????? ???????????????? ?? ??????????? ??????????????
? ??????? ???????????? ??????????????. ??????????????????? ?????????? ???????? (????????? ??????) ????????????? ?????? ??????????? ?????? ???? [1] (????? ???????? ?
???? ??????), ??? ???????????? ??????????? ????????? ?????? ?????? ?????? ??????????????????? ???????? (??????????????????? ?????????? ????????) ? ?????????? ???????????? ?????????. ???????? ???? ?????????????? ?????????? ???????? ????????????
????????? ??????? ?????? ????????? ????? (? ????? ?????? n ?????) ????????????????
??????? ?? ???? ????? ?????? ??????????? ??? ?????????? ????????????????? ?????? ??????? ????? ??????????????? ?????????? ???????????? ????????? (????? ??????? ?????
??????????? ??????????? ?????? ????? ????????? ?? ????????? ?? ????????? ?????????).
?????????????? ???????? ???????????? ?? ?????????? ?? ?????????, ?????? ?? ???????
????????? ??? ?????????? ?? ??????????????? ????????? ????????? (?????????????? ???????????, ?????????????? ????????). ?????? ? ???????????? ????????? ???????????: i ?
????? ????????? ?????????? ??????, ??????????????? ?????????? ???????, ???????
?????? ???? ?????????? ? ???????; I ? ????????? ???? ??????, ??????? ????? ??????????
? ?????????????? ???????; n ? ?????????? ???????? ??????, ????? i ? 1,n ); n i ? ??????????
????????? ? ????????? ?????????? ??????, ??????????????? ???????? i (????????? ??-
?????? ?. B. ??????????? ????? ??????????? ??????????? ?????????? ??? ??????????? ??????, ?????????????? ?? ?????? ?????????? // ?????. ???????. ???. ??-??. ?????: ?????????????? ??????????. 2015. ?. 13, ???. 1.
?. 55?73.
ISSN 1818-7900. ╛брзлкм у??. ?б?к?: ╩лыс?о??кслл?б зб?лснс?кк. 2015. ?со 13, ??тшрм 1
╘ ═. B. ═?сзс?, 2015
56
═. B. ═?сзс?
?????? ?????? ?? n i ?????????? ????????). ??????, ???????? ? ????????? i-? ?????????,
?????????????? ??????????????? ?? ??????????. ?????? i ????????????? ?????????, ??????????? ? ??????? ?????????, ?????????????? ?????? i-?? ???? (????????????? ????
??????????? ? ??????? ????????? ?????????, ?????????????? ?????? i-?? ????). ??????????? ?????????? ??????????????????? ????????? i-?? ???? ???????????? ????????? ?????? ???????? ????????? ?????? i-?? ????. ???? ????????? ?????? i-?? ???? ???????? n i
?????????, ?? ?????????????? ??? ?????? ????????? ?????? ???? ????????? ? ??????????? ??????? n i ????? ???. ???? ???????????????? ??????????? ??????? ? ???? ?????? ??????? ? ????????? ??????????? ?? ?? ???? ??????, ????????????? ? ??????? ???????????????????? ???????????. ??? ???? ??????????????, ??? ??????????? ????????? ??????
??????????????????? ????????? ????????? ? ??????????? ?????? ??????? ?? ?????????
????????? (????????? ? ??????????? ?????? ?????????????? ????????? ????????). ?????
?????????? ?????????????? ????????? ? ??????????? ???????? ???????????? ???????????
??????? ??????? ???????? ????????? ?????? ?? ??????????. ??? ??? ?????? ?????????? ??
?????? ???????? ????????, ???????? ? ???????????? ?????????? ???????? ?? ??????????????? ?????????, ????? ????? ???? ???????????? ?????????? ?????????? ??????????????????? ???????? ????????? ??????????????? ??????, ?????????????? ????? ???????
??????? ???????? ?? ??????????. ??????????? ??????? ?? ?????????????? ????????? ?????? ?????????????? ? ?????????????? ???????? ??????????? ??????????????? ? [2?4].
?????????? ?????? ?????????? ?????????????? ?????????, ??????????????? ? ??????
??????, ????????????, ??? ??? ni ? 1 ( i ? 1, n ) ??????????? ????????? ????????? ?????? (??????????? ?????? ?? ?????????? ??????????????? ????????), ??? ???????? ? ????????
?????? ???? ???????????? ?????????? ?????????? ????????.
?????? ??????????
??????????? ?????? ?????? ?????????? ????????? ??????????? ??????????? ??????????
????????? ????????? ?????? ?????? ????? ??? ???????? ?????????? ???????? ? ?????????????? ?????????????? ???????? (? ????????? ? ??????????? ????????) ? ??????????????
????????? ????????? ??????????? ??????????? ???????. ? ??????? [5; 6] 1 ? [9] ??????????? ??????? ???????????? ????? ?????? ?????????? ????????? ????????? ?????? ??? ??????
???? ?????????? ????????? ????????? ??? ????????? ????? ????????? ??????????? ? ??????? ??????????? ?? ??????????? ????? ????????? ????????????. ??? ???? ??????????? ???
?????? (?????? ? ??????, ?????? ? ?????????), ??? ? ???????????? ?????? ????????? ?????????? ?????????? ???????? ????????? ??????. ? ?????? 2 ??????????? ??????? ?????
?????? ?????????? ??? ??????? ??????????? ?? ??????? ?????????? ???????? ? ???????,
?????????????? ???????????? ??????? ?????????. ??? ???? ??????????? ?????? ??????
?????????? ?????????? ????????? ????????? ?????? ??? ????????????? ????? ????????
(2?4 ???????) ? ????? ?????? ? ??????, ? ????? ???????????? ?????? ? ?????????? ???????????? ?????????? ? ??????? ????? ?????? ??????????. ? ???????? ????? ?????? ?. ?. ?????? ????????? ??????? ??????????? ????? ?????????? ?????????????? ????????? ?????? ?? ?????????????? ???????? ? ?????????????? ???????. ?????????? ?????????????
? ???????????? ??????? ????????? ????? ???????????? [7] 3, ? ??????? ???????????????
?????? ???????????? ??????????? ?????????? ????????? ????????? ??????. ????????
???????????? ?????????? ?????? ?????????? ????????? ?????? ??????????? ???????
1
??????? ?. ?. ?????? ? ????????? ??????? ????? ?????? ?????????? ??? ?????? ? ?????????? ????????
? ?? ?????????? ??? ????? ????????????? ???????????. ????. ... ?-?? ???.-???. ????. ?., 2007. 426 ?.; ??????? ?. ?. ????????? ??????? ????? ?????? ?????????? ??? ?????? ??????? ? ?????????? Lmax ? ? w j U j : ????.
? ????. ???.-???. ????. ?., 2006. 131 ?.
2
????? ?. ?. ??????????? ??????????? ????????????? ?????? ????????????????? ????? ? ???????? ??
??????????-??????????????? ?????????: ????. ? ?-?? ????. ????. ?????? ?/?, 2008. 317 ?.
3
?????? ?. ?. ?????? ???????????? ?????????? ? ???? ?????? ????????? ???????. ????. ? ????. ????.
????. ?., 2008. 139 ?.
????кблзл?х обзс? рсрз??нблк? рз?зк?брмк? ??рткр?лкх ?н? мсл?бхб?л?? ркрзбо
57
(? ?????????, [8]). ??????? ????? ????????? ????????? (????????? ?????? ? ???????) ??????????????? ? ?????? [9], ?????? ????????? ??? ?????? ?????????? ?????????? ???????????? ???????????? ????????????? ?????? ?????? (?????????? ??? ?????? ?????? ????)
??? ????????? ?? ???????????? ?????????? ????????. ???????????? ???????? ???????????
??????????, ????????? ? ?????????? ?????????, ????????????? ? ???????, ?? ? ?????
?? ????????????? ????? ?? ???????????????, ??? ?? ??? ?? ??????????? ??? ??????????
?????????? ???? ???????? ????? ???????, ???????????? ?? ??? ????????? ?????? (? ??????????? ?????????? ?????????? ?????????? ??? ?????? ????????? ? ? ????????? ???????? ????????? ??????????? ? ?????? [6]).
?????????? ???? ? ????? ???????? ????????????
???? ?????? ??????? ? ????????????????? ??????? ?????????? ?????????? ?????????
????????? ?????? ? ??????????? ????????. ????????????????? ??????? ?????????? ?????????? ????????? ????????? ?????? ??????? ? ?????? ??????? ??????????? ??????????? ??
??? ??????????????? ????????, ??? ???????????? ???????????? ???????????? ??????????,
? ??????? ??????? ?????????? ???????? ?????? ???? ??????? ?? ????????? ?? ??????????? ??????????? ? ??????????? ?? ?????????????? ??????? ? ???????. ????? ???????, ??????? ??? ???????????? ???????????? ??????????, ??????????? ???????????? ? ???????
???????, ???????? ??????????? ?????????? ?????????? ???????? ????????? ??????. ?????
??? ??????? ?????? ?????????? ??????? ?????????? ???????????? ?????????? ?????? ????
?????? ?????? ??????????? ?????? ???????????? ??????????? ??????????, ???????????
???????? ???????? ??????????? ? ???????????? ??????????. ??? ?????????? ????????????
???? ? ?????? ???????? ??????, ????????? ? ???????????? ???????????? ?????? ??????????
??????????? ?????????? ?????????? ???????? ????????? ??????, ???????????? ╚??????╩
????????? ? ?????????? ???????????. ??? ???? ???????????? ??????????? ?????????? ??????? ??????? ? ?????????? ??????????? ?????????? ????????? ????????? ??????.
???????? ?????????? ??????
??????????????? ?????? ???????? ??????? ? ?????? ???????????, ?. ?. ??? ?????????, ??????????????? ?????????????? ?????? (???? ??????, ?????????? ?????? ??????? ????,
???????????? ????????? ?????? ????????? ????? ?? ???????? ? ?. ?.) ? ???????????????
??????? (?????????? ?????????????? ????????, ?????????? ????????? ?????? ? ?. ?.) ???????? ???????????. ???? ????? i ????????? ????????????? ???? ??????, ??????????????
? ???????, ?, ??????????????, ????????????? ???? ?????????, ??????????? ????????? ????
??????, ????? ????? di ????????? ?????? ??????? ??????????? ? ??????? ??????? i-?? ????
?????? ( i ? 1, n ). ??? ???? ???????? ??????? ??????? ?? ???????? ? ??????? ? ??????? ??????????? ?????? ?? ????????? ?????????, ??? ???? di ? 0 . ????????? ????? l ?????? ??????????????? ???????, ????????? ? ?????? ?????????????? ??????? (l-? ??????? ?????????????? ??????????? ???????), ??????????????? ?????????? l-? ????? ?????????
? ???????, ??? ???? l ? 1, L , ??? L ? ????? ?????????? ????????? ?????????. ?????? ????????? ??????????? ??????? ??????????? ??????????, ??????????????? ??????????? ???
???? ????? ?????????. ?????????? ???????????? ??????????? ? ??????? ???????? ???????????? ??????????? ???????, ??????? ??? ????????????, ???? ????????? ?????????, ???
???? ???? l-? ?????? ????????? ? ?????????? i-? ????????? (? ????????? ?????? i-?? ????), ????????? ?? ????? ???? ????????. ??? ?????????????? ??????? ??????????? ???????
??????????????? ??????? ? ??????????? ?? ??????? ?????????? ?????????????????? ??
??????. ?????????? ?? ?????? l-? ??????? ??????????? ??? ????? i-?? ????????? ??????????????? ?????????? ???????????? ????????? ?????? ?? ???? ???????, ?????????? ??????????????? ?????? ??????????? ?????????? ??? ????????????? ???????????? ????. ? ???????????? ? ???????????? ????????????? ? ???????????? ??????? ????????? N ?????
?????? ( N = {1,2,.., n} , n ? ?????????? ????? ??????), ????????? ??????? ??????????? ? ???-
58
═. B. ═?сзс?
????; ??? ??? ? ??????? ??????????? ????????? ????????? ??????, ?? n ? 1 (??? i ? 1, n ),
?. ?. ??? ?????? ?? n ?????????????? ???????? ????? ???????? ??????????? ?? ??????
?? ??????????.
?????????? ????????? ????????? ?????? (??????? ?? ?????????? ????????) ?????????
??? ? . ?????????? ????????? ?????? (?????????? ????????) ? ? ??? ???????????? ??????????????????? ? l ??????? ?????? ?? ????????? ?? ?????? l-? ???????? ?????????
i
1
2
3
L
( l ? 1, L ), ??? ????? ??? ? ? {? , ?, ? ,..., ? } . ??? ??? ??????? ??????? ?? ??????????
???????? (?????????????????? ? l ( l ? 1, L )) ????????, ?? ??? ???????????? ????? ??????????????????? ? l ?????????? ? ? ???????????? ??????? ??????? ? P ? ( l ? 1, L ) ???????? ????????? ?????? ? ??????? (???????? ??????? ?????????????? ???????? ?? ???????l
???). ??????? pijl ? 1 , ???? ?????? i-?? ???? ???????? ? ?????????????????? ? j-? ??l
?????, pijl ? 0 ? ????????? ??????, ??????? ?????? n ? n , ??? n ? ?????????? ?????
??????.
??? ???????????? ???? ?????? ??????????????? ???????? ????????? ?????? (???????l
??? ????????) ? ??????????? ??????? ? ???????????? ??????? ????????? ???????????: t i ?
???????????? ????????? ????????? ?????? i-?? ???? ?? l-? ???????? ????????? ( l ? 1, L )
0l
??????????????? ????????????? ?? ??? ??????????; (t ji ) ? ??????? ???????? ???????
?????? ????????? ?????? i-?? ????, ?????????? ? ? l j-? ???????. ??? ??? ????? ???????
????????? ?????? ??? ????????????? ????????? ??? ????????? ? ??????????? ??????
????????? ????????? ? ??????????????? ??? ??????????? ?????? ? ?????? ???????
d i ? 0 ?????????? ?? ?????????, ?? ???????????? ?????????????? ??????? ????????? ????????? ?? ????????? ?????? i-? ????? ?? ???????????. ??? ??? ? ??????? ??????????? ????????? ????????? ??????, ?? ???????????? ??????????? ????????? ? ????????? ?????? i-?? ????
l
?? ????????? ?????? k-?? ???? ????? ???? ???????? ? ????????? t i ????????? ?????? ??????????????? i-? ????? ( i = 1, n ) ?? l-? ???????? ??????? ( l ? 1, L ). ???????? ?????????
?????? (t 01
ji ) ( l ? 1, L ) ???????????? ? ???????????? ? ????? ?????? ? P ? ( l ? 1, L ) ???l
0l
?????? ???????: t 0lji ?0 ??? ???? ???????? ??????? (t ji ) , ??????? ????????????? p ijl = 1 .
0l
? ?????? ???? p ijl = 0 , ?? ??????????????? ??? ??????? t 0jil ??????? (t ji ) ????? 0 ( t 0jil = 0 ).
??? ??????? ???????? ????????? ???????? ??????? (t 01
ji ) ???????????? ? ?????? ??????? ( P ) 1 ????????? ???????:
n
2
n
3
n
t101i ? 0 ; t 201i ? ? t h1 ? p1h1 ; t 301i ? ?? t h1 ? p1h , j ; t 401i ? ?? t h1 ? p1h , j ? ?. ?.
h ?1
???????, ??? t
01
2i
j ?1 h ?1
j ?1 h ?1
? 0 ??? ???? ???????? ??????? (t ) , ??????? ????????????? pi12 ? 1 .
0l
ji
0l
? ?????? ???? pi12 ? 0 , ?? ??????????????? ??? ??????? ??????? (t ji ) ????? 0. ? ?????
01
???? ????????? ??? ??????????? t ji ????? ????????? ?????:
k ?1 n
t ki01 ? ?? t h1 ? p1h , j , ??? k ? 1,
j ?1 h ?1
??? k ? ????? ??????? ?????? i-?? ???? ? ?????????????????? ? 1 .
??? l-?? ??????? (??? l ? 1) ???????? ??????? (t 0jil ) ???????????? ??????????? ????:
?) ?????? ?????? (?????? ??????? ??? ?????? i-?? ????, j = 1):
(1)
????кблзл?х обзс? рсрз??нблк? рз?зк?брмк? ??рткр?лкх ?н? мсл?бхб?л?? ркрзбо
59
n
t10,il ? ? pihl ?1 ? (t h0,li?1 ? t il ?1 ) ,
(2)
h ?1
??? ?????? i ???? ?????? ???????????? ?? ??????? ? P ? ( l ? 1, L ) ??? ?????????? ??????
l
??????? ? ?????????????????? ? l (i-? ??? ??????, ?????????????? ? ??????? j = 1 ?? l-?
???????? ?????????);
?) j-? ?????? (j ? 1) ? ??????? ? P ? ( l ? 2 , L ) ??? ?????? i-?? ????:
l
n
?n
?
t 0jil ? max ?? pil,?h1 ? (t h0,li?1 ? t il ?1 ); ? (t 0j ?l 1,h ? t hl ) ? phl , j ?1 ? .
h ?1
? h?1
?
(3)
?????????????? ????????? (1)?(3) ???????? ??????? ??????????????? ???????? ????????? ?????? ???????????????????? ??????????? ? ?????????????? ???????, ?. ?. ????????? ?????????? ??? ????????? ??????????????. ??????????? ???????? ????????? ????????????? ??????????????? ???????? ??????????? ? ??????????? ?? ????? ??????????????
l
???????, ??????? ?????????????? ? ????? [? P ? , (t 0jil ) | l ? 1, L] . ??? ??????? ?????????????
?????????? ??????? ?????? ???? ??????????? ????????, ??????????? ??????????????
? ?????????????? ????????? (1)?(3) ???????? ????????????? ??????????????? ????????.
??????????? ????????? ?????? ??????????? ??????? ????????? ??????, ?????????????
??? ?????????? ??????? (?????????? ?????????? ????????) ? ???????????? ╚??????╩
?????????:
1) ?????????? ? ????? ?????????????? ?? ?????????? ((s?1)-?) ???? ????????? ?????l
?????????????? ?????????? ???????? ? ( s ? 1) ????????? i-?? ???? ??? ????????? ??????????????? ?? ??????;
2) ??????????? ???????????? ?????????????? (???????) ??????????????? ?????????
??? i-?? ???? ?????? ?? ????? ??????????? ??????????????????? ?? ??????? (s-?) ???? ??l
??????? ? ( s ) ;
3) ?????????? ? ?????? ?????????? ??????? ??????? ????? ?????????? ??????? ???? ??l
???????, ?????????? ? ?????????? ????????? ? ????? ?????????????????? ? ??????? ??????????????? ?????? ?? ???? ??????? ????? ? ?? ??????;
4) ? ?????? ???? ????????? ????????? ?????? ???????????????? i-?? ???? ? ??????????????????? ? ( l ? 1, L ) ?? ???? ??????? ????? ? ?? ?????? ?? ???????? ? ??????????
???????? ??????? ???????, ????? ??????????? ????????? ????????? ?????? i-?? ???? ????l
???????? ? ???? ??????????????????? ? ( l ? 1, L ), ????? ? ???? ???????????????????
? ?. ?. ????? ???????, ??? ???????? ??????? ??????????? ??????? ? ????? ????????????
??????? ? ?????? ?? ???????????? ? ?????????? ????????? (???????????? ??????? ??????????? ???????? ????????).
? ???????????? ? ????????????? ????????? ???????????? ?????????? ????????? ??????
?? ????????? s-? ???? ??????????? ??????? ????????? ????????? ?????????? ? ??????????
l
? ??????????????????? ? ( l ? 1, L ) ?????? ?????? i-?? ????, ??? ???? ?? ???????????
l
????? ????????? ?????????????? ??????? ????????? ?????????? ? ??????????????????? ?
l
( l ? 1, L ) ?????? ?????????? (n ? i) ?????. ????? ???????, ?? s-? ???? ????????? ??????????? ?????? ????? ?? ??????????? ???????? ???????????? ??????? (?? ??????????? ??????????? j-? ??????? ? ? ( l ? 1, L ) ?????? ???????????????? i-?? ????). ?? ?????? ???????? ???????????? ??????? ??? ?????? i-?? ???? (??????????????? ????? ???????
l
????????? ?????? ???? ?????, ??????????? ? ? ?? ?????????????? ????? ?????????)
??????????? ??????? ?? ??????????? ??????? ?????? ??????????? (n ? i)-?? ?????, ???
???? ??????? ????????? ??????, ?????????? ?? ?????????????? ????? ?????????, ?? ??l
??????. ? ????? ?????? ??????????? ?????? ????? ?????? ? ??????????? ? ? ?????? ??l
60
═. B. ═?сзс?
???? ????, ???????????? ?? ??????? ? ???? ???????????????????; ??? ???? ??????? ?? ?????????? ?????? ???????????????? i-?? ???? ??????????? ?? ?????? ???????? ???????????
????? ???????????????????, ?????????????? ??? ?????? ?????????????? (i ? 1)-?? ????,
l
? ??????? ????????? ?????? ???? ????? ? ? ?? ??????????.
??? ????? ????, ??? ?? ?????? s-? ???? ????????? ? ?????????? ????? ???????? ?????l
?????? ?????????????????? ? ??????????? ???? ????????? ????????? ?????? i-?? ????,
???????? ?????? ????????????? ????? ??????????????????? ??? ???????? ?????????? ???????? ? ???. ????? ??????, ?? ??? ????????? ???????????? ????????? ? ??????????????????? ? ( s ) ( l ? 1, L ), ? ?????? ?? ????????? ??????? ??????????, ??????????????????
??????? ???????????. ?????? ????????????? ??????????? ??????? ???????? ? ????? ?????? ?????????? ? ??????? ????? ???????????????? ???????. ??????? ???? ???????????????? ??????? ?????????? ????????????? ????????? ?????? ????? ???????, ????? ?????
????? ??????????????? ???????? ???? ???????????. ??????????? ???????? ???????? ????????? ?????? ? ???????? ?????????? ????????? ????????? ??????????? ?????????? ??????? ???? ??????? (?. ?. ?????????? ??????? ???? ???????????????? ??????? ???????????
?? ?????? ??????? ???????? ???????? ????????? ??????). ?????????? ???? ???????????????? ??????? ?????????? ????????????? ???????????? ????????????? ?? ????????????,
?. ?. ??????????? ??? (????????????) ????????. ? ???????? ????, ??????? ??????????? ???
???????????? ???? ????????, ??????????????? ?????????? ???? ???????????????? ???????.
??? ??????????? ???? ???????? ????????????? ???????????? ??????? ????????? ????????? ???????????:
l
1) ???
n
n
i ?1
i ?1
? t 0jil ? pijl > ? (t 0j ?l 1,i ? til ) ? pil, j ?1 l-? ??????? ????????? ??????? ?????????? ??? ??-
??????? ?????? ? j-? ??????? ????? ?? ????????? ? (j ? 1)-? ??????? (????? ???????????????
??????? ??????, ? ?? ?? ???); ????? ???????????? ???????? l-?? ???????? ????????? ??? ??l
???????? ???????? ?????????? ???????? ????????? ?????? ? ?????????????????? ? ( s )
n
???????????? ??????????
n
?? t
j ? 2 i ?1
0l
ji
? pijl ? (t 0j l?1,i ? til ) ? pil, j ?1 ; ?????????? ????????? ???????-
?? ?????????? ????????? ??????? l-?? ???????? ? ???????? ?????????? ?????? ??? ?? ?????????;
l
2) ??? ?????????????????? ? ??????? ??????? ???????? ????????? ? ???????? ?????????? ?????? ???????????, ????? ????????? ????? ???????? ???? L ????????? ???????????
???????, ????????? ? ????????? ?????????? ?????? ??? ?????????, ????? ?????????? ??L
???????? ????
n
n
??? t
l ? 2 j ? 2 i ?1
0l
ji
? pijl ? ( t 0j ?l 1,i ? til ) ? pil, j ?1 ;
3) ??????? ????????? ????????? ??? ?????????? ???????? ??????? ????? ? ?????????
??????????? ?????? ?? ?????????, ???? ??? ?????? ???????? ?????? ??????? ? ??????????????????? ? ( l ? 2 , L ), ??? ??????? ???????? ????????? ???????? ?????? ????????? ???l
??? ???????????, ??? ??? t101i ? 0 ; ??? l-?? ???????? (??? ???????, ??? l ? 1 ) ????? ????????
?????????? ?????? ??? ????????? ? ?????? ??????? ? ( l ? 2 , L ) ???????????? ????????l
n
?? ????
?t
i ?1
0l
1,i
? pil1 ; ????? ??????? ???? l-? ????????? ????????? (??? l ? 2 , L ) ????? ????L
?????? ? ???????????? ? ??????????
n
?? t
l ? 2 i ?1
0l
1,i
? pil1 .
?????? ?? ????????? ??????????? ????? (?????????) ??????? ???? ????????? ????????? ??? ????????? ???????? ?????????? ?????? ???????????? ????????? ?? ???????? ? ???????? ?????????? ?????? ? ?????? ??????? ? ? ( l ? 2 , L ), ? ????? ????????? ?? ??????l
????кблзл?х обзс? рсрз??нблк? рз?зк?брмк? ??рткр?лкх ?н? мсл?бхб?л?? ркрзбо
61
?? ? ???????? ?????????? ?????? ? ????????? j-? ??????? (??? ???????, ??? j ? 1 ). ?????
???????? ??? ????????? ??? ???????? ????????????? ??????????? ??????? ?? ???????
?????????? ???????? (??????? ????????? ??????) ? ??????????????????? ? 1 ( l ? 2 , L )
?????????:
L
n
L
n
n
f ? ?? t10,il ? pil,1 ? ??? t 0jil ? pijl ? ( t 0j ?l 1,i ? til ) ? pil, j ?1 .
l ? 2 i ?1
(4)
l ? 2 j ? 2 i ?1
????????? ????? ? ??????? ??????????? ???????? ???????????????? ??????? ? ( s ) ,
? ??????? ??????????? ????? ?????? ???????? ???????????? ???????, ? ????? ?max ? ??????????? ????????? ??????? ??????????? ???????? ???????????????? ???????. ????????
??????? ? ??????????? ??????? ???????????? ?????????? ????
n
n
? ( s ) ? ?? | pi , j ( s ? g ) ? pi , j ( s ) | / 2 ,
i ?1 j ?1
??? g ? ?????? ?????????????? ???? ?????????, ?? ??????? ??????????? ???????????? ?????? ??????? ? ( s ? g ) ?? ???? ???????? ???????????? (?????????) ??????? ? ( s ) . ????????? ???????? ??????? ??????????? ? (s ) ???????? ?????? 1. ??? ?( s ) ? 1 ????????? ?????? ???????????????? i-?? ???? ?????????? ? ????? ?? ??????????????????? ? ( l ? 1, L ),
l
??? ? ( s ) ? 2 ????????? ?????? i-?? ???? ?????????? ? ???? ??????????????????? ?
l
( l ? 1, L ) ? ?. ?.
??????? ???????? ?????????? ?????????? ????????? ????????? ?????? ? ?????????????? ?????? ????????? Greedy Sheduler. ???????? ??????????? ???????????? ????????? ?????????????? ?????? i-?? ???? ? ??????????????????? ? ( l ? 1, L ) Greedy Sheduler ????????????:
l
1) ?????????? ?????? ???????????????? i-?? ???? ? ? ( l ? 1, L ) ????? ?????????? ??
? ????? ?????? ??????????????????;
l
2) ????????? ????????? ?????? i-?? ???? ? ??????????????????? ? ( l ? 1, L ) ?? ????
??????? ????? ? ?????? ??????????????????? ? ??????????? ?? ???????? ???????? ??????l
????? ? (s ) (? ????? ?????????????????? ? ( l ? 1, L ), ? ???? ??????????????????? ? ,
? ???? ??????????????????? ? ?. ?. ? ??????????? ?? ???????? ??????? ??????????? ? (s ) ???????? ???????????????? ???????);
l
3) ????????? ????????? ?????? i-?? ???? ? ??????????????????? ? ????????????? ????????? ???????? ??????? ??????? f, ??? ???? ??????????? ??????????? ????????? ??????? f,
l
???????????? ??? g, ?????????????? ? ???????????????? ??????????????????? ? , ? ???????
l
l
?????????? ????????? ??????????????? ?????? ( l ? 1, L , ??????????????? ?????
?
?f g ? 0 ???? ??????
?
?
?f g (? ( s )) ? 0 ? ????? ?????????? ???????? ??????? ??????? f , ??????????????? ???-
?f g ? 0 ?????????? ????????? ??????? ??????? f [14]), ?. ?.
??????? ? ( s ? g ) , ??????????????? ?? ?????? ????????? ?????????? ? ( s ) , ??? ????????
????????? ?????? i-?? ???? ????????????? ??? ??????? ???????? ??????????? ?? s-? ????;
4) ? ?????? ???? ????????????? ?????????? ??????? ? ?f g ? 0 ????? ??????????? g, ??
????? ???? g, ??? ??????? ??????????? ??? ???????, ?????????? ?? ??????????? g?, ??? ???????? max ( ? ? g f (? ( s )) ? 0 ) ;
g
l
5) ? ??? ??????????????????? ? , ? ??????? ????????? ????????? ?????? i-?? ???? ??????????? ?????????? ??????? max ( ? ? g f (? ( s )) ? 0 ) , ??????? ?????? ??????????? (?. ?.
g
62
═. B. ═?сзс?
??????????????? ??????? ??????????? ??? ???????? ???????????), ????? ???? ????????
?? ??????????? ?????? ???????? ???????????? ????????? ?????? i-?? ???? ? ??????????????????? ? ( l ? 1, L ) ???????????;
6) ? ??? ??????, ???? ??? ?????? ???????? ???????????? ??????? ? ??????????? ? ??????? ???????? ? (s ) ????? ??????? ?? ???????, ?? ???????? ??????? ????????????? ?? 1, ????? ???? ????????? ??????????????? ?????? i-?? ???? ?????????? ?? ???? ??????? ?????
l
? ?????? ??????????????????? ? ( l ? 1, L ), ?????????? ??????? ????????????? ????????
??????? (??????????????? ???????? ??????????? ?? ??? ???, ???? ???????? ??????????? ???
??????????? ??????? ?? ???????? ??????????? ????????? ???????? ?max , ??????????
l
??????? ??????????? ??????????? ?? ??? ???, ???? ? ( s ) ? Omax ).
????? ???????, ??????????? g ??????????? ????????? ??????? ??????? f ?????????????
l
??????????????? ??????????????????? ? , ? ??????? ?????????? ????????? ?????? ???????????????? i-?? ???? ?? (s + g)-? ???? ?????????, ?. ?. ??????????? g ????????????? ??????? ???? g ??????????? ???????????? ??????? ?? ?????? ???????? ???????? ??????????l
?? ??????? ? ( s ) ? ????????????? ????????? g-? ?????? ??????????????????? ? , ? ???????
?? ?????? ???? ????????? ???????????? ?????????? ????????? ?????? ????????????????
i-?? ????.
??? ??????????? ????????? ???????????? ??????????? ?????????? ????????? ??????
Greedy Sheduler ? ???????????? ??????? ????????? ???????????: s ? ????? ???????? ????
l
?????????; i' ? ?????? ???? ??????, ?????????????? ??????? ? ??????????????????? ?
( l ? 1, L ) ???????????? ?? ??????? ???? ?????????; v max ? ?????? ???????? ?????? ( P ) l
( l ? 1, L ), ? i'-?? ?????? ??????? ??????????? ???????? 1, ??????????????? ???????? ???????????????? i'-?? ???? ?????? (?????? ??????? v max ????????????? ?????? ??????????????????? ? ( l ? 1, L ), ??? ??????????? ?????? i'-?? ????, ??????????? ??????????????
l
??????? ? ? ????????????); v ? ?????? ??????? ??????? ( P )l ( l ? 1, L ), ????????????????
l
l
???????? ?????????????? ? ? ?????? ???????????????? i'-?? ???? (?????? ??????? ????l
??? ?????? i?-?? ???? ? ?????????????????? ? ); m? ?????????? ??????, ??????????? ? ??????????????????? ? ( l ? 1, L ) ?? ???????? s-?? ???? ?????????; M s ? ????????? ??????l
l
????????? ??????????????????? ? , ? ??????? ?? ?????? ??????? ???? ?????????
p
s
???????? ????????? ??????? ?????????? ???????? (????????? ??????); N s ? ?????????
??????????? g ????????? ??????? ??????? f ?? s-?? ???? ?????????, ? ??????? ????????????? ?????????? ??????? ? ?f g ( s ) ? 0 ??? ?????????????? ?? ?????? ????????? ??????????
?(s ) ????? ??????? ?( ? g ) ,???????????? ????? ????????? ????????? ?????? i-?? ????
? ??????????????????? ? ( l ? 1, L ), ?????????? ??????????????????? ??? ??????????????
????????? ????????? ?????? ? ??? ????????????? ??????? ??????? ??????????????? ??????????? ? ( s ) ; I? ????????? ????? ??????, ??????? ?????? ???? ?????????? ? ??????? (??l
??? ??????, ??????? ?????? ???? ????????? ? ??????????????????? ? ( l ? 1, L )).
????????????? ?????????? ????????? ????? ??????? ??? ?????????? ???????????? ??????? ?? ???????? ????????? ???????: I ? ?1,2,3,.., n?; m=0; v max = 1, s = 1, ????? ????????
l
???????? ???????????? ??????? ?max . ???????? Greedy Sheduler ??????????? ????????????
?????????????? ?????? i-?? ???? ? ??????????????????? ? ( l ? 1, L ) ???????? ?????????
????.
l
????кблзл?х обзс? рсрз??нблк? рз?зк?брмк? ??рткр?лкх ?н? мсл?бхб?л?? ркрзбо
63
l
1. ?????? ???? ?????? i', ??????????? ? ??????????????????? ? ( l ? 1, L ), ???????????? ????????? ???????: i' ? min?i | i ? I ?; ????? ???? ?????? i ' ????????????? ???????
(??????) ?????? ? ???????? ( P ) l ? ??????? ? ???????? (t 0lji ) , ???????? ? ??????? ????????????? ?????? ????? ????.
2. ??????????? ? ? l ( l ? 1, L ) ?????? i'-?? ???? ??????????? ? ?????? ???? ???????????????????; ??? ????? ? i ' -?? ?????? ??????? v max ( s ) ?????? ( P )l ( l ? 1, L ) ???????? ?????l
???, ??????????????? ???? ?????? (???????? pi ', v max ? 1 ); ???????? ? ????????? P l ( s )
?? s-? ???? ?????????, ????????? ? ?????????????? ????????? v max -? ???????? ?? i ' -?
?????, ??????????? ????????? ???????: pi ',v max ? 1 , pk ,vmax ? 0 , ??? k ? 1, n ? k ? i?.
l
3. ????????????? ????????? M s ??????????????? ??????????????????? ? , ? ???????
?? ??????? s-? ???? ????????? ???????? ????????? ??????? ????????? ?????? ??????????? ????????? ???????: M s ? {1,2,.., L} .
4. ?? ?????? ?????? P l ( s ) ( l ? 1, L ) ??????????? ?????????? ????????? ??????
(t 0jil ( s )) ( l ? 1, L ), ??????? (t 0jil ( s )) ??????????? ? ???????, ??????? ? ???????????? ???????? ??????? l (??? l ? 1, L ).
5. ??? ??????????? ???? ?????? P l ( s ) ? (t 0jil ( s )) ( l ? 1, L ) ???????????? ???????? ???????? f ( s ) ; ?????????????? ????? ??????? ??????? ? ???? ??? ?????? ( P l ( s ) ; (t 0jil ( s )) )
???
l ? 1, L
???????????
???
????????
???????????
(( ( P l ( s )) , (t 0jil ( s )) | l ? 1, L )*=
= ( P l ( s ); (t 0jil ( s )) | l ? 1, L) ;
6. ???????? v ??????? ??????????????? ???????? ?????? ( P l ( s )) ? ????? ??????
(t 0jil ( s )) ????????????? ???????? v max (v ? v max ) ; ??? ?????????? ??????? v max ( s ) =1 (??????????? ? ? l ( l ? 1, L ) ?????? ???????? ? ??? ?????? ???????) ????????? ??????? ??????
? ? l ?? ???????????, ??????????? ??????? ? ???? 13.
7. ???????? ??????? ??????????? ? (s ) ??????? ?(s ) , ? ??????? ????? ??????????? ????? ???????? ??????????? ???????, ???????? ?????? 1.
8. ???????? g ??????? ???? ???????? ?????????????? ??????? ???????????????? 1
( ( s ? g ) ? ????? ?????????????? ???? ?????????, ?????????? ? ???????????? ??????????
???????????? ??????? ?? ?????????????? ?????? i'-?? ???? ? ??????????????????? ? l ,
???????????? ?? ?????? ???????? ???????? ???????????? ?????????? ? * ( s ) (???????
( P l ( s ) ; (t 0jil ( s )) )*).
9. ????????? ? ??????????????????? ? l ( l ? M s ) (??? ?????????? ???? ????????? ???????????????????) ??????? ?????? ????? ???????, ??? ?????? i'-?? ???? ???????????? ??
???? ??????? ? ?????? ? l ( l ? M s ); ?????????? ??????????????????? ? l , ? ??????? ???????????? ?????????? ????????? ?????? i-?? ????, ????????????? ???????? ???????? ??????????? ?( s ) ; ??????????? ???????? ? ????????? ( P l ( s )) ????? ??? pil', v ?1 ( s ? g ) ? 1 ,
pil', v ( s ? g ) ? 0 , pil' ,v ( s ? g ) ? 0 , pkl ', v ?1 ( s ? g ) ? 0 , p kl ' ,v ( s ? g ) ? 1 , ??? k' ? ??????? ?????
? ???????? ( P l ( s )) , ? ??????? ???????? p kl ' ,v ?1 ? (v-1)-? ??????? ????? 1 (?? s -? ???? ????????? ? ??? ?????????? ??????? ??? ??????????????? ??????, ??????? ??? ????????
64
═. B. ═?сзс?
?? ( s ? g ) -? ????); ? ?????????? ??????????? ??????? ( P l ( s ? g )) ( l ? M s ); ?????? v ???????? ???????????????? ???????, ???????????????? ?????????????? ? ? l ??????????????? ??????, ??????????????: v ? v ? 1 .
10. ? ?????????????? ?????? ( P l ) (??? l ? 1, L ) ??????????? ??????? ( t 0jil ) (???
l ? 1, L ) ? ??? ??????? (s+g)-?? ???? ?????????, ? ????? ???????? ???????? f ( s ? g ) (? ????? ??????????? ??????? ( ( P l ( s ? q )) , ( t 0jil ( s ? q )) | l ? 1, L )).
11. ???
?????????
???????
( ( P l ( s )) , (t 0jil ( s )) | l ? 1, L )
?
???????
???????
?
( ( P l ( s ? g )) , ( t 0jil ( s ? g )) | l ? 1, L ) ??????????? ???????? ????? ? g f ( s ) ???? ??????
? ?g f ( s ) ?????????? ?????????? ??????? ??????? f ????????? ??????? [10]:
?
?) ? g f ( s ) ? [ f ( s ? g ) ? f ( s )] ? 0 ,
?
?) ? g f ( s ) ? [ f ( s ? g ) ? f ( s )] ? 0 ;
? ?????????? ??????? g ????? ??????????????????? ? l , ??? ??????? ???????????
? ?g f ( s ) ? 0 ??????????? ? ????????? N sp : N sp ? N sp ? { g } , ? ????? ???????????
?
????????? N s ??? ??????????? g, ??? ??????? ? g f ( s ) ? 0 ; ???? N s ? ? , ?? ?????p
p
?????? ??????? ? ???? 14.
p
12. ? ????????? N s ?????????? ??????????? g ' , ??? ???????? ?????? ??????????????
?
?
g
?????????
? ?g f ( s ) ? 0
??????????: g ' ? max (| ?
g
?
g
f ( s ) | ) ???
f ( s ) ? 0 ; ?????????? ??????? ( ( P l ( s ? g ' )) , (t 0jil ( s ? g ' )) | l ? 1, L ) ???????????????
??? ???????? ???????????, ?? ?????? ???????? ??????????? ??????????? ???????.
13. ?????????? ??????? ( ( P l ( s ? g' )) , ( t 0jil ( s ? g' )) | l ? 1, L ) ??????????? ??? ???????? ???????????: ( ( P l ( s )) , ( t 0jil ( s )) | l ? 1, L )*=( ( P l ( s ? g ' )) , ( t 0jil ( s ? g' )) | l ? 1, L ), ??????????? ???????? ?????? ???? ????????? s ? s ? g ; ??? ?????????? ??????? v ? 1 ??????????? ??????? ? ???? 7; ??? ???????????? ??????? v ? 1 ??????? l ???????????????????
? l ( l ? M s ), ? ??????? ?? ?????? s-? ???? ?????????? ????????? ?????? ???????????????? i'-?? ???? ??????????? ?? ????????? M s : M s ? M s \ {l} , ??? ?????? l ?????????????
?????? ???????????????????, ???????????????? ???????? g (??? g ? ?????? ???? ?????????
???????????? ???????????? ???????? ???????????? ??????? ? ( s ) ), ??? ??????????
??????? M s ? ? ??????????? ??????? ? ???? 7; ??? M s ? ? ??????????? ?????????????????? ? l ( l ? M s ), ? ??????? ????? ???? ??????? ??????? ????????? ??????, ???????????
??????? ? ???? 16.
p
14. ???? N s ? ? , ?? ? ??????? ??????????? ? ???????? O( s ) ???????? ????????????
??????? ( ( P l ( s )) , (t 0jil ( s )) | l ? 1, L )* (??????????
? * ( s ) ) ????? ???????, ???????????
???????? ??????? ???????, ?? ???????, ????? ??????? ???????? ??????? ??????????????
????????? ???????: O ? O ? 1 ? ??????????? ???????????????? ???????? ??????? O( s ) ,
???? O( s ) ? Omax , ?? ??????????? ??????? ? ???? 8;
15. ??? ?????????? ??????? O( s ) ? Omax ? ???????????? ??????????? Omax ????????
???????? ???????????? ??????? ( ( P l ( s )) , ( t 0jil ( s )) | l ? 1, L )* ????? ???????? ???????????
????кблзл?х обзс? рсрз??нблк? рз?зк?брмк? ??рткр?лкх ?н? мсл?бхб?л?? ркрзбо
65
??????? ?? ???????, ??????? ???????? ??????????? ??????? ( ( P l ( s )) , ( t 0jil ( s )) | l ? 1, L )*,
??????????????? ??????? ????????? ?????? ? ??????????? ? ?????? ???????????????????
? l ( l ? 1, L ) ??????? i' -?? ????, ????? ???? ??????????????????? ??? ????????? ??????????? ??????? ??? ??????????????? ????? ??????: 1,2,.., i' ; ??? ?????????? ???????
O( s ) ? Omax ??????????? ??????? ? ???? 16.
16. ??????????? ??????????? ????????? I ????????? ???????: I ? I \ {i ?} , ???? ???
??????????? ? ?????????? ??????????? ????????? I ??????????? ??????? I ? ? , ?? ???l
??? ???? n ????? ????????? ? ??????????????????? ? (l ? 1, L ) ??????????? ???????,
????? ?????? ???? ???????? ??????? ?? ??? 17; ???? I ? ? , ?? ?????? ?? ???? ????? ???l
?????? ? ??????????????????? ? (l ? 1, L ) , ??????????? ??????? ?? ??? 1.
17. ??????? ?????????.
?????? ????????? ????????? Greedy Sheduler ??????????, ??? ?? ????????? ╚??????╩
?????? ? ??????????? ???????????? ??????????? ???????. ??? ??????????? ??????????? ????????????? ???????????? ??????????? ??????? (?????????? ?????????? ???????? ????????? ??????) ???????? ????????? ???????.
???????. ???????? Greedy Sheduler ???????? ?????????? ?????? ?????????? (????????
?????? ??????????) ? ???????????? ???????????? ??????????? ?????????? ?????????
??????.
??????????????: ??????? ??????? ?????? ????????????, ??? ???????, ??????? ????????
???????? ???????????, ????? ???????? ? ??????????? ???????????? ???????. ??? ????
???????????? ??????? ?????????? ?????? ??????????? ???????????? ????? ???????????????? ??????? ????????, ??????? ?????? ??????????? ????????? ???????????? ?? ??????
???????? ???????????? ??????? ??????????.
????????? ??????? (????????? ????????? ??????????????????? ? l (l ? 1, L) , ?????????????? ?????????? ? ??? ?????? ???? i ? 1 ) ????????? ??? z0 . ???????? ??????????????? ??????, ????????? ? ??????????? ? ??????????????????? ? l ( l ? 1, L ) ??????, ????
??????? ??????????? ????????? N 1 ???? N1 ? {2,3,4,.., n} , ????????? ????? z n ?1 . ?????
???????, ?????? z n ?1 ??????? ? ?????????? ? ? l ( l ? 1, L ) ??????, ???? ??????? ??????????? N 1 .
? ???????? ?????? z n ?1 ????? ???? ???????? ????????? z' 1 , ??????? ???????????? ?????????? ? ??????????????????? ?????? ( i ? 2 )-?? ????. ?.?. ? ?????? z' 1 ??????????? ?????? ????? ? ????? ?????? ??????????? ???????????? ?????????????? ?????? ( i ? 2 )-??
???? ? ??????????????????? ? l . ????????? ??????? ?????? z '1 ??? rz' 1 . ? ?????????? ????????? ????????? z '1 ????? ???? ???????????? ????????? z n ? 2 , ????????? ? ???????????
? ? l ( l ? 1, L ) ?????? ?????, ????????????? N 2 ? {3,4,.., n} . ????? ????????? zn ? 2 ????????????? ??? ????????? ?????? N 2 , ??????????? ?? ?????? ????????? N 1 ????? ?????????? ?? N 1 (?? ???????? ?????? z n ?1 ) ?????? ( i ? 2 )-?? ????. ??? ???? ????????? z n ? 2 ,
??????????? ????? ??????? ?????? (? ?????? z' 1 ), ?????????? ???????? ?????? z n ?1 (???
???? N 1 ? N 2 ). ?????????? ? ????????? zn ? 2 ????? ???? ???????? ????????? z' 2 ?????????? ? ? l ( l ? 1, L ) ?????? ( i ? 3 )-?? ????.
????????? ??????? ????????? z' 2 ??? rz' 2 , ????? ??????? rz' 2 ??????????? ? ?????????????? (?? ??????) ??????? rz' 1 ?????? z '1 . ??? ???? ??????? rz' 2 ?????? z' 2 ?? ????????
????????? ??????? ????????? ?????? ????? i ? 1 ? i ? 2 , ??????????? ??? ??????? ??????
66
═. B. ═?сзс?
z' 1 . ????? ???????, ??????? ?????? z n ? 2 ??????????? ?? ?????? ??????? rz'1 ?????? z' 1 ,
??????? ???????? ???????? ??????????? ??? ?????? ????? i ? (1,2) (??????????????
?? ?????? ??????? ??????). ????? ?? ?????? ?????? z n ? 2 (? ?????? ????????? ????????? z' 2 )
????? ???? ???????????? ?????? z n ?3 .
????????? ?? ????????, ???????? ? ??????, ??? ?????????? ? ???????????????????
? (l ? 1, L) ?????? ( n ? 1 )-?? ???? (?????? ????? ??? ????????? ???????? ????????????
l
rz' n ? 2 ?????? z' n ?2 ) ????????? ???????????? (??????????????) ?????????
? z 1 , ??????? ??????? ????????? ??????????? ???????????? ?????????????? ???-
???????
z n ?( n ?1 )
??? n -?? ???? ? ??????????????????? ? l (l ? 1, L) . ????????? z 1 ????? ???? ??????????
? ???????????? ????????? z' n ?1 , ??????? ??????? ??????????? ?? ?????? ??????? rz' n ? 2 ?????? z' n ?2 . ????? ???????, ??????? ?????? ??????????? ?????????? ? ????????? ??????
n ????? ????????????, ???:
1) ?????? ??????????? ????????? ? ????, ????? ????? ?????????? ??????? ?????? ?? ??????????? ???????????? ?????????????? ? ??????????????????? ? l (l ? 1, L) ?????? i-??
???? ?????????? ?????? ?????? ???? ????????? z n ?i ?? ?????????? ? ???????????????????
? l ??????, ???? ??????? ??????????? ????????? N i ? {i ? 1, i ? 2,.., n} ;
2) ??????? ???????? ?????? z n ?1 (? ?????) ???????????????? ? ??????? ????????? z 1
(????????? ? ??????????? ? ? l (l ? 1, L) ?????? n-?? ????), ??????? ?????? ???? ????????
?? ?????? ??????? ????????? z 2 (?????????? ? ? l (l ? 1, L) ?????? (n-1)-?? ????) ? ?. ?.;
? ???? ??????? ??????? ????????? z 1 ??????????? ????? ?????????? ??????? ??????, ?????????? ? ??????????? ?????? n-?? ???? ? ??????????????????? ? l (l ? 1, L ) ;
3) ??????? ????????? zn ? ( i ?1) , ?????????????? ????? ???????????? ??????? ??????
? ?????? ? ?????? z' i ( i ? 1, n ? 2 ), ??????????? ?? ?????? ??????? rz' i ? ?? ????????????
??? ???? ????????? ??????? ????????? ??????, ??????????? ? ??????????????????? ? l ??
?????????? ????? ?????????.
? ????? ?????????? ??????????? ??????? ?????? z n ?1 ?? ?????????? ? ??????????????????? ? l ( l ? 1, L ) ?????? (n?1)-?? ???? ????? ???? ???????? ?? ????????? ???????????
??????? ???????? z '1 , z' 2 ,.., z' n ?1 . ????? ??????? rz' k ????????? z' k ???????? ???????
?????????? ???????? z' 1 , z' 2 ,.., z' k ?1 , ???????????? ??????? ????????? ?????? ??????????????? ????? ? ??????????????????? ? l (l ? 1, L) , ??? ??????? ????????? z' n ?1 ??????????
?????? ????????? z' n ?2 ? ?. ?., ??? ??????? ????????? z' 2 ?????????? ?????? ?????????
z' 1 . ??? ????????? ??????????? ??????? z n ?1 ????? ???? ???????? ????? ??????????? ???????? ??????????? ??????? ???????? z' 1 , z' 2 ,.., z' n ?1 . ??? ??????? ????????? z' k ??????????? ?????????? ???????? z' 1 , z' 2 ,.., z 'k ?1 , ?????????? ??????????? ???????? z' k ?1 , ,..,
z' n ?1 ??? ???? ?? ???????????. ? ??????????????? ??????????? ?????????? ????????
(???????) ??????? ?????? ? ?????????????? ?????????.
??????????? ? ???, ??? ?????????? ??????????? ??????????? ??????? ??????????? ????? ???????, ??? ??? ????? ????????? ??????? ???? ???????? ????????? ??????? ?????
? ??????? ????????? ???????? ??? ??????????? ??????????? ???????.
????? ???????, ?????????? ??????? ??????? ?????? ??? ??????????????? ????????? ???????? ??????????. ?????????? ???????? ??????????? ????????? ??????????? ???????
? ??? ??????????????.
????кблзл?х обзс? рсрз??нблк? рз?зк?брмк? ??рткр?лкх ?н? мсл?бхб?л?? ркрзбо
67
??? ????? ???????? ?????????????? ??????????? ????????????? ??????????????? ??????
(???????????????? ??????? ???? ????????? ????????) ? ???? ???????? [10; 11]. ?????????
?????????? ???? ???????? E , I , ????????? ?? ????????? ????????? E , ??????????? ??????? ?????????? ????????, ? ????????? ??? ??????????? I , ??????????? ?????????? ??????????? ??????????? ????????. ??????? M ? ( E , I ) ???????? ?????????? ?????????? [11]:
1) ????????? I ?? ?????, ???? ???????? ????????? E ???????? ?????? ( E ? ? ), ? ?????
???????? ?? ?????? ???????? ? ? , ?. ?. I ? ? ;
2) ???? B ? I , ? A ? B , ?? A ? I ; ?. ?. ???? ??????????? ????????? B ?????? ? ????????? ??????????? ??????????? I , ? A ???????? ????????????? B , ?? A ????? ??????
? I;
3) ???? A, B ? I ? ??? ???? A ? B , ?? ?????????? ????? ??????? x ????????? B , ???
x ?( B \ A ) ? A ? { x }? I .
????? ???????, ???? ??? ??????????????? ?????? ????? ???????? ????????????????
???????? 1?3 ???????? (?. ?. ?????? (??????, ???????) ???????? ?????????? ?????????? 1?3
????????), ?? ?? ??????? ????? ???? ??????? ? ?????????????? ??????? ?????????.
????????, ??? ????????? A ? B ???????? ????????????, ???? ???? ?? ??? ?? ????????
?????? ???????. ???????????? ??????????? ????????? B ? I ?????????? ????? ????????.
? ????? ???????? ???????????? ?????????????? ???????????? ????????????? ???????
??? ???????? ?????? ?????? ?????????? ?????? ??? L = 2 (??????????????? ??? ??????? ?
???????? ?????????) ? n = 3 (??????????????? ?????? ???? ?????). ??? ?????????? ??????????? ?????????? ?????????? ??? ???????????? ??????? ????: ( i , j1 , j 2 ) , ??? i ? ??? ??? ??????, ??????? ?????????????? ? ???????; j1 ? ??? ??????? ?????? i-?? ???? ? ?????????????????? ? 1 ?? ?????? ???????? ?????????;
j 2 ? ??? ??????? ?????? i-?? ???? ????
? ?????????????????? ? ?? ?????? ???????? ?????????. ????? ??? ?????????? ?????????
2
?? L ????????? ????????? ( L ? 2 ) ?????????:
? ? {(1, j1 , j2 ), (2, j1 , j2 ), (3, j1 , j2 )} .
? ???? ?????? ??? ????????? ?????????? ? ? ? ' , ???????????? ??????? ????????? ?????? ? ??????????? ???????, ????? ????? ??? ? ? {(1, j1 , j2 ), (2, j1 , j2 ), (3, j1 , j2 )} ,
??????
i-?
?????
( i ? 1,3 )
? ' ? {(1, j '1 , j '2 ), (2, j '1 , j '2 ), (3, j '1 , j '2 )} .
??? ??? ????? ???????????? ???????????? ????????? ????????? ???????, ????? ? ? ? ' .
? ?????? ????, ??? ????????????? ???????? ???????????? ??? ????????????? ??? ?????? ???????? ?????? ???????, ????? ?????????? ? ? ? ' (????????? ?????????? ????
{( i , j1 , j 2 ) | i ? 1,3 } ) ???????? ????????????. ????? ???????, ??? ??? ? ? ? ' ? ? ? ? ' ????????? ? (?????????? ? ) ???????? ???????????, ??? ??? ? ' ?? , ?? ????????? ? ' ?????
???????? ???????????. ??????????????, ??? ??????????????? ???????? ?????? ?????????
? ? ? ' ???????? ?????????????, ?. ?. ?????? ???????? M.
????????, ??? ? ?????????? ? ? ? ' ?????????? ????? ?????? ???? ( i , j1 , j 2 ) , ???
(i ' , j1 , j2 ) ? (i ' , j '1 , j '2 ) , ??? i' ? ??? ??????, ??????? ?????????? ??????? ?? ?????? ? ?????? ???????? ? ??????????? ? ? ? ' . ????? ??? ?????????? ??????? ? ? ? ' ??????????,
????? ??? ????????? i-? ????? ?????? ??????????? ??????? ( i , j1 , j 2 ) ? ( i , j'1 , j' 2 ) ???
i ? i' . ????? ??? ??????????? ? 1 ? {(i ' , j1 , j2 ), (i, j1 , j2 ) | i ? i ' } ? ? '1 ? {(i ' , j '1 , j '2 ),
( i , j'1 , j' 2 ) |i ? i' } ??????????? ??????? ? 1 ? ? '1 (??? i, i '? {1,2,3} ? i ? i' ). ????????, ???
??? ???????? ? 2 ? ? ' 2 ???? ? 2 ? {(i, j1 , j2 ) | i ? i ' } ? ? '2 ? {(i, j '1 , j '2 ) | i ? i '} ???????
? 2 ? ? ' 2 ??????????? ?????????????.
68
═. B. ═?сзс?
????? ? 1 ? ? , ??? ???? ????????? ? ? ? ' , ?????????????, ? ???? ????, ??? ? 1 ? ? '1 ,
?????, ??? ? 1 ? ? ' . ?? ???????? ? '1 ? ? ' , ? ???? ????, ??? ? ? ? ' ? ? 1 ? ? '1 , ?????, ???
? '1 ? ? . ????? ???????, ???????????? ? 1 ???????? ??????????? ?? ????????? ? ????????? ? ' , ? ???????????? ? '1 ? ?????????? ?? ????????? ? ????????? ? . ????? ??? ? 1 ? ?
? ? '1 ? ? ' ?????, ??? ? 1 ? I ? ? '1 ? I . ??????????? ??????????? ????? ???? ?????????
??? ??????????? ? 2 ? ? ? ? ' 2 ? ? ' , ????? ? 2 ? I ? ? ' 2 ? I . ?????? ???????? ????????
????????????? ? ??????????????? ?????? ????? ????????? ??????????.
??? ?????????????? ???????? ???????? ????????? ??????????? ????????? ? 1 ? I
? ? 2 ? I ? ???? ? 1 ? {( i , ji 1 , ji 2 ), ( i' , ji' 1 , ji' 2 )} , ? 2 ? {( 1, j11 , j12 ), ( 2 , j 21 , j 22 ), ( 3 , j31 , j32 )} .
? ???????????? ? ???????? 3 ? 1 ? ? 2 (??? ? ? 1 ??????? ????? ?????? i, i? ????? ????????? ???? ?? ???????? 1, 2, 3). ????? ? ????????? ? 2 ????? ???? ???????? ????????????
? 21 , ? 22 , ? 23 ?????????? ???? (????????? 2):
? 21 ? {( 1, j11 , j12 ), ( 2 , j 21 , j 22 )} ,
? 22 ? {( 1, j11 , j12 ), ( 3 , j31 , j32 )} ,
? 23 ? { ( 2 , j 21 , j 22 ), ( 3 , j31 , j32 )} .
? ???? ????, ??? ????????? ? 1 ? ? 2 ??????????, ????? ? 1 ? ? 21 ; ? 1 ? ? 22 ; ? 1 ? ? 23
(????????, ????? ???? ? 1 ? ? 21 , ???? ? 1 ? ? 22 , ???? ? 1 ? ? 23 ??????????, ??? ??? ? 1 ? ? 2
??????????). ??? ??????? ? 1 ? ? 21 ? ? 1 ? ? 22 ?????????? i ? 1 , ????? ???????? ????
ji1 ? j11 ? ji 2 ? j12 , ???? ji 1 ? j11 ? ji 2 ? j12 . ? ???? ?????? ??? i' ? 2 ?????????? ???????? ????????? ????????: ji' 1 ? j 21 ? ji' 2 ? j 22 (??? ji1 ? j11 ? ji 2 ? j12 ) ???? ji' 1 ? j21
? ji' 2 ? j12 (??? ji 1 ? j11 ? ji 2 ? j12 ). ?? ???????? ??? i' ? 3 ????? ji' 1 ? j31 ? ji' 2 ? j32
(??? ji1 ? j11 ? ji 2 ? j12 ) ???? ji' 1 ? j31 ? ji' 2 ? j32 (??? ji 1 ? j11 ? ji 2 ? j12 ).
? ????? ???? ??????????? ??????? ????? ???? ???????????? ????????? ???????:
ji' 1 ? j k 1 ? ji' 2 ? j k 2 (??? ji1 ? j11 ? ji 2 ? j12 ) ???? ji' 1 ? j k 1 ? ji' 2 ? j k 2 (??? ji 1 ? j11
? ji 2 ? j12 ), ??? i' ? k ? 2 ???? i' ? k ? 3 . ??????????? ??????????? ????? ???? ?????????
??? ??????, ????? i ? 2 , ? i' ? 1 ???? i' ? 3 , ? ????? ??? ??????, ????? i ? 3 , ? i' ? 1 ????
i' ? 2 .
???????????? ?????? ?????? ? '1 ??????????? ????? ?????????? ? ????????? ??????? ??-
???????? ???? ? 1 ? {(i, ji1 , ji 2 ), (i ' , ji '1 , ji '2 )} ?????? ?????? ???? ( i' ' , ji'' 1 , ji'' 2 ) (???????, ???
( i' ' , ji'' 1 , ji'' 2 ) ? ? 2 ? ( i' ' , ji'' 1 , ji'' 2 ) ? ? 1 ). ????? ?????????? ? ? 1 ?????? i??-?? ???? (??????
????
( i' ' , ji'' 1 , ji'' 2 ) ) ????????? ???????? ????????? ??????? ?????????? ????
? '1 ? {(i, ji1 , ji 2 ), (i ' , ji '1 , ji '2 ), (i ' ' , ji ''1 , ji ''2 )} , ??? ???? ???????? ???????????? (?????????) ??????? ?????????? ? 1 ? ? '1 ???????? ?? ?????.
??? ??? ? 1 ? ? 2 k (??? k ? 1,3 ), ?? ? 1 ? ? ' 1 , ??? ???? ? 2 k ? ? 2 , ????? ? '1 ? ? 2 (?, ?????????????, ? ' 1 ? ? 2 ), ??????? ?????????????? ????????? ? ' 1 ? ? 2 ???????? ????????????
?, ?????????????, ? ' 1 ? I (?. ?. [? 1 ? {i ' ' , ji ''1 , ji '' 2 }] ? I ), ??? ? ??????????? ????????. ??? ????????, ??? ?????? ???????? ?????????? ???????? ??? ??????????????? ?????? ????????
? ???????? ?????? (??????? ????????) ???????? ?????????.
? ???? ????, ??? ???????????? ??????? ???????? ??? ??????????????? ?????? ????????
??????????, ?????????? ?????????? ??????????? ????????????? ???????????? ???????
???? ?????? ? ?????????????? ??????? ?????????. ??? ????? ????????????? ???????? ? ???????????? ??????? ????????? ??? ????????, ??????????? ? [11]. ? ???????????? ? ???? ???-
????кблзл?х обзс? рсрз??нблк? рз?зк?брмк? ??рткр?лкх ?н? мсл?бхб?л?? ркрзбо
69
????? ? ?????????? ?????? ??????? ?????????, ???????????? ? ??????????? ????????, ?????????? ???????????? ??????????? ???????.
??????? ?????????? ??????????, ???? ?? ????????? E ?????? ??????? ??????? f ?? ?????????? ?? ????????? ????????????? ?????. ??? ???? ??????? f ???????? ??????????
? ???????? ???????????? ???????????????? ?? ??? ???????????? ????????? ?. ??? ???????????? ???????????? ??? ????? ????? ??? ?????????, ?. ?. f ( ? ) ?
n
?f
i ?1
i
, ??? f i ? ???????
????????? ?????????, ????????? ? ??????????? ? ??????????????????? ? l ( l ? 1, L ) ??????
i-?? ????. ? ???? ?????? ???? ????????????? ??????? ? ????? ??? ? (1) ? {(1, j1 , j2 )} , ?? ???
??????????????? ????????? ????????? ???????? L ???????? ??? ????????? ?????? ( i ? 1 )-??
????. ???????? ??????? f ( 1 ) ????????????? ???? ???????? ( 1, j1 , j 2 ) , ??????? ?????????
??? f 1 , ??? ???????? ???????????? ?? ???????????? {(1, j1 , j2 )} . ????? ??? ??????????
? ?????????? ? ?????? ???? ( 2, j1 , j2 ) ? ???????????? ?????? ????????????, ????????? ? ?,
??????? ????????? ??? ????????? ? : ? ( 2) ? {(1, j1 , j2 ), ( 2, j1 , j2 )} . ??? ???? ?????????? ?
? ?????? ?????????? (2, j1 , j2 ) ???????? ? ????????? ???????? ????????, ????????? ????-
?????? ?????? ( i ? 2 )-?? ???? (???, ??????????????? ????? ?????? ??????????, ?????????
??? f 2 ). ? ???? ?????? ???????? f ( 2 ) ? ??? ????? ????? f 1 ? f 2 , ? ???? ???????? ????????-
???? ?? ???????????? ????????? {(1, j1 , j2 ), ( 2, j1 , j2 )} . ??????????? ??????????? ?????
???? ????????? ??? ?????? ?????????? ???? (3, j1 , j2 ) . ???????? f ( 3 ) , ??? ????? ?????
f 1 , f 2 , f 3 , ???????????? ?? ???????????? {(1, j1 , j2 ), (2, j1 , j2 ), (3, j1 , j2 )} .
????? ???????, ????????? ? ???????????? ???????? ????????????? ??????????, ??????????? ??????? ???????????? (????????? ?????????) ???????? ?????????? ??????? ????????, ???????????? ?? ????????. ???????? ?????? ????? ???? ???????????? ????????? (????????????? ????????? ????????) ? ??? ??? ?????????? ?????????? ??????? ???????
(?????????? ??????? ??????? ?????????? ?? ????????), ????? ?????? ???????? ????????????
??????????? ???????????? ??????????? ???????, ? ??????? ????? ???? ??????? ????
??????????? ???????. ????? ??????????????? ????????, ?????????? ?????????? ??????? ?????????, ????? ???????????? ??????????? ???????????? ??????? ???????????????
??????.
??????????? ??????????? ?????????? ????????????? ?????? ?????????? ???????????
??????????, ????????? ??????????? ??? ????????????? ? ????????? ? ??????? ????????. ?????????? ???????????? ??????????????????? ????????? ?????? ? ???? ???????? ????? ???
?????????? ?????????? ????? ?????? (n = 5 ? n = 10) ? ?????????? ????? ??????????????
???????? (????????? ?????????) ???????????? ?? ???. 1?2.
???. 1. ??? ??????????????????? ?????????? ???????? ????????? ?????? ??? n = 5 ? L = 3
70
═. B. ═?сзс?
???. 2. ??? ??????????????????? ?????????? ???????? ????????? ?????? ??? n = 5 ? L = 6
????????????? ????????????? ?????????????? ????????? Greedy Sheduler ????????? ????? ????????? ??????????? ?????????? ?????????? ? ???????????? ????????? ??????? ? ?????????????? ????????????????? ???????. ? ???????? ????? ??? ????????? ??????????? ???????????? ?????? ???????? ??? ???? ???????? [5], ??????????? ????? ? ????????????
????????????? ????????? ??? ?????? ? ??????????? ??????????????????? [12], ????? ?????????? ?????????? ?? ?????? ???????????? ?????????? [13; 14] ? ????? ?????? ???
?????????? ?????????? [12]. ???????????? ????????? ??? ?????? ???????? ? ????????????
?????? ???????? ???????? ??????? ??????? ????????? ????????? ???? ?????? ? ??????????
(? ????????? ???????????? ???? ???????? ????? ????? ??? max (t Lji ) . ??? ??-
1,20
i, j
1,00
????? ????????? ????????? ??????
0,80
0,60
0,40
0,20
0,00
5 ?????
10 ?????
15 ?????
20 ?????
25 ?????
30 ?????
??????? ??? ????? ??????
?????? ????????
?????? ????????
??????????? ?????(???????????)
???????????? ????????
?????
???. 3 ????????? ????????????? ??????? ??????????
?????????? ??? ???????? max(t Lji )
i, j
???? ???????? ???????? [5] ??????? ??
?????????? ???? ???????????????????
????????? ?????? ?? ?????? ? ??????
????????, ? ????? ?? ????????? ? ????????????? ????????. ??????? ? ??????
???? ????????? ????????? ?????????????????? ????????? ?????? ?? ??? ????? ???????????. ? ????? ? ???? ????????? ??????? ?????? ??????????
?????????? ????????? ????????? ?????? ??? ???? ???????? (??? ??????????
?????????? ????? ?????? n) ? ?????????????? ???????, ????????????? ???
??????? ?????? ????????, ? ?????
???????????? ??????, ???????????? ?????????? ? ?????? ??????. ??? ????
? ???????? ???????? ???????????, ???????? ???????? ????? ??????????????,
?????? ???????? ???? max (t Lji ) . ????i, j
??????
??????????
????????????
???????? ?? ????????, ?????????????? ?? ???. 3 (??? ???? ???????????
????????????? ??????? ???????????
???????????. ?????? ??????????? ???????, ??? ??? ????? ?????????? ?????
????кблзл?х обзс? рсрз??нблк? рз?зк?брмк? ??рткр?лкх ?н? мсл?бхб?л?? ркрзбо
71
?????? (5?15 ????? ????????? ??????, ?????????????? ? ???????) ????????????? ??????
???????? ???????????? ?? 3?8 % ????? ??????????? ???????, ??? ?????????? ??????????
????? ????????? ?????? ?? 20?30 ????????????? ?????? ???????? ???????????? ?? 10?
15 % ????? ??????????? ???????, ??? ??????????????? ??????. ????? ????????? ????????? ????????????? ??????? ????????? ? ????????????????? ??????? (???????????? ????????? ? ????? ??????), ??? ???? ??? ??????????? ??????????? ?????????? ???????????
????????, ??????????? ??????? ????????? ????????? ??? ????????? ??????, ??????????
?????????? (4). ?????????? ????????????? ???????????? ????????????? ????????????????? ??????? ? ?????????????? ??????? ????????? ? ????????????? ???????? ????????????
?? ???. 4.
?
?
?
???. 4. ????????? ????????????? ??????? ??????????
?????????? ??? ????????? ????????? ? ?????? ?? ????????: ? ? L = 3; ? ? L = 6; ? ? L = 9
72
═. B. ═?сзс?
?????? ??????????? ???????, ??? ??? ?????? ?????????? ?????????????? ???????? (????,
?????, ?????? ????????? ?????????) ??? ?????? ?????????? ????? ?????? (5?15 ????? ????????? ??????, ?????????????? ? ???????) ????????????? ?????? ???????? ????????????
?? 5?8 % ????? ??????????? ???????, ??? ???? ????????????? ????????? ????? ??????????? ??? ???????? ?????????? ?????????. ??? ?????????? ?????????? ????? ????????? ?????? ?? 20?30, ????????????? ?????? ???????? ???????????? ?? 10?15% ????? ???????????
???????, ??? ??????????????? ????????????????? ??????.
??????????? ?????? ????????????? ??????? ????????? ?????????? ?????????? ? ????????? ? ?????????? ???????? ??????? ??????????? ??? ????????????? ??? ????????? ??????? ? ???????? ?????????? ?????????. ????? ???????, ????????????? ????? ????????? ?????????? ??????????? ??????? ?? ??????? ????????? ?????? ? ??????????? ????????.
??????????
?????????? ???????? ??????????? ?????????? ????????? ????????? ?????? ? ??????????? ????????, ??????? ???????? ????? ???????????, ??? ????????? ????????????????? ?????????. ? ?? ?? ????? ? ??????? ?? ?????? ???????? ? ???????????? ?????? ??????????
?????????? ???? ???????? ????????? ?????????? ??????? ????????? ?????? ??? ????????,
??? 3, ?????????? ????????? ?????????. ?????????? ???????????? ?????? ???? ??????????
?? ?????????? ??????? ? ??????? ???????????? ???????????? ?????????? ????????? ????????? ?????? ? ??????????? ???????, ? ?????? ??????? ??????? ????????????? ?????
???????????? ??????????? ?????????? ????????? ??????. ??? ???? ???????????? ????????
??????????????? ?????????? ???????? ?? ????????????? ????? ??????? ? ???????, ?????????? ??????????????? ??? ??????????????? ????????.
?????? ??????????
1. ???? ?., ???? ?. ???????????? ? ?????????????? ???????????????? ?? ?++. ?.: ???????, 2004. 672 ?.
2. ???????? ?. ?. ?????? ?????????????? ??????????. ?.: ?????????, 2004. 320 ?.
3. ???????? ?. ?., ???????? ??. ?. ???????????? ??????????. ???.: BHV? ?????????,
2002. 599 ?.
4. ???????? ?. ?. ???????????? ?????????????? ???????. ??????????: ???? ???
╚????????? ??????????? ???????????╩, 2008. 133 ?.
5. ??????? ?. ?., ??????? ?. ?. ?????? ??????????. ?????? ? ?????????. ?.: ???, 2011.
222 ?.
6. ??????? ?. ?. ???????? ?. ?., ?????????? ?. ?., ??????? ?. ?. ?????? ??????????. ?????? ?????????? ????????????? ?????????. ?.: ??? ??. ?. ?. ??????????, 2012, 159 ?.
7. ??????? ?. ?., ?????????? ?. ?. ??????????? ?????????? ? ???????????? ??????????
???????????? ?? ????? ??????? ??????? ???????????? ?????????? ???????. ?????. ????
???????????, ?????????????? ??????? ? ??????????. 2012, ?2 (25), ?. 45?52.
8. Pinedo M. L. Sheduling.Theory,Algoritms, and Systems. Springer, 2008. 664 p.
9. ??????? ?. ?. ?????? ? ?????? ???????????? ????????????. ???? ??????. ?????:
???, 2004. 63 ?.
10. ??????? ?. ?. ???????? ? ?????????? ???????????. ?.: ????????? ????, 2003.
224 ?.
11. ?????? ?., ????????? ?., ?????? ?. ?????????. ?????????? ? ??????. ?.: ?????,
2002. 960 ?.
12. ????????? ?. ?., ?????? ?. ?. ????? ?????? ? ?????? ? ?????????????? ???????? ???
??????????? ?????? ?????? ??????????. ?????????????? ?????????????. ???????????
??????????. ?????. ?????????. ??-?? ??. ???????????? ?. ?., 2008, ?3, ?. 147?153.
13. ?????????? ?., ?????????? ?., ?????????? ?. ????????? ????, ???????????? ????????? ? ???????? ???????. ?.: ??????? ?????-???????, 2006. 284 ?.
????кблзл?х обзс? рсрз??нблк? рз?зк?брмк? ??рткр?лкх ?н? мсл?бхб?л?? ркрзбо
73
14. ????????? ?. ?. ???????????? ???????? ??????????? ?????????? ??????? ???????????? ??????? ? GRID. ????????????????? ?????????????? ???????, 2010, ? 4 (26). ?. 115?
126.
???????? ???????? ? ??????????? 16.12.2014
K. V. Krotov
Sevastopol State University
33 Universitetskaya Str., Sevastopol, 299053, Russian Federation
krotov_k1@mail.ru
GRADIENT METHOD OF MAKING A STATIC SCHEDULES FOR CONVEYOR SYSTEMS BASED ON GREEDY STRATEGIES
The model of scheduling data in conveyor systems and method of constructing a static schedule,
which based on greedy strategy, were found in work.
Keywords: multi-stage conveyor system; schedules performance data processing programs; gradient method; greedy algorithm.
References
1. K. Hughes. Parallel and Distributed Programming in C ++/ Hughes T. M .: Publishing House
?Williams?, 2004. 672 p.
2. Toporkov V. V. Models of distributed computing. Moscow FIZMATLIT, 2004, 320 p.
3. Voevodin V. V., Voevodin Vl.V. Parallel computing. SPb, Publishing house ╚BHVPetersburg╩, 2002. 599 p.
4. Sirotina N. Y. Parallel Computing System. Krasnoyarsk University FSEIHPE ╚Siberian
Federal University╩, 2008, 133 p.
5. Lazarev A. A., Gafarov E.R. Scheduling theory. Problems and algorithms. Moscow,
Publishing House of Moscow State University, 2011. 222 p.
6. Lazarev A. A., Musatov E. G., Kvartsheliya A. G., Gafarov E. R. Scheduling theory.
Objectives of traffic management systems. Moscow, Publishing House of Moscow State University,
2012, 159 p.
7. Dolgov O. E., Peresvetov V. V. Scheduling minimizing total tardiness on a single device by
parallel ant colony. / Computer science, computer facilities and management. Bulletin PNU, 2012,
? 2 (25), p. 45-52.
8. Pinedo M. L. Sheduling.Theory,Algoritms, and Systems. Springer, 2008, 664 p.
9. Kovalev M. M. Models and methods of scheduling. Lectures. Minsk, Publishing house BSU,
2004, 63 p.Kovalev M. M. Matroids in discrete optimization. Moscow, Publishing house ╚Editorial
IRDA╩, 2003. 224 p.
11. Kormen T., Leiserson C., Rivest R. Algorithms. Construction and analysis. Moscow,
MTsNMO, 2002, 960 p. 16.
12. M. H. Prilutsky, V. S.Vlasov. Branch and bound method with heuristic estimates for
conveyor scheduling problems. Mathematical modeling. Optimal control. Bulletin of the Nizhny
Novgorod University, 2008, ?3,. p.147-153.
13. Rutkovskaya D, Rutkowski J., Pilinsky M., Rutkovskiy L. M. Neural networks, genetic
algorithms and fuzzy systems. Hotline Telecom, 2006, 284 p.
14. Shapovalov T. S. Genetic algorithm for scheduling run parallel jobs in GRID.
Multiprocessor computer systems, 2010, ?4 (26), p. 115-126.
1 .
?????? ?? ????????? ??????????? ????? (?????????) ??????? ???? ????????? ????????? ??? ????????? ???????? ?????????? ?????? ???????????? ????????? ?? ???????? ? ???????? ?????????? ?????? ? ?????? ??????? ? ? ( l ? 2 , L ), ? ????? ????????? ?? ??????l
????кблзл?х обзс? рсрз??нблк? рз?зк?брмк? ??рткр?лкх ?н? мсл?бхб?л?? ркрзбо
61
?? ? ???????? ?????????? ?????? ? ????????? j-? ??????? (??? ???????, ??? j ? 1 ). ?????
???????? ??? ????????? ??? ???????? ????????????? ??????????? ??????? ?? ???????
?????????? ???????? (??????? ????????? ??????) ? ??????????????????? ? 1 ( l ? 2 , L )
?????????:
L
n
L
n
n
f ? ?? t10,il ? pil,1 ? ??? t 0jil ? pijl ? ( t 0j ?l 1,i ? til ) ? pil, j ?1 .
l ? 2 i ?1
(4)
l ? 2 j ? 2 i ?1
????????? ????? ? ??????? ??????????? ???????? ???????????????? ??????? ? ( s ) ,
? ??????? ??????????? ????? ?????? ???????? ???????????? ???????, ? ????? ?max ? ??????????? ????????? ??????? ??????????? ???????? ???????????????? ???????. ????????
??????? ? ??????????? ??????? ???????????? ?????????? ????
n
n
? ( s ) ? ?? | pi , j ( s ? g ) ? pi , j ( s ) | / 2 ,
i ?1 j ?1
??? g ? ?????? ?????????????? ???? ?????????, ?? ??????? ??????????? ???????????? ?????? ??????? ? ( s ? g ) ?? ???? ???????? ???????????? (?????????) ??????? ? ( s ) . ????????? ???????? ??????? ??????????? ? (s ) ???????? ?????? 1. ??? ?( s ) ? 1 ????????? ?????? ???????????????? i-?? ???? ?????????? ? ????? ?? ??????????????????? ? ( l ? 1, L ),
l
??? ? ( s ) ? 2 ????????? ?????? i-?? ???? ?????????? ? ???? ??????????????????? ?
l
( l ? 1, L ) ? ?. ?.
??????? ???????? ?????????? ?????????? ????????? ????????? ?????? ? ?????????????? ?????? ????????? Greedy Sheduler. ???????? ??????????? ???????????? ????????? ?????????????? ?????? i-?? ???? ? ??????????????????? ? ( l ? 1, L ) Greedy Sheduler ????????????:
l
1) ?????????? ?????? ???????????????? i-?? ???? ? ? ( l ? 1, L ) ????? ?????????? ??
? ????? ?????? ??????????????????;
l
2) ????????? ????????? ?????? i-?? ???? ? ??????????????????? ? ( l ? 1, L ) ?? ????
??????? ????? ? ?????? ??????????????????? ? ??????????? ?? ???????? ???????? ??????l
????? ? (s ) (? ????? ?????????????????? ? ( l ? 1, L ), ? ???? ??????????????????? ? ,
? ???? ??????????????????? ? ?. ?. ? ??????????? ?? ???????? ??????? ??????????? ? (s ) ???????? ???????????????? ???????);
l
3) ????????? ????????? ?????? i-?? ???? ? ??????????????????? ? ????????????? ????????? ???????? ??????? ??????? f, ??? ???? ??????????? ??????????? ????????? ??????? f,
l
???????????? ??? g, ?????????????? ? ???????????????? ??????????????????? ? , ? ???????
l
l
?????????? ????????? ??????????????? ?????? ( l ? 1, L , ??????????????? ?????
?
?f g ? 0 ???? ??????
?
?
?f g (? ( s )) ? 0 ? ????? ?????????? ???????? ??????? ??????? f , ??????????????? ???-
?f g ? 0 ?????????? ????????? ??????? ??????? f [14]), ?. ?.
??????? ? ( s ? g ) , ??????????????? ?? ?????? ????????? ?????????? ? ( s ) , ??? ????????
????????? ?????? i-?? ???? ????????????? ??? ??????? ???????? ??????????? ?? s-? ????;
4) ? ?????? ???? ????????????? ?????????? ??????? ? ?f g ? 0 ????? ??????????? g, ??
????? ???? g, ??? ??????? ??????????? ??? ???????, ?????????? ?? ??????????? g?, ??? ???????? max ( ? ? g f (? ( s )) ? 0 ) ;
g
l
5) ? ??? ??????????????????? ? , ? ??????? ????????? ????????? ?????? i-?? ???? ??????????? ?????????? ??????? max ( ? ? g f (? ( s )) ? 0 ) , ??????? ?????? ??????????? (?. ?.
g
62
═. B. ═?сзс?
??????????????? ??????? ??????????? ??? ???????? ???????????), ????? ???? ????????
?? ??????????? ?????? ???????? ???????????? ????????? ?????? i-?? ???? ? ??????????????????? ? ( l ? 1, L ) ???????????;
6) ? ??? ??????, ???? ??? ?????? ???????? ???????????? ??????? ? ??????????? ? ??????? ???????? ? (s ) ????? ??????? ?? ???????, ?? ???????? ??????? ????????????? ?? 1, ????? ???? ????????? ??????????????? ?????? i-?? ???? ?????????? ?? ???? ??????? ?????
l
? ?????? ??????????????????? ? ( l ? 1, L ), ?????????? ??????? ????????????? ????????
??????? (??????????????? ???????? ??????????? ?? ??? ???, ???? ???????? ??????????? ???
??????????? ??????? ?? ???????? ??????????? ????????? ???????? ?max , ??????????
l
??????? ??????????? ??????????? ?? ??? ???, ???? ? ( s ) ? Omax ).
????? ???????, ??????????? g ??????????? ????????? ??????? ??????? f ?????????????
l
??????????????? ??????????????????? ? , ? ??????? ?????????? ????????? ?????? ???????????????? i-?? ???? ?? (s + g)-? ???? ?????????, ?. ?. ??????????? g ????????????? ??????? ???? g ??????????? ???????????? ??????? ?? ?????? ???????? ???????? ??????????l
?? ??????? ? ( s ) ? ????????????? ????????? g-? ?????? ??????????????????? ? , ? ???????
?? ?????? ???? ????????? ???????????? ?????????? ????????? ?????? ????????????????
i-?? ????.
??? ??????????? ????????? ???????????? ??????????? ?????????? ????????? ??????
Greedy Sheduler ? ???????????? ??????? ????????? ???????????: s ? ????? ???????? ????
l
?????????; i' ? ?????? ???? ??????, ?????????????? ??????? ? ??????????????????? ?
( l ? 1, L ) ???????????? ?? ??????? ???? ?????????; v max ? ?????? ???????? ?????? ( P ) l
( l ? 1, L ), ? i'-?? ?????? ??????? ??????????? ???????? 1, ??????????????? ???????? ???????????????? i'-?? ???? ?????? (?????? ??????? v max ????????????? ?????? ??????????????????? ? ( l ? 1, L ), ??? ??????????? ?????? i'-?? ????, ??????????? ??????????????
l
??????? ? ? ????????????); v ? ?????? ??????? ??????? ( P )l ( l ? 1, L ), ????????????????
l
l
???????? ?????????????? ? ? ?????? ???????????????? i'-?? ???? (?????? ??????? ????l
??? ?????? i?-?? ???? ? ?????????????????? ? ); m? ?????????? ??????, ??????????? ? ??????????????????? ? ( l ? 1, L ) ?? ???????? s-?? ???? ?????????; M s ? ????????? ??????l
l
????????? ??????????????????? ? , ? ??????? ?? ?????? ??????? ???? ?????????
p
s
???????? ????????? ??????? ?????????? ???????? (????????? ??????); N s ? ?????????
??????????? g ????????? ??????? ??????? f ?? s-?? ???? ?????????, ? ??????? ????????????? ?????????? ??????? ? ?f g ( s ) ? 0 ??? ?????????????? ?? ?????? ????????? ??????????
?(s ) ????? ??????? ?( ? g ) ,???????????? ????? ????????? ????????? ?????? i-?? ????
? ??????????????????? ? ( l ? 1, L ), ?????????? ??????????????????? ??? ??????????????
????????? ????????? ?????? ? ??? ????????????? ??????? ??????? ??????????????? ??????????? ? ( s ) ; I? ????????? ????? ??????, ??????? ?????? ???? ?????????? ? ??????? (??l
??? ??????, ??????? ?????? ???? ????????? ? ??????????????????? ? ( l ? 1, L )).
????????????? ?????????? ????????? ????? ??????? ??? ?????????? ???????????? ??????? ?? ???????? ????????? ???????: I ? ?1,2,3,.., n?; m=0; v max = 1, s = 1, ????? ????????
l
???????? ???????????? ??????? ?max . ???????? Greedy Sheduler ??????????? ????????????
?????????????? ?????? i-?? ???? ? ??????????????????? ? ( l ? 1, L ) ???????? ?????????
????.
l
????кблзл?х обзс? рсрз??нблк? рз?зк?брмк? ??рткр?лкх ?н? мсл?бхб?л?? ркрзбо
63
l
1. ?????? ???? ?????? i', ??????????? ? ??????????????????? ? ( l ? 1, L ), ???????????? ????????? ???????: i' ? min?i | i ? I ?; ????? ???? ?????? i ' ????????????? ???????
(??????) ?????? ? ???????? ( P ) l ? ??????? ? ???????? (t 0lji ) , ???????? ? ??????? ????????????? ?????? ????? ????.
2. ??????????? ? ? l ( l ? 1, L ) ?????? i'-?? ???? ??????????? ? ?????? ???? ???????????????????; ??? ????? ? i ' -?? ?????? ??????? v max ( s ) ?????? ( P )l ( l ? 1, L ) ???????? ?????l
???, ??????????????? ???? ?????? (???????? pi ', v max ? 1 ); ???????? ? ????????? P l ( s )
?? s-? ???? ?????????, ????????? ? ?????????????? ????????? v max -? ???????? ?? i ' -?
?????, ??????????? ????????? ???????: pi ',v max ? 1 , pk ,vmax ? 0 , ??? k ? 1, n ? k ? i?.
l
3. ????????????? ????????? M s ??????????????? ??????????????????? ? , ? ???????
?? ??????? s-? ???? ????????? ???????? ????????? ??????? ????????? ?????? ??????????? ????????? ???????: M s ? {1,2,.., L} .
4. ?? ?????? ?????? P l ( s ) ( l ? 1, L ) ??????????? ?????????? ????????? ??????
(t 0jil ( s )) ( l ? 1, L ), ??????? (t 0jil ( s )) ??????????? ? ???????, ??????? ? ???????????? ???????? ??????? l (??? l ? 1, L ).
5. ??? ??????????? ???? ?????? P l ( s ) ? (t 0jil ( s )) ( l ? 1, L ) ???????????? ???????? ???????? f ( s ) ; ?????????????? ????? ??????? ??????? ? ???? ??? ?????? ( P l ( s ) ; (t 0jil ( s )) )
???
l ? 1, L
???????????
???
????????
???????????
(( ( P l ( s )) , (t 0jil ( s )) | l ? 1, L )*=
= ( P l ( s ); (t 0jil ( s )) | l ? 1, L) ;
6. ???????? v ??????? ??????????????? ???????? ?????? ( P l ( s )) ? ????? ??????
(t 0jil ( s )) ????????????? ???????? v max (v ? v max ) ; ??? ?????????? ??????? v max ( s ) =1 (??????????? ? ? l ( l ? 1, L ) ?????? ???????? ? ??? ?????? ???????) ????????? ??????? ??????
? ? l ?? ???????????, ??????????? ??????? ? ???? 13.
7. ???????? ??????? ??????????? ? (s ) ??????? ?(s ) , ? ??????? ????? ??????????? ????? ???????? ??????????? ???????, ???????? ?????? 1.
8. ???????? g ??????? ???? ???????? ?????????????? ??????? ???????????????? 1
( ( s ? g ) ? ????? ?????????????? ???? ?????????, ?????????? ? ???????????? ??????????
???????????? ??????? ?? ?????????????? ?????? i'-?? ???? ? ??????????????????? ? l ,
???????????? ?? ?????? ???????? ???????? ???????????? ?????????? ? * ( s ) (???????
( P l ( s ) ; (t 0jil ( s )) )*).
9. ????????? ? ??????????????????? ? l ( l ? M s ) (??? ?????????? ???? ????????? ???????????????????) ??????? ?????? ????? ???????, ??? ?????? i'-?? ???? ???????????? ??
???? ??????? ? ?????? ? l ( l ? M s ); ?????????? ??????????????????? ? l , ? ??????? ???????????? ?????????? ????????? ?????? i-?? ????, ????????????? ???????? ???????? ??????????? ?( s ) ; ??????????? ???????? ? ????????? ( P l ( s )) ????? ??? pil', v ?1 ( s ? g ) ? 1 ,
pil', v ( s ? g ) ? 0 , pil' ,v ( s ? g ) ? 0 , pkl ', v ?1 ( s ? g ) ? 0 , p kl ' ,v ( s ? g ) ? 1 , ??? k' ? ??????? ?????
? ???????? ( P l ( s )) , ? ??????? ???????? p kl ' ,v ?1 ? (v-1)-? ??????? ????? 1 (?? s -? ???? ????????? ? ??? ?????????? ??????? ??? ??????????????? ??????, ??????? ??? ????????
64
═. B. ═?сзс?
?? ( s ? g ) -? ????); ? ?????????? ??????????? ??????? ( P l ( s ? g )) ( l ? M s ); ?????? v ???????? ???????????????? ???????, ???????????????? ?????????????? ? ? l ??????????????? ??????, ??????????????: v ? v ? 1 .
10. ? ?????????????? ?????? ( P l ) (??? l ? 1, L ) ??????????? ??????? ( t 0jil ) (???
l ? 1, L ) ? ??? ??????? (s+g)-?? ???? ?????????, ? ????? ???????? ???????? f ( s ? g ) (? ????? ??????????? ??????? ( ( P l ( s ? q )) , ( t 0jil ( s ? q )) | l ? 1, L )).
11. ???
?????????
???????
( ( P l ( s )) , (t 0jil ( s )) | l ? 1, L )
?
???????
???????
?
( ( P l ( s ? g )) , ( t 0jil ( s ? g )) | l ? 1, L ) ??????????? ???????? ????? ? g f ( s ) ???? ??????
? ?g f ( s ) ?????????? ?????????? ??????? ??????? f ????????? ??????? [10]:
?
?) ? g f ( s ) ? [ f ( s ? g ) ? f ( s )] ? 0 ,
?
?) ? g f ( s ) ? [ f ( s ? g ) ? f ( s )] ? 0 ;
? ?????????? ??????? g ????? ??????????????????? ? l , ??? ??????? ???????????
? ?g f ( s ) ? 0 ??????????? ? ????????? N sp : N sp ? N sp ? { g } , ? ????? ???????????
?
????????? N s ??? ??????????? g, ??? ??????? ? g f ( s ) ? 0 ; ???? N s ? ? , ?? ?????p
p
?????? ??????? ? ???? 14.
p
12. ? ????????? N s ?????????? ??????????? g ' , ??? ???????? ?????? ??????????????
?
?
g
?????????
? ?g f ( s ) ? 0
??????????: g ' ? max (| ?
g
?
g
f ( s ) | ) ???
f ( s ) ? 0 ; ?????????? ??????? ( ( P l ( s ? g ' )) , (t 0jil ( s ? g ' )) | l ? 1, L ) ???????????????
??? ???????? ???????????, ?? ?????? ???????? ??????????? ??????????? ???????.
13. ?????????? ??????? ( ( P l ( s ? g' )) , ( t 0jil ( s ? g' )) | l ? 1, L ) ??????????? ??? ???????? ???????????: ( ( P l ( s )) , ( t 0jil ( s )) | l ? 1, L )*=( ( P l ( s ? g ' )) , ( t 0jil ( s ? g' )) | l ? 1, L ), ??????????? ???????? ?????? ???? ????????? s ? s ? g ; ??? ?????????? ??????? v ? 1 ??????????? ??????? ? ???? 7; ??? ???????????? ??????? v ? 1 ??????? l ???????????????????
? l ( l ? M s ), ? ??????? ?? ?????? s-? ???? ?????????? ????????? ?????? ???????????????? i'-?? ???? ??????????? ?? ????????? M s : M s ? M s \ {l} , ??? ?????? l ?????????????
?????? ???????????????????, ???????????????? ???????? g (??? g ? ?????? ???? ?????????
???????????? ???????????? ???????? ???????????? ??????? ? ( s ) ), ??? ??????????
??????? M s ? ? ??????????? ??????? ? ???? 7; ??? M s ? ? ??????????? ?????????????????? ? l ( l ? M s ), ? ??????? ????? ???? ??????? ??????? ????????? ??????, ???????????
??????? ? ???? 16.
p
14. ???? N s ? ? , ?? ? ??????? ??????????? ? ???????? O( s ) ???????? ????????????
??????? ( ( P l ( s )) , (t 0jil ( s )) | l ? 1, L )* (??????????
? * ( s ) ) ????? ???????, ???????????
???????? ??????? ???????, ?? ???????, ????? ??????? ???????? ??????? ??????????????
????????? ???????: O ? O ? 1 ? ??????????? ???????????????? ???????? ??????? O( s ) ,
???? O( s ) ? Omax , ?? ??????????? ??????? ? ???? 8;
15. ??? ?????????? ??????? O( s ) ? Omax ? ???????????? ??????????? Omax ????????
???????? ???????????? ??????? ( ( P l ( s )) , ( t 0jil ( s )) | l ? 1, L )* ????? ???????? ???????????
????кблзл?х обзс? рсрз??нблк? рз?зк?брмк? ??рткр?лкх ?н? мсл?бхб?л?? ркрзбо
65
??????? ?? ???????, ??????? ???????? ??????????? ??????? ( ( P l ( s )) , ( t 0jil ( s )) | l ? 1, L )*,
??????????????? ??????? ????????? ?????? ? ??????????? ? ?????? ???????????????????
? l ( l ? 1, L ) ??????? i' -?? ????, ????? ???? ??????????????????? ??? ????????? ??????????? ??????? ??? ??????????????? ????? ??????: 1,2,.., i' ; ??? ?????????? ???????
O( s ) ? Omax ??????????? ??????? ? ???? 16.
16. ??????????? ??????????? ????????? I ????????? ???????: I ? I \ {i ?} , ???? ???
??????????? ? ?????????? ??????????? ????????? I ??????????? ??????? I ? ? , ?? ???l
??? ???? n ????? ????????? ? ??????????????????? ? (l ? 1, L ) ??????????? ???????,
????? ?????? ???? ???????? ??????? ?? ??? 17; ???? I ? ? , ?? ?????? ?? ???? ????? ???l
?????? ? ??????????????????? ? (l ? 1, L ) , ??????????? ??????? ?? ??? 1.
17. ??????? ?????????.
?????? ????????? ????????? Greedy Sheduler ??????????, ??? ?? ????????? ╚??????╩
?????? ? ??????????? ???????????? ??????????? ???????. ??? ??????????? ??????????? ????????????? ???????????? ??????????? ??????? (?????????? ?????????? ???????? ????????? ??????) ???????? ????????? ???????.
???????. ???????? Greedy Sheduler ???????? ?????????? ?????? ?????????? (????????
?????? ??????????) ? ???????????? ???????????? ??????????? ?????????? ?????????
??????.
??????????????: ??????? ??????? ?????? ????????????, ??? ???????, ??????? ????????
???????? ???????????, ????? ???????? ? ??????????? ???????????? ???????. ??? ????
???????????? ??????? ?????????? ?????? ??????????? ???????????? ????? ???????????????? ??????? ????????, ??????? ?????? ??????????? ????????? ???????????? ?? ??????
???????? ???????????? ??????? ??????????.
????????? ??????? (????????? ????????? ??????????????????? ? l (l ? 1, L) , ?????????????? ?????????? ? ??? ?????? ???? i ? 1 ) ????????? ??? z0 . ???????? ??????????????? ??????, ????????? ? ??????????? ? ??????????????????? ? l ( l ? 1, L ) ??????, ????
??????? ??????????? ????????? N 1 ???? N1 ? {2,3,4,.., n} , ????????? ????? z n ?1 . ?????
???????, ?????? z n ?1 ??????? ? ?????????? ? ? l ( l ? 1, L ) ??????, ???? ??????? ??????????? N 1 .
? ???????? ?????? z n ?1 ????? ???? ???????? ????????? z' 1 , ??????? ???????????? ?????????? ? ??????????????????? ?????? ( i ? 2 )-?? ????. ?.?. ? ?????? z' 1 ??????????? ?????? ????? ? ????? ?????? ??????????? ???????????? ?????????????? ?????? ( i ? 2 )-??
???? ? ??????????????????? ? l . ????????? ??????? ?????? z '1 ??? rz' 1 . ? ?????????? ????????? ????????? z '1 ????? ???? ???????????? ????????? z n ? 2 , ????????? ? ???????????
? ? l ( l ? 1, L ) ?????? ?????, ????????????? N 2 ? {3,4,.., n} . ????? ????????? zn ? 2 ????????????? ??? ????????? ?????? N 2 , ??????????? ?? ?????? ????????? N 1 ????? ?????????? ?? N 1 (?? ???????? ?????? z n ?1 ) ?????? ( i ? 2 )-?? ????. ??? ???? ????????? z n ? 2 ,
??????????? ????? ??????? ?????? (? ?????? z' 1 ), ?????????? ???????? ?????? z n ?1 (???
???? N 1 ? N 2 ). ?????????? ? ????????? zn ? 2 ????? ???? ???????? ????????? z' 2 ?????????? ? ? l ( l ? 1, L ) ?????? ( i ? 3 )-?? ????.
????????? ??????? ????????? z' 2 ??? rz' 2 , ????? ??????? rz' 2 ??????????? ? ?????????????? (?? ??????) ??????? rz' 1 ?????? z '1 . ??? ???? ??????? rz' 2 ?????? z' 2 ?? ????????
????????? ??????? ????????? ?????? ????? i ? 1 ? i ? 2 , ??????????
1/--страниц
Пожаловаться на содержимое документа