Њзбекистон республикаси олий ва њрта махсус

Тarmoqli rejalashtirish masalasining algoritmi

Bajariladigan ishlar oddiy bo„lsa, yuqorida ko„rib o„tgan grafik usuli yordamida rejalashtiriladi. Agarda bajariladigan kompleks ishlar murakkab bo„lsa (ayrim hollarda ishlar soni va mantiqiy aloqalar mingdan va undan ortiq bo„lishi mumkin), albatta EHM yordamida hal qilinishi uchun ishlarning aniq ketma-ketligi yoki algoritmi tuzib olinadi.
Тarmoqli grafikning algoritmini tuzish uchun quyidagi 1-jadvaldan foydalanamiz.
1-jadval
Тarmoq grafigini tuzish uchun ma‟lumotlar

№	ai ish	Qaysi ishga asoslanib bajariladi	ti vaqt
1	a1	-	t1
2	a2	-	t 2
3	a3	-	t 3
4	a4	a1, a2	t 4
5	a5	a1, a3, a4	t 5
6	a6	a2, a3	t 6
7	a7	a4	t 7
8	a8	a4, a5	t 8
9	a9	a4, a5, a6	t 9
10	^a10	a6, a7, a8, a9	^t10

Bu jadvalda bajariladigan ishlar va bu ishlar qaysi ishlarga asoslanib bajarilishi hamda har bir ish uchun ketadigan vaqt aniq ko„rsatilgan.
1-jadvaldagi bajariladigan ishlar va ular orasidagi aloqalarning matematik formulasini yozib olamiz. Buning uchun belgilashlar kiritamiz.

a_i ish bajarilishining minimal boshlanish vaqtini  _i
bilan, ishning minimal

tugash vaqtini esa T_i
bilan belgilab olamiz. Har qanday ishning minimal tugash vaqti
T_i  _i  t_i

formula bilan aniqlanadi. Bu yerda, t_i
bo„yicha aniqlanadi.

• 
  a_i
  

ishning bajarilishi uchun ketgan vaqt

Mana shu ifoda yordamida hamma kompleks ishlarda bo„ladigan mantiqiy

aloqalarni formulalar bilan ifodalaymiz. Aytaylik, a_i
ish
a _j ,
a_l , a_k
ishlarga asoslanib

bajarilsin. U holda a_i
yozamiz:
ish faqat
a _j ,
a_l , a_k
bajariladi. Bu aloqani quyidagi ko„rinishda

  maxT , T , T .
i j l k

Bu formulani har bir ish uchun ketma-ket ravishda tatbiq qilib, barcha ishlarning minimal tamom bo„lish vaqtini T  aniqlaymiz.

1. 
   jadvaldagi ishlar uchun  _i
   

va T_i
larni hisoblaymiz.

Birinchi, ikkinchi va uchinchi, ya‟ni
a₁ ,
a₂ , a₃
ishlar uchun:

₁  0
 ₂  0
T₁  t₁ ,
T₂  t₂ ,
.

a₄ ish esa
a₁ , a₂
ishlarga asoslanib bajarilganligi uchun  ₄
 ₄  maxT₁, T₂.
ni aniqlaymiz.

a₄ ishning tugash vaqti
a₅ ish uchun


a₆ ish uchun


a₇ ish uchun
T₄   ₄  t₄ .


₅  maxT₁, T₃ , T₄  T₅  ₅  t₅ .


₆  maxT₂ , T₃
T₆  ₆  t₆ .

 ₇  maxT₄  T₄

T₇  ₇  t₇ .

a₈
a₉
^a10
ish uchun

ish uchun

ish uchun

₈  maxT₄ , T₅ 
T₈  ₈  t₈ .


₉  maxT₄ , T₅ , T₆  T₉  ₉  t₉ .


₁₀  maxT₆ , T₇ , T₈ , T₉ 
^T10 ^{ }10 ^{ t}10 ^.

Shunday qilib, har bir ishning boshlanish  _i 
aniqladik.
va tugash T_i 
vaqtlarini

Butun kompleks ishlarning tugash vaqti hamma ishlarni tugash vaqtlarining maksimumiga teng bo„ladi:
T  maxT₁, T₂ , T₃ , T₄ , T₅ , T₆ , T₇ , T₈ , T₉ , T₁₀.

Kritik ish (kritik yo„l)  _i
va T_i
lar aniqlanib bo„lgandan keyingina aniqlanadi.

Kritik ish bitta bo„lmasdan, bir necha bo„lishi mumkin.

Yuqorida aytib o„tilgan algoritmni quyidagi konkret masala uchun tatbiq qilamiz.
Masala. Quyidagi jadvalda har bir ish uchun aniq vaqt ajratilgan.

№	ai ish	Qaysi ishga asoslanib bajariladi	ti vaqt
1	a1	-	10
2	a2	-	9
3	a3	-	15
4	a4	a1, a2	17
5	a5	a1, a3, a4	16
6	a6	a2, a3	22
7	a7	a4	19
8	a8	a4, a5	21
9	a9	a4, a5, a6	25
10	^a10	a6, a7, a8, a9	31

Jadvaldagi aniqlaymiz, ya‟ni:
a₁ ,
a₂ ,...,
^a10
ishlar uchun
₁,  ₂ ,..., ₁₀
va T₁ , T₂ ,..., T₁₀
larni

T₁ 10; T₂  9; T₃ 15 ;
₁  0;  ₂  0; ₃  0 ;
 ₄  maxT₁, T₂  max10, 910 ;
T₄   ₄  t₄ 10 17  27 ;

₅  maxT₁, T₃ , T₄  max10, 15,
T₅  ₅  t₅  27 16  43 ;
27 27 ;

 ₆  maxT₂ , T₃  max9, 1515;
T₆   ₆  t₆ 15  22  37 ;
 ₇  maxT₄ , T₄  27 ;
T₇   ₇  t₇  27 19  46 ;
₈  maxT₄ , T₅  max27, 43 43 ;

T₈  ₈  t₈  43  21  64 ;
₉  maxT₄ , T₅ , T₆  max27,


43, 37 43 ;

T₉  ₉  t₉  43  25  78 ;
₁₀  maxT₆ , T₇ , T₈ , T₉  max37,
T₁₀  ₁₀  t₁₀  78  31 109 .
46, 64,


78 78 ;

Kompleks ishlarni bajarish uchun maksimal vaqt T₁₀  109
T  maxT₁, T₂ , T₃ , T₄ , T₅ , T₆ , T₇ , T₈ , T₉ , T₁₀
ga teng, ya‟ni

 max10, 9, 15, 27, 43, 37, 46, 64, 78, 109109 .
Endi kritik ishni topamiz. T₁₀ maksimum qiymatga ega. Bunda
^a10
ish kritik ish

bo„ladi.
^a10
ish
a₉ ,
a₇ ,
a₈ , a₉
ishlarga asoslanib bajarilganligi uchun a₉
kritik ish

bo„ladi. Keyingi formulalarga o„tsak,
T₄ ,
T₅ , T₆
lar orasida eng kattasi T₅
bo„lganligi

uchun a₅ ish kritik bo„ladi. Keyingi formulalarga qarab kritik ishlarni aniqlaymiz.

Ko„rib chiqqan misolimizda
a₁ ,
a₃ ,
a₄ ,
a₅ ,
a₉ ,
^a10
lar kritik ish bo„ladi.

Umuman olganda, tarmoqli grafik modeliga asoslanib dasturlar tuzish asosida murakkab vazifalarni kompyuterlar yordamida yechish katta samara beradi.

Тayanch iboralar

Тarmoqli model, ish hodisa, soxta ish, ochiq va berk kontur, sikl, yo„l, kritik yo„l, optimistik baholash, pessimistik baholash, kutish vaqti, ishning boshlanish va tugash vaqti, kritik ish.

Тakrorlash uchun savollar

1. 
   Тarmoqli modellardan foydalanish sohalarini yoritib bering.
   
2. 
   Тarmoqli modellarni tuzish nimaga asoslangan?
   
3. 
   Тarmoqli modelning asosini nima tashkil etadi?
   
4. 
   Soxta ish deb nimaga aytiladi?
   
5. 
   Тarmoqli modellarda berk kontur nima uchun ishlatiladi?
   
6. 
   Тarmoqli modellarda sikl deb nimaga aytiladi?
   
7. 
   Тarmoqli modellarning asosiy afzalliklarini tushuntirib bering.
   
8. 
   Тarmoqli grafikda yo„l deb nimaga aytiladi?
   
9. 
   Тarmoqli grafikda kritik yo„l deb nimaga aytiladi?
   
10. 
    Тarmoqli grafikda «optimistik va pessimistik baholash» deb nimaga aytiladi?
    
11. 
    Тarmoqli grafikka oid hisob ishlarini davom ettirishda kutish vaqtini aniqlash formulasini tushuntirib bering.
    
12. 
    Kritik ish nechta bo„lishi mumkin?
    

11. BOB