Желілік графикті құру. Критикалық жолды анықтау. Уақыт резерві

• аяқталушы оқиғадан бөлек тұғырықты оқиғалар болмауы керек;

• цикл болмауы керек.

 

 

Тапсырманы  шешу алгоритмі:

1. модельді немесе желілік графикті тұрғызу;
2. желілік графикті реттеу;

Желілік графикті реттеу дегеніміз,  жоғарыдағы ережелермен  тұрғызу керек дегенді білдіреді.

3. Жобаның сызықты диаграммасын тұрғызу;

Сызықты диаграмманы  тұрғызғанда әрбір жұмыс уақыттың параллель осінде сызықтармен бейнеленеді, оның ұзындығы сол жұмыстың ұзақтығына тең болады. Ұзақтығы нөлге тең жалған жұмыстар болған жағдайда ол нүктелермен белгіленеді. Жобаның сызықты диаграммасынан кризистік уақытты, кризистік жолды, сонымен қатар барлық жұмыстың уақыт резервін анықтауға болады. 

4. кризистік жолды таңдаймыз;

   Кризистік жолды анықтау үшін – жұмыс-кесінділерді қарастырамыз.

5. кризистік жолға жататын параметрлерді (жұмысты) талдаймыз;
6. қалған басқа жұмыстарды талдаймыз;
7. уақытша параметрлерді есептейміз;

  Эксперттің және жобаның жауапты орындаушыларын сұрау негізіндегі жұмысқа арналған үлестірудің сандық мінездемесін анықтау үшін үш уақытша бағаны анықтайды:

1. оптимисттік бағаны, яғни қолайлы жағдайлардағы жұмыс ұзақтығы;
2. пессимисттік бағаны, яғни қолайсыз жағдайлардағы жұмыс ұзақтығы;

    с) өте ықтимал бағаны, яғни қалыпты жағдайлардағы жұмыс ұзақтығы;

8. уақытша бағаның сандық мінездемесін анықтау (есептеу);
9. жобаны орындау мерзімі нұсқаушы мерзімінен асып түспейтіндігінің ықтималдық бағасы.

Бізге берілген жобаны құрастырғанда 12 оқиға ерекшеленді  деп ойлайық:  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  10,  11  және  24  олардың жұмыстарын байланыстыратын:  (0, 1),  (0, 2),  (0, 3),  (1, 2),  (1, 4),  (1, 5),   (2, 3),  (2, 5),  (2,7), (3, 6), (3, 7),  (3, 10),  (4, 8),  (5, 8),   (5, 7),  (6, 10),  (7, 6),  (7, 8),  (7, 9),  (7, 10),  (8, 9),  (9, 11),  (10, 9), (10, 11). Желілік график құрап, оны реттеу керек.

 

Желілік графикті тұрғызу.

Жұмыстардың тізімінен  көргендей,  желілік графиктің бастапқы оқиғасы 0 оқиға болып табылады  (себебі оның алдында ешқандай оқиға жоқ),   ал қорытындылаушы – оқиға 11  (себебі онан соң ешқандай оқиға жоқ).   Желілік графикаға байланысты   уақыт өзгерісі солдан оңға қарай,  0 оқиғаны графиктің сол жақ бөлігіне орналастырайық,сол арқылы аралық оқиғаларды сәйкес нөмірлеріне байланысты олардың арасына орналастыру арқылы   11 оқиғаны – оң жақ бөлікке орналастырамыз.(сурет. 1). Оқиғаларды жұмыс тізіміне сәйкес жұмыс-бағыттармен байланыстырамыз.

 

Сурет. 1

 

 

Тұрғызылған желілік график құрастыру ережесін қанағаттандырады. Дегенмен, бұл график толығымен реттелмеген.

Желілік графикті реттеу.Мұнда оқиғалар мен жұмыстар келесідей орналасу керек: яғни реттелген желілік графикте барлық жұмыс-бағыттар  солдан оңға қарай бағытталған: кіші нөмірлі оқиғадан үлкен нөмерлі оқиғаға қарай.

Шартты түрде  желілік графикті бірнеше тік  қабаттарға бөлеміз (оларды бөлшек сызықтармен айналдырып, рим цифрларымен белгілейміз).

І қабатқа  бастапқы оқиға 0 ді орналастырып (сурет 2), ойымызша бұл оқиғаны және онан шығатын барлық жұмыс-бағыттарды графиктан сызып тастаймыз (1 суретті қараңыз) Сонда ешқандай кіріс бағыты жоқ ІІ қабатты құрайтын 1 оқиға қалады. Ойша 1 оқиғаны және онан шығатын жұмыстарды сызып тастасақ, ІІІ қабатты құрайтын 4 және 2 оқиғалар ешқандай кіріс бағытсыз қалады. Осы көрсетілген сызу процедурасын жалғастыру арқылы, 5 және 3 оқиғалы IV қабат, 7 оқиғалы V қабатты, 8 және 6 шы оқиғалы VI қабатты, 10 оқиғалы VII қабатты, 9 оқиғалы VIII қабатты, және соңғы 11 оқиғалы IX қабатты аламыз.

 

Сурет. 2

 

Енді көретініміздей, оқиғалардың бастапқы нөмірленуі дұрыс  емес: яғни, 6 оқиға VI қабатта орналасқанымен, алдыңғы қабатта орналасқан 7 оқиғадан кіші нөмірге ие. Сол сияқты 9 және 10 оқиғалар жөнінде де осылай айтуға болады.

Оқиғалар  нөмірін графикте (2 суретті қараңыз) орналасқанына сәйкес өзгертейік, сол  арқылы реттелген желілік графикті аламыз (сурет 3).

Бір вертикал қабатта орналасқан оқиғалар нөмірінің  ретінің аса маңызы жоқ.

 

 

 

Сурет. 3

Желілік графиктің  ең маңызды түсінігінің бірі –  жол түсінігі. Жол  –  кез-келген жұмыстар тізбегі, мұнда әрбір жұмыстың соңғы оқиғасы келесі жұмыстың бастапқы оқиғасымен сәйкес келеді.  Желілік графиктің әртүрлі жолдарының арасында көбіне қарастырылатын толық жол L   –   бастапқысы желінің ағымдағы оқиғасымен, ал соңғысы – аяқталушы оқиғамен сәйкес келеді. 

Желілік графикадағы  өте ұзақ жол кризистік деп  аталады. Сонымен қатар бұл жолда  орналасқан жұмыстар мен оқиғалар да кризистік деп аталады.

Мысалыға, біз  қарастырған желілік графикада (сурет 3 қараңыз) толық жол болып төмендегілер саналады:

• Жол 0 –– 1 –– 2 –– 7 –– 10 –– 11 ұзақтығы 8 + 9 + 3 + 5 + 13 = 38 тәулік;
• Жол 0 –– 1 –– 3 –– 4 –– 6 –– 10 –– 11  ұзақтығы 8 + 4 + 10 + 3 + 5 + 13 = 43 тәулік;
• Жол 0 –– 5 –– 8 –– 9 –– 11 ұзақтығы 9 + 10 + 4 + 17 = 40 тәулік;
• Жол 0 –– 3 –– 5 –– 6 –– 9 –– 10  –– 11 ұзақтығы 13 + 7 + 9 + 12 + 6 + 13 = 60 тәулік және т.с.с.

 

Бұл жерден көретінімдей, соңғы жолдың ұзақтығы басқалардан көп     (жоғарыда көрсетілген 4 толық жолдың ішінде ғана емес, сонымен қатар барлық толық жолдың ішінде),  сондықтан да ол кризистік деп аталады. Кризистік жолдың ұзақтығы 60 тәулікті құрайды, яғни жұмыс кешенін өткізу үшін 60 тәулік қажет болады. Бұл жұмыс жиынтығын жылдам бітіру мүмкін емес, себебі соңғы оқиғаға жету үшін кризистік жолды міндетті түрде өту керек.

Шынымен де, 11 оқиғаға жету үшін (10, 11) жұмыстарын орындау қажет, яғни 10 оқиғаны бітіру керек; 10 оқиғаға  жету үшін (9,10) жұмыстарды бітіру керек, яғни 9 оқиғаны аяқтау керек; 9 оқиғаға жету үшін (6,9) жұмыстарды орындау қажет, яғни 6 оқиғаны бітіру қажет және т.с.с.

Кризистік жолды  анықтау арқылы, біз желідегі кризистік  оқиғаларды орнаттық 0,  3,  5,  6,  9,  10  және 11  және кризистік жұмыстар (0, 3),  (3, 5),  (5, 6),  (6, 9),  (9, 10),  (10, 11).

ЖБЖ (Жоспарлау  мен Басқару Жүйесі) – де кризистік  жолдың маңызы зор. Себебі бұл жолдың жұмыстары желілік график көмегімен  жоспарланатын барлық жұмыс жиынтығының  жалпы аяқталу циклын анықтайды. Және жобаның уақытын қысқарту үшін ең алдымен кризистік жолда жатқан жұмыс уақытын қысқарту керек. 

Сызықты диаграмманы  тұрғызу.

Айта кететін  жайт желілік графиктің классикалық  түрі – уақыт масштабынсыз сызылған желі. Сондықтан,желілік график жұмыстың орындалу реті жөнінде дәл нақты көрініс берсе де, әрбір дәл уақыт мезетінде орындалуы тиіс кейбір жұмыстарды анықтау үшін жеткіліксіз. Осыған байланысты желілік графикті реттегеннен кейінгі жобаны жобаның сызықты диаграммасымен толықтыру ұсынылады. Біз қарастырып отырған желідегі мұндай сызықты диаграмма төменде суретте көрсетілген.

 

Сурет. 4

 

Сызықты диаграмма  құрастырғанда әрбір жұмыс, ұзындығы жұмыс уақытына тең, уақыттың осіне  параллель кесінделермен бейнеленед. Нөлдік ұзақтықтағы жалған жұмыстар болған жағдайда(қарастырылып отырған желіде ол жоқ) ол нүктемен бейнеленеді. i  және  j оқиғасы, (i,  j) жұмысының басы мен соңы  сәйкесінше кесіндінің басы мен соңына орналастырады.

Жобаның сызықты  диаграммасынан кризистік уақытты, кризистік жолды, сонымен қатар барлық жұмыстың уақыт резервін анықтауға болады.

Кризистік жолды таңдау.

Сонымен, жұмыс  жиынтығының кризистік уақтыты  диаграмманың барлық кесіндісінің оң жақ соңындағы уақыт осінің координатасына тең. 

 

t кр  =  t (11) = 60 (тәулік).

 

Кризистік жолды  анықтау үшін соңғы оқиғасы желідегі аяқталу оқиғасымен сәйкес келетін  жұмыс – кесінділерді қарастырамыз(біздің мысалда (9, 11)  және  (10, 11)).   Содан  соң оң жақ соңы,  алдында қарастырылған (10, 11) кесіндісінің сол жақ соңымен  t (10)  бір кесіндіде жататын (9,10) кесіндісін табамыз.  Қалған кризистік жолдың жұмыстар-кесінділерін де осылай анықтаймыз: (6, 9),  … , (0, 3).

 

1 ші кестеде  желілік графиктің негізгі уақытша  параметрлері көрсетілген. 

 

Параметрмен мінезделетін желі элементі	Параметр  атауы	Параметрдің шартты белгіленуі
Оқиға i	Оқиғаның  орындалуын ерте мерзiмі Оқиғаның  орындалуын кеш мерзiмі Оқиғаның уақыт  резервi	tр (i) tп (i) R (i)
Жұмыс (i‚ ‏‏j)	Жұмыстың  ұзақтығы Жұмыстың  басталуының ерте мерзімі Жұмыстың  аяқталуының ерте мерзімі  Жұмыстың  басталуының кеш мерзімі  Жұмыстың  аяқталуының кеш мерзімі  Жұмыс уақытының  толық резерві Бiрiншi түрдегі  жұмыстың дербес уақыт резервi Екінші түрдегі  жұмыстың дербес уақыт резервi Немесе  жұмыстың еркiн уақыт резервi Жұмыстың  тәуелсіз уақыт резервi	t (i, j) tрн (i, j) tро (i, j) tпн (i, j) tпо (i, j) Rп (i, j) R1 (i, j)   Rс (i, j)       Rн (i, j)
Жол L	Жолдың ұзақтығы Кризистік жолдың ұзақтығы Жолдың уақыт  резерві	t (L) tкр R (L)

Кесте 1

 

Көрcетiлген параметрлердiң мазмұнын және есептеуiн қарап шығамыз.

Кризистік жолға  жататын параметрлерді талдау.

Оқиға параметрлерінен бастаймыз. Жоғарыдай айтылғандай, оқиға барлық жұмыстар аяқталмайынша басталуы мүмкін емес. Сондықтан i – ші оқиғаның орындалуының ерте мерзімі tр (i) осы оқиғаға қатысты жолдың максималды ұзақтығымен анықталады: 

tр (i) = max t (Lпi),   (1)

 

бұл жерде   Lпi  - і – ші оқиғаға қатысты кез келген жол, яғни  бастапқыдан желінің і-ші оқиғасына дейінгі жол.

Егер j оқиғасы бірнеше келетін жолдан тұрса, сәйкесінше бірнеше і оқиға келсе, онда j оқиғасының орындалуының ерте мерзiмін төмендегідей формуламен тапқан ыңғайлы

tр (j) = max [tр (i) + t (i, j)].   (2)

 

і-ші оқиғаның орындалуының кеш мерзімі tп(i) төмендегі  формулаға тең

tп (i) = tкр – max t(Lci),   (3)

 

бұл жерде  Lci – і-ші оқиғаға ілескен кез келген жол,яғни желідегі і-ші ден қорытындылаушы оқиғаға дейінгі жол.

Егер де j оқиғасының өзінен кейін бірнеше  кезек жолдары  болса, яғни бірнеше тізбектелген j оқиғалардан тұрса, онда і оқиғаның орындалуының кеш мерзімін төмендегідей формуламен тапқан ыңғайлы: 

tп (i) = min [tп(j) – t (i, j)].   (4)

 

і – ші оқиғаның уақыт резерві R(i) оның орындалуының кеш және ерте мерзімдерінің айырмашылығы ретінде анықталады:

 

R(i) = tп (i) – tр (i).   (5)

 

Оқиғаның  уақыт резерві - жұмыс жиынтығының  орындалу мерзімін ұзартпай , қандай мүмкін болатын уақыт аралығында бұл оқиғаның пайда болуын тоқтатуға мүмкін болатынын көрсетеді. 

Кризистік оқиғалар уақыт резервін қажет етпейди, себебі кризистік жолда орналасқан оқиғаның орындалуындағы кез келген тоқтау, қорытындылаушы оқиғаның орындалуында да сондай тоқтауды туғызады. 

Мұнан шығатыны, кризистік жолдың топологиясы мен  ұзындығын анықтау үшін, желілік  графиктің барлық толық жолын  таңдап және олардың ұзындығын анықтау  міндетті емес. 

Желідегі  қорытындылаушы оқиғаның пайда болуының ерте мерзімін анықтау арқылы, кризистік жолдың ұзындығын анықтаймыз, сонымен қатар нөлдік уақыт резервіндегі оқиғаларды анықтау арқылы оның топологиясын анықтаймыз.

Егер желілік  графикте жалғыз ғана кризистік жол  болса, онда ол жол барлық кризистік  оқиғалардан өтеді, яғни нөлдік уақыт резервіндегі оқиға. Егер кризистік жолдар бірнешеу болатын болса, онда оларды кризистік оқиғалар көмегімен анықтау қиынға соғады, себебі кризистік оқиғалардың бір бөлігінен кризистік те кризистік емес те жолдар өтуі мүмкін. Бұл жағдайда кризистік жолдарды анықтау үшін кризистік жұмыстарды қолдану ұсынылады.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2  Арнайы  бөлім

2.1 Есептің экономикалық  және математикалық қойылымы

Есетің экономикалық қойылымы:  Төменде көрсетілген кестеде жұмыс жасауға кеткен күндедің ұзақтығы, жұмыс түрі және мазмұны көрсетілген. Осы есепте желілік графикті құру, критикалық жолды анықтау және уақыт резервін анықтау керек.

Тұтынушыларға тауарды  ұсыну

Желілік графикті құру. Критиалық  жолды анықтау. Уақыт резерві кестесін табу керек.

Жұмыс	Жұмыс мазмұны	Күндердің ұзақтығы
(1,2)	Тауарды таңдау	3
(2,3)	Жіберуге дайындық	2
(2,4)	Выписка накладых	2
(3,5)	Түсірілген жүктің көлемін  анықтау	1
(4,5)	Бағаларды анықтау	1
(4,6)	Есеп беруді безендіру	2
(5,6)	Таксировка	2
(5,8)	Автокөлік тапсырысы	2
(6,7)	Шотты банкқа және тұтынушыға жіберу	3
(6,9)	Тауарды шот бойынша  тексеру	3
(7,10)	Счетты төлеу	20
(8,9)	Тауарды жүктеу	1
(9,10)	Тауарды тасымалдау	15
(10,11)	Жүкті шығару және құжатпен тексеру	3