11-маъруза воšÅа ва операциянинг ваšт резервлари ќамда критик алгоритмлар. ЭЌтимолли тармоšлар

11-МАЪРУЗА


ВОŠÅА ВА ОПЕРАЦИЯНИНГ ВАŠТ РЕЗЕРВЛАРИ ЌАМДА КРИТИК АЛГОРИТМЛАР. ЭЌТИМОЛЛИ ТАРМОŠЛАР


РЕЖА:

1. 
   Воšеанинг резерв интервали.
   
2. 
   Операциянинг ваšт резервлари.
   
3. 
   Резерв интервали ва ваšт резервлари учун ќисоблаш формулалари.
   
4. 
   Критик йœлни аниšлаш учун Беллман-Калаба усули.
   
5. 
   Эќтимолли тармоšларда ваšт параметрларини ќисоблаш.
   

Таянч иборалар: Воšеанинг кутилаётган ваšти, чегаравий ваšт, резерв интервали, бœш резерв ваšти, тœла резерв ваšти, богланмаган резерв ваšти, критик йœл, критик ваšт, операциялар комплексининг тœла бажарилиш ваšти, Беллман-Калаба усули, эќтимолли тармоšлар, бета-таксимот, операциялар бажарилиши œрта ваšти ва дисперсияси, операциялар комплексини бажарилишининг фактик ва режалаштирилган муддатлари.


1. Воšеанинг резерв интервали. Операциянинг ваšт резервлари. Биз œтган маърузада операциялар комплекси тармоš моделининг муќим элементи бœлган тармоš учлари – воšеаларнинг кутилаётган содир бœлиш ваšтларини šандай аниšлашни šœриб чиšдик ќамда критик йœл, критик ваšт каби мухим тушунчалар билан танишдик. Тармоšдаги критик йœл эса критик операциялар ва воšеалар šатори билан аниšланади. Маълумки критик операцияларнинг бажарилишининг бошлаш ваšтини кечиктириб бœлмайди. Критик бœлмаган операцияларда эса (операциялар комплексининг тœлиš бажарилиш муддатига таъсир этилмаган ќолда) уларнинг бошланиш ваšтини маълум чегарада кечиктириш мумкин. Шунинг учун ќар бир нокритик воšеанинг содир бœлиш чегаравий ваšтини аниšлаш муќимдир.
Шу маšсадда (i) – нокритик воšеани šараймиз. У албатта оралиš воšеадан иборат бœлади. (i) – нокритик воšеадан тугалловчи (n) – воšеагача бœлган ваšт буйича энг узун йœлга сарфланадиган ваšт (i) ва (n) – воšеалар орасидаги барча воšеалар содир бœлиши учун зарур минимал ваšтдан иборат бœлади. Ана шу минимал ваšтни тугалловчи воšеанинг содир бœлиш ваšти t_n дан айириб (i) – воšеа учун содир бœлиш чегаравий ваšти ни ќосил šиламиз.
Шундай šилиб, ќар бир (i) – нокритик воšеа учун ваšт бœйича иккита характеристикага эга бœламиз:
а) t_i – воšеанинг кутилаётган содир бœлиш ваšти;
б) – воšеанинг содир бœлиши учун чегаравий ваšт (воšеанинг содир бœлиши дан кечиктирилса, у операциялар комплекси бажарилиши муддатининг кечикишига олиб келади).
Критик воšеалар учун худди шунга œхшаш чегаравий ваšт аниšланса, у кутилаётган ваšт билан устма-уст тушади. Шунинг учун критик операцияларнинг бажарилишида ваšт бœйича кечиктириш бœлиши мумкин эмас.
[t_i, ] ваšт оралиђига воšеанинг эркинлик интервали ёки резерв интервали дейилади. Резерв интервалига тегишли ваšт моментида воšеанинг содир бœлиши барча ишларнинг тœлик бажарилиш ваšтини œзгартирмайди.
Бу янги тушунчани яхширок англаб олиш учун 1-расмда кœрсатилган тармоš графигини мисол сифатида šàраймиз.
Дастлаб (7)-воšеани šàраймиз. Бу воšеа кейинги (11)-воšеадан 4 ваšт бирлигига фарš šилади, яъни Р_7,11 операция (11)-воšеадан 4 ваšт бирлиги олдин бошланади. (7), (11), (10), (12) воšеалар кетма-кетлиги (7) ва (12) воšеаларни туташтирувчи ваšт бœйича энг узун йœлни ташкил этади. Бу йœл учун ваšт сарфи 4+6+13=23 га тенг. Демак = t₁₂-23=61-23=38, яъни (7) воšеа [37,38] интервалда содир бœлиши мумкин. Худди шунга œхшаш (9) – воšеадан (12)-воšеагача бœлган энг узун йœл =(9)- (10)-(12) ваšти 5+13=18га тенг. Шунинг учун =t₁₂-18=61-18=43. (6)-воšеадан (12)-воšеагача энг узун йœл =(6)-(8)-(11)-(10)-(12) бœлиб, унинг учун сарфланган ваšт 3+13+6+13=35. Шунинг учун =t₁₂ –35=61-35=26. Шу тарзда давом этиб =40, =9 чегаравий ваšтларни аниšлаймиз.
Топилган ваšтларни t_i ваšтлар ёнида šавс ичига ёзиб šœямиз. Шундай šилиб ќар бир (i)-воšеанинг содир бœлиш ваšти šуйида келтирилган интервалларда бœлади (критик воšеалар учун бу интерваллар аниš ваšт мометига айланади):

1. 
   : 0 (7) :
   
2. 
   : [8,9] (8) : 29
   
3. 
   : 13 (9) : [33,43]
   
4. 
   : 20 (10): 48
   
5. 
   : [17,40] (11): 42
   
6. 
   : [23,26] (12): 61
   

Худди шунга œхшаш ќар бир P_ij операция учун (j)-воšеанинг содир бœлиш муддатини бузмаган ќолда уни šанчага кечиктириш мумкинлигини билиш šизиšарлидир. Бу эса P_ij операциянинг бошланиш ваšтини кечиктиришнинг мумкин бœлган šиймати бœлиб, у P_ij операциянинг бœш ваšт резерви деб аталади ва M_ij деб белгиланади.