Ўзбекистон алоқа ва ахборотлаштириш агентлиги тошкент ахборот технологиялари университети самарқанд филиали

ЎЗБЕКИСТОН АЛОҚА ВА АХБОРОТЛАШТИРИШ АГЕНТЛИГИ
ТОШКЕНТ АХБОРОТ ТЕХНОЛОГИЯЛАРИ УНИВЕРСИТЕТИ
САМАРҚАНД ФИЛИАЛИ
Ахборот ва педагогика технологиялари факультети

Умумкасфий фанлар кафедраси

Тизимли тахлил асослари фанидан
ЛАБОРАТОРИЯ -4


Мавзу: Жадваллар назарияси масаласи. Джонсон алгоритми
Бажарди:
Текширди:
Самарқанд - 2012 й


РЕЖА:

1. 
   Бир машина учун жадвал тузиш масаласи. Масалани ечиш алгоритми.
   
2. 
   Кетма-кет хизмат килувчи бир неча машиналар учун жадвал тузиш масаласи.
   
3. 
   Икки машина учун жадвал тузиш масаласини ечиш алгоритми (Джонсон алгоритми).
   

1. Бир машина учун жадвал тузиш масаласи. Жадваллар назариясида осон хал килинадиган, амалий жихатдан мухим булган бир катор масалалар мавжуд. Бир машина учун жадвал тузиш масаласи бунга мисол була олади. Шундай масаланинг «машина – операция» терминида куйилишини караб чикамиз.
Фараз килайлик, бир машинада бажарилиши учун бир вактда
операциялар берилган булсин. Хар бир операцияни машинада бажариш вакти хам берилган. Машинада операцияларни бажариш жадвалини тузиш масаласи деганда операцияларни бажаришнинг шундай тартибини аниклашни тушунамизки, бунда кандайдир самарадорлик критерияси оптимал киймат кабул килсин.
Бундай масалани хал килиш алгоритми самарадорлик критериясига бођлик булади.
Куйидаги критерияни караймиз:
, бунда – операцияни бажариш учун кутишга кетган вакт бирлигига бођлик булган жарима микдори (ёки операцияни бажариш учун керакли булган маблађ киймати),
– операциянинг кечикиши ,
,
– операцияни тугатиш вакти, – операцияни тугатиш учун керакли булган директив вакт.
Купчилик масалаларда га минимал киймат берадиган жадвал тузиш талаб килинади.