Изчисляване и анализ на мрежови графики. Ранна дата на събитието

Основни параметри на мрежовата диаграма

Основните параметри на мрежовата диаграма са:

критична пътека

Резерви от време за завършване на събитията

Резерви от време за изпълнение на работата

Пътека - поредица от задания, в които крайното събитие на едно задание съвпада с началното събитие на друго.

Пълен път - път, чието начало е първоначалното събитие, а краят е крайното.

Продължителността, дължината на пътя, е равна на сумата от продължителностите на работата. Неговите съставни части.

критична пътека - пълен път. най-дългият от всички пътища на мрежовата диаграма от първоначалното събитие (I) до последното (C).

Дължината на критичния път определя общата продължителност на целия комплекс от работи. Критичният път ви позволява да намерите времето на крайното събитие.

Пълните пътища могат да излизат извън критичния или частично да съвпадат с него. Тези по-кратки пътувания се наричат отпуснат.Характеристиките им са. Че имат времеви резерви. Критичният път не е такъв. За всяко i-то събитие се определя:

tpi– ранно начало- минимално възможното време на възникване на това събитие за дадена продължителност на работа.

t p i– късна дата на пристигане- максималното време на настъпване на това събитие, в което все още е възможно да се извършат всички следващи работи, при спазване на установения краен срок за настъпване на събитието.

R i – застой за събитие- периодът от време, за който настъпването на това събитие може да бъде отложено, без да се нарушава периодът на развитие на планирания комплекс като цяло. Определя се като разликата между късно ( t p i) и рано ( t p i) времето на завършване на това събитие.

Резервите на събитие на критичния път са равни на нула, тъй като на него t p i = t p i

За всяка работа тидж) се определя:

ранна начална дата (t w.d. ij)- минимално възможното време за започване на тази работа.

ранна крайна дата (t p.o. ij)- минималният възможен срок за изпълнение на тази работа, за определена продължителност на работа

късна начална дата (t b.s. ij)- максималната от допустимите дати за започване на тази работа

късна крайна дата (t p.o. ij)- максимумът от допустимите срокове за завършване на тази работа, при които все още е възможно да се извършат следните работи в съответствие с установения краен срок за настъпване на крайното събитие.

Очевидно ранната начална дата на дейността съвпада с ранната дата на началото на нейното първоначално събитие, а ранната крайна дата я надвишава с продължителността на дейността:

т р.н. ij = t p i

t r.o. ij = t p i + t ij

Късната крайна дата на дейността е същата като късната дата на нейното крайно събитие, а късната начална дата на дейността е по-малка от продължителността на дейността:

t p.o. ij = t p j

t a.s. ij = t p j – t ij

Пълно резервно време за завършване на работата Rnij– максималният период от време, за който можете да отложите началото или да увеличите продължителността на работата, без да променяте зададената дата за настъпване на крайното събитие.

Свободно време за работа, който е част от пълния резерв - максималният период от време, с който можете да забавите началото или да увеличите продължителността на работа, като същевременно не променяте ранните начални дати за следваща работа.

Задачите, които се намират на критичния път, нямат резерви, тъй като всички резерви се създават поради разликата в продължителността на критичния и разглеждания път.

Относителен показател, характеризиращ резерва от време за извършване на работа, е техния коефициент на опън,което е равно на съотношението на продължителността на сегментите от пътя между едни и същи събития, освен това един сегмент е част от пътя с максимална продължителност от всички пътища, преминаващи през тази работа, а другият сегмент е част от критичния път.

3.Изчисляване на мрежови модели

Мрежовите параметри за мрежови диаграми се изчисляват с помощта на графичен и табличен метод, а за сложни - с математически метод.

Графично методът на изчисление се извършва директно върху графиката и се използва в случаите, когато броят на събитията е малък. За да направите това, всеки кръг е разделен на 4 сектора.

Горният сектор е резервът от време за настъпване на събитието R i

ляв сектор - ранна дата на събитието tpi

десен сектор - късната дата на събитието t p i

отдолу - номер на събитието

Метод за изчисляване на параметрите

1) Ранно време на събитията . Ранната дата на завършване на първоначалното (първо или нулево) събитие се приема за равна на нула. Ранните дати за завършване на всички други събития се определят в стриктна последователност чрез нарастващ брой събития. За да се определи датата на ранно завършване на всяко събитие j, се вземат предвид всички работни места, включени в това събитие, като за всяка работа датата на ранно завършване на крайното събитие се определя като сбор от датата на ранно завършване на първоначалното събитие на работата и продължителност на тази работа Тидж,от получените стойности се избира максималното време за ранно завършване на j-то събитие

t pj = (t pi +t ij) max и се записва на графиката (левия сектор на събитието)

2) Късни дати за събития . Късната дата на завършване на последното събитие се приема за равна на ранната му дата. Изчисляването на късните дати за завършване на всички други събития се извършва в обратен ред, според низходящите номера на събитията. За да се определи късният срок за завършване на предишното събитие i, се вземат предвид всички произведения, произтичащи от i-то събитие. За всяка работа се изчислява късният срок за изпълнение на първоначалното събитие t p i ,като разликата между късната дата на завършване на последното събитие на тази работа t p jи продължителността на тази работа тидж.От получената стойност изберете минималното време за късно завършване на i-тото събитие: t p i = (t p j - t ij)minи се записва в десния сектор.

3) Критична дължина на пътя е равно на ранната дата на крайното събитие.

4) Времеви резерви за събитието . Когато определяте резервите от време за събития, трябва да извадите от числото, записано в десния сектор на това събитие, числото, записано в левия сектор, и да го поставите в горния сектор.

5) Когато определяте общото резервно време за работа, извадете от числото, записано в десния сектор на крайното събитие, числото, записано в левия сектор на първоначалното събитие, и продължителността на самата работа.

6) Когато определяте свободния резерв за работа, извадете от числото, записано в левия сектор на крайното събитие, числото, записано в левия сектор на първоначалното събитие, и продължителността на самата работа.

Първоначални данни:

Табличен метод

Кодовете на длъжностите в таблицата са изписани във възходящ индекс аз

Колони 2 и 3 се попълват със спомагателни данни: кодове на предишни и следващи работи. Тези данни ще са необходими за изчисления. Ако работите са първоначални, т.е. няма предишни работи, или окончателни, т.е. няма последващи работи, тогава в съответните колони се поставят тирета. Може да има няколко предишни и следващи задачи според броя на векторите, завършващи или започващи в дадено събитие./

Колона 4 съдържа стойностите на продължителността на работа.

Колона 5 започва изчислените данни. Изчислението се извършва в две преминавания през редовете на таблицата. Първият преминава през редовете отгоре надолу, в които се изчисляват най-ранните работни дати, а вторият преминава през редовете отдолу нагоре, в които се изчисляват късните работни дати.

Ранното начало на дейности, които нямат предишни (в колона 2 - тире), може да се приеме за 0, ако не е посочена друга стойност. Предсрочното завършване на работата се определя по формулата t r.o. ij = t pH ij + t ij и се вписва в колона 6.

Ранното начало на почивката може да се дефинира като, ако например се разглежда работа 2.5, която има начално събитие 2, тогава нейното ранно начално време е равно на ранното крайно време на работа 12, тъй като има край събитие от 2. Стойността от колона 6 се пренаписва в колона 5 Кодовете на предишни работи са посочени в колона 2. Предсрочното завършване също се определя по формулата t r.o. ij = t pH ij + t ij

Ако в колона 2 е посочено, че определена работа е предшествана от повече от една работа (работа 5.6 се предшества от работи 2.5 и 3.5), тогава е необходимо да изберете стойността на ранния старт от няколко опции за стойност (9 - до края на работа 2 ,5 или 13 - до края на работа 3.5). Правилото за избор съответства на формулата t p .n. ij = (t pi + t ij) макс , тоест избрана е максималната стойност (в примера - 16). Ранните окончания са дефинирани както по-горе.

Максималната стойност на ранния край в колона 6 съответства на стойността на продължителността на критичния път (16).

Второто преминаване по редовете на таблицата от работата, записана в последния ред, до работата, записана в първия ред, ви позволява да определите стойностите на показателите за късна ефективност. За задания, които нямат последващи задания (в колона 3 - тире, в примера на работа 46, 5,6), стойността на критичния път се записва в колоната за късно завършване (8). За тези работни места стойността на късното стартиране се изчислява по формулата t a.s. ij t от ij - t ij

Късното завършване на почивката може да се определи като, ако например се разглежда работа 3.5, която има крайно събитие 5, тогава нейното късно крайно време е равно на късното начално време на работа 5.6, тъй като има край събитие от 5. Стойността от колона 7 се пренаписва в колона 8. Кодовете на последващи работи са посочени в колона 3. Късното начало също се определя по формулата t a.s. ij t от ij - t ij .

Ако в колона 3 е посочено, че повече от едно задание следва определено задание (задание 0.1 е последвано от задания 1.2 и 1.3), тогава е необходимо да изберете стойността на късния завършек от няколко опции (3 - според начален час на работа 1 ,3 или 7 - според начален час 1,2), се избира минималната стойност (в примера - 3). Късният старт се определя както по-горе по формулата t a.s. ij t от ij - t ij .

Стойността на общата хлабина (колона 9) се изчислява по формулата

R nij = t от ij - t pH ij - t ij.

Стойността на свободното провисване (колона 10) се изчислява по формулата

R с ij = t ро ij - t рр ij - t ij

Всяка поредица от мрежови дейности, в която крайното събитие на всяка дейност съвпада с началното събитие на дейността, следваща я, се нарича през.

Извиква се мрежов път, където началната точка е същата като началното събитие, а крайната точка е крайното събитие пълен.

Пътят от първоначалното събитие до всяко предприето предшествантова събитие. Извиква се пътят, който предхожда събитието и има най-голяма дължина максимален предишен. Означава се с L 1 (i), а продължителността му е t.

Извиква се пътят, свързващ дадено събитие с последното последващиначин. Този най-дълъг път се нарича доколкото е възможно последващои се означава с L 2 (i), а продължителността му е t.

Пълният път с най-голяма дължина се нарича критичен. Извикват се пътища, различни от критичния път отпуснат. Имат резерви от време.

Дейностите по критичния път са подчертани с дебели или двойни линии. Продължителността на критичния път се счита за основен параметър на графиката.

Помислете за алгоритъм за определяне на критичния път на мрежова диаграма, използвайки алгоритъма на метода на динамично програмиране.

Нека сортираме върховете на графа по рангове и да ги номерираме от края към началото. Това ще направи възможно съпоставянето на ранговите числа с етапите на движение назад при намиране на условно оптимални контроли на последния, последните два и т.н. етапи. Намирането на критичния път ще бъде анализирано с помощта на примера на мрежовата диаграма, показана на фиг. 10.7.

Според принципа на оптималност на Белман, оптималното управление на всеки етап се определя от целта на управлението и състоянието в началото на етапа. Състоянието на системата са събитията, които се намират в редиците. За завършване на последното събитие X 16 е необходимо да завършите предишните събития. Възможни състояния на системата в началото на последния етап на работа - настъпване на събития X 14 и X 15. В кръговете в точките X 14 и X 15 поставяме максималната продължителност на работа на последния етап: X 14 5 , X 15 7 . Нека намерим максималната продължителност на работа на последните два етапа. Състоянието на системата в началото на предпоследния етап се дължи на събитието X 13. Максималната продължителност на пътя, водещ от X 13 до X 16 е .

Следователно числото 14 трябва да бъде поставено в кръга близо до събитието X 13 и т.н. Извършвайки етапите от края към началото, намираме дължината на критичния път t cr =96. За да намерим самия критичен път, нека преминем през процеса на изчисление от първоначалното събитие X 1 до крайното X 16 . Получихме числото 96 на първия етап (от самото начало), като добавихме 16 към числото 80. Следователно критичният път на този етап ще бъде равен на (X 1, X 3). Числото 80 = 16 + 64. Следователно критичният път във втория етап минава през работата (X 3 , X 4) и т.н. На графиката е отбелязано с удебелена линия:

X 1 - X 3 - X 4 - X 7 - X 8 - X 10 - X 11 - X 12 - X 13 - X 15 - X 16 .

Ранни и късни дати за завършване на събитията. Отслабване на събитието

Всички пътища, които се различават по продължителност от критичния път, имат резерви от време. Разликата между дължината на критичния път и всеки некритичен път се нарича обща хлабина на дадения некритичен път и се обозначава с: .

ранен терминзавършване на събитие се нарича най-ранната точка във времето, до която цялата работа, предхождаща това събитие, е завършена, т.е. се определя от продължителността на максималния път, предхождащ събитието, т.е.:

или

За да намерите ранната дата на събитието j, трябва да знаете критичния път на насочения подграф, който се състои от набор от пътища, предхождащи даденото събитие j. Ранният член на първоначалното събитие е равен на нула: t p (1)=0.

късен срок събитиенарича най-късната точка във времето, след която има точно толкова време, колкото е необходимо за завършване на цялата работа след това събитие. Последният от допустимите срокове за изпълнение на събитието, съвкупно с продължителността на изпълнение на всички следващи дейности, не трябва да надвишава дължината на критичния път. Късният краен срок за събитие се изчислява като разликата между продължителността на критичния път и продължителността на максимума от пътищата, следващи събитието:

За събития на критичния път ранните и късните дати за завършване на тези събития са еднакви.

Разликата между късните и ранните дати за завършване на събитието е резервният час на събитието: . Интервалът се нарича интервал на свобода на събитието. Пропускът на събитието показва максимално допустимото време, през което дадено събитие може да бъде отложено без увеличаване на критичния път.

Тъй като сумата определя продължителността на пътя с максимална дължина, преминаващ през това събитие, тогава , т.е. хлабината на всяко събитие е равна на пълната хлабина на максималния път през това събитие.

При ръчно изчисляване на параметрите на времето е удобно да се използва методът на четирите сектора. При този метод кръгът от мрежовата диаграма, обозначаващ събитието, се разделя на четири сектора. Номерът на събитието се поставя в горния сектор; вляво - най-ранният възможен час на събитието (); вдясно - най-късното от допустимото време на събитието; в долния сектор - резервното време на това събитие: .

За да изчислите най-ранната крайна дата за събития: , приложете формулата , разглеждайки събитията във възходящ ред на номерата, от началния до крайния, според произведенията, включени в това събитие.

Късната дата за приключване на събитията се изчислява по формулата , започвайки от крайното събитие, за което ( - номер на крайното събитие), според произтичащите от него задания.

Критичните събития имат застой от нула. Те определят критичните дейности и критичния път.

Пример 10.2. Нека мрежовата диаграма, показана на фиг. 10.8.

Решение.Изчислете ранните дати за завършване на събитията:

Така че финалното събитие може да се случи едва на 14-ия ден от началото на проекта. Това е максималното време, за което могат да бъдат изпълнени всички дейности по проекта. Определя се от най-дългия път. Предсрочната дата на завършване на работата 6 =14 съвпада с критичното време kp - общата продължителност на работата, лежаща на критичния път. Сега можете да маркирате дейностите, които принадлежат към критичния път, връщайки се от крайното събитие към първоначалното. От двете задачи, включени в събитието 6 , , дължината на критичния път определя задачите (5, 6), тъй като (5 + 56)=14. Следователно работата (5, 6) е критична и т.н. Работи (1, 3), (3, 4), (4, 5), (5, 6) определят критичния път: cr = (1-3-4-5-6).

Сега изчисляваме късните дати за завършване на събитията. Позволявам . Нека използваме метода на динамично програмиране. Всички изчисления ще бъдат извършени от крайното събитие до първоначалното събитие. Късните дати за завършване на събитията са:

Тъй като след събитие 5, за да завършите проекта, работата (5, 6) трябва да бъде завършена за 3 дни. Две задачи излизат от събитие 4, така че:

Пропускът за събитие 2 е: . Резервите на останалите събития са равни на нула, тъй като тези събития са критични.

Ранни и късни начални и крайни дати. Определяне на резервите от работно време. Пълен резерв от работно време.

Събитието, непосредствено предхождащо тази работа, ще бъде извикано първичени обозначават , и събитието непосредствено след него, - финали посочете. Тогава всяка работа ще бъде означена с . Познавайки времето на завършване на събитията, можете да определите времевите параметри на работата.

Ранно начално времее равно на ранната дата на събитието: .

Ранно приключване на работатае равно на сумата от ранната дата за завършване на първоначалното събитие и продължителността на тази работа: или .

Късен край на работасъвпада с късната дата на завършване на последното му събитие: .

Късен начален часе равна на разликата между късната дата на завършване на крайното събитие и стойността на тази работа:

Тъй като сроковете за изпълнение на работата са в границите, определени от и , те могат да имат различни видове времеви резерви.

Пълен резерв от работно време -това е максималното време, необходимо за завършване на всяка работа, без да се превишава критичният път. Изчислява се като разликата между късното крайно събитие и ранното време за завършване на самата работа: . От тогава .

По този начин, пълен резерв по време на работае максималното време, с което неговата продължителност може да бъде увеличена, без да се променя продължителността на критичния път. Всички некритични задачи имат ненулева обща хлабина.

Безплатен резерв за работно време- това е запасът от време, който може да бъде наличен при извършване на тази работа, при условие че нейните начални и крайни събития се случват на най-ранните им дати: .

Изчисляването на мрежовата графика в табличен вид се извършва съгласно формулите, посочени по-рано в раздел 4 (1-10). При определяне на параметрите на мрежовите модели по аналитичен начин изчислението се извършва под формата на таблица. Помислете за характеристиките на изчисляването на мрежови модели по този начин (приложение 1), като използвате примера за изчисляване на параметрите на мрежовата диаграма, показана в заданието за тази курсова работа (опция 15).

В началния етап е необходимо да се опише първоначалният мрежов модел. В този случай шифрите на всички задания и зависимости се въвеждат в първата колона на таблицата, като се започне от заданието, произтичащо от първото събитие. Кодовете на длъжностите трябва да бъдат включени в таблицата последователно, произволен ред на включване на длъжности и зависимости в таблицата не е разрешен. Втората колона на таблицата съдържа продължителността на всички работи и зависимости.

Изчисляването на мрежовия график започва с определянето на стойностите на ранните параметри на работата. Ранното начало на работа 1-2 е равно на нула (формула 1), а ранният й край според формула 2.

Ранният старт на дейности 2-6 и 2-7 (в съответствие с формула 3) е равен на ранния край на дейност 1-2.

Максималната стойност на ранното завършване на работа 19-21, равна на 36, определя продължителността на критичния път и следователно общата продължителност на изпълнението на всички дейности в оригиналния мрежов модел. Получената стойност на ранното завършване на тази работа 19-21 = 36 се прехвърля в колоната на късното завършване на крайната работа 20-21.

Късното начало на работа 20-21 се определя по формула 5 (= 34)

Късното начало на работа 20-21 е късният край на работа 15-20 (=), която го предхожда.

Освен това изчисляването на късните параметри се извършва по подобен начин, с изключение на случаите, когато заданието има няколко последователни задания (например задание 6-9 има две последователни - 9-10 и 9-14). В този случай, в съответствие с формула 4, късното завършване на работа 6-9 е равно на минималната стойност на късното начало на последваща работа 9-10 и 9-14.

За да намерите позицията на критичния път, е необходимо да определите стойностите на общия и частния резерв от време за всяка работа и зависимостите на мрежовата диаграма и да въведете техните стойности в 7-ма и 8-ма колона на изчислението маса, съответно.

Общият резерв от работно време, съгласно формули 8-9, се определя като разликата между късното и ранното завършване или като разликата между късното и ранното начало на съответната работа. Полезно е да се определи стойността на общата хлабина и по двата начина, съвпадението на получените стойности може да се счита за допълнителна проверка. Например за работа 6-7:

Частичният застой на работното време, съгласно формула 10, се определя като разликата между стойността на ранното начало на следващата дейност и стойността на ранното приключване на тази дейност. Например за работа 6-7:

Критичният път се характеризира с нулева хлабина. Сравнението на параметрите на мрежовия модел, получени чрез секторни и таблични методи, трябва да разкрие пълната им идентичност, наличието на несъответствия показва погрешността на изчисленията.

Графичен метод за изчисляване на мрежови диаграми

Изчисляването на мрежовата графика по графичен начин се извършва подобно на табличния метод (формули 1-10), но графичният или секторен метод за изчисляване на параметрите на мрежовата графика включва записването им директно върху модела (Приложение 2). Всяко събитие (кръг) е разделено на четири сектора. Обозначаването на секторите е показано на следната фигура:

За дейностите по критичния път общите и частичните стойности на провисване са равни на нула; това е маркирано на диаграмата на мрежата с двойна линия.

За да проверите правилността на извършените изчисления, трябва да се уверите, че:

• * разкри непрекъснат критичен път;
• * изчислените времеви резерви имат неотрицателна стойност;
• * стойността на частния пропуск за всички задачи е по-малка или равна на стойността на общия пропуск за тези задания;
• * поне една стойност на късното начало на работите (работите), произтичащи от първото събитие, е равна на нула.

Известни са две метод за изчисляване на параметрите на мрежовата графика".изчисляване директно върху мрежовата графика; аналитични (таблични).

Изчисляване основни показатели на мрежовия моделможе да стане по следния начин.

• 1. Изчисляване на ранните дати:
  • ? ранно започване на работасе определя от продължителността на най-дългия път от изходното събитие до началото на изпълнението на тази работа,
  • ? ранни дати на завършване- това е възможно най-ранната дата за завършване на работата. Времето за ранно приключване на работата е равно на сумата от времето за ранно начало на работата и продължителността на самата работа.
• 2.Изчисляване на критичния път.Продължителността му се определя като общото време на дейностите по критичния път, т.е. времето за завършване на целия комплекс от работи с най-голямо паралелизиране на всички работи. Това време е равно на най-голямото от времето за ранно завършване на завършванията на мрежовата графика. Критичният път преминава през събития, които нямат времеви резерви (през критични дейности).
• 3.Изчисляване на късни начални и крайни датисе определят от възможностите за изместване на границата надясно по цифровата ос на сроковете за завършване на работата, така че времето на критичния път да не се променя. Следователно е логично да се извършат изчисления от последното събитие до първото и първо да се определи времето на късното завършване на работата и след това да се изчисли времето на късното начало на работа:
  • ?късна начална дата (ij) се определя като разликата между късното завършване на работата и продължителността на самата работа,
  • ? късна дата на завършванесе определя от стойността на пътя с минимална продължителност, водещ до него от крайното събитие, и се изчислява като разликата между критичния път и максималната продължителност на работа от крайното събитие на мрежовата диаграма до крайното събитие на тази работа .
• 4. Изчисляване на резервите от време".

азпълен резерв по време на работасе определя като разликата между късен старт и ранен старт, или между късен финал и ранен финал. Трябва да се отбележи, че общото време за работа по критичния път е равно на нула,

• ? частен (свободни) времеви резерви“.
• 1)частен застой от първи видопределя се от възможността за промяна на късното начално време ( ij)към по-ранни дати, без да се променят късните срокове за завършване на непосредствено предходна работа,
• 2) частен застой от втори видсе определя от способността за промяна на ранния край на работата (ij)на по-късни дати, без да се променят ранните дати за започване на непосредствено следваща работа; се определя от разликата между ранното начало на последващата дейност и ранния край на тази дейност.

Нека разгледаме процедурата за изчисляване на параметрите с помощта на пример. Диаграмата на мрежата е показана на фиг. 7.5.

Ориз. 7.5.

За да изчислим параметрите, ще използваме табличния метод, а за да опростим възприемането, ще обобщим всичко в една таблица. 7.1.

Правила за използване на времеви резерви при мрежово планиране.

• 1. За да бъдат равни общите и частичните резерви на работа (y), е необходимо и достатъчно крайното събитие Y на въпросната работа да е събитие на критичния път.
• 2. Ако е пълна резерва (Аз и]1)на някаква работа е равна на нула, тогава частният резерв от втория тип (g "f)също е равно на нула. Между тези резерви винаги има съотношение R(IJ) > r"ijyОбщите и частните времеви резерви винаги са по-големи или равни на нула.
• 3. За да бъде частичният резерв от работно време (y) равен на нула, е необходимо и достатъчно тази работа да лежи на пътя с максимална дължина от първото събитие до събитието y.
• 4. Ако продължителността на работа (y) се увеличи с p, т.е. p тогава ранната начална дата на последващата работа ще се увеличи със стойността на p - g" ("uu
• 5. Ако продължителността на работа (y) се увеличи с размера на общия резерв от време за тази работа, тогава се образува нов критичен път, чиято продължителност е равна на продължителността на стария.
• 6. Общият резерв от работно време (y) е равен на сумата от частичния резерв от време на втория вид от тази работа и минимума от общия резерв от цялата непосредствено следваща работа.

Резултатите от изчисляването на параметрите на мрежовата диаграма

Таблица 7.1

	Продължителност	Рано	условия, з	Късни дати, з		Времеви резерви, h
	работи, з	Наченки	окончания	Наченки	окончания	Пълна	Безплатно
	Критичен път, h		(работи 1-3

7. Ако продължителността на работа (r /) се увеличи с p, тогава ще се появи нов критичен път, чиято продължителност ще надвишава продължителността на стария критичен път с p -

След като се изгради мрежовата графика и се изчислят основните й показатели, те започват да я оптимизират.

• 1. Изберете критичния път и намерете неговата дължина;
• 2. Определяне на времеви резерви за всяко събитие;
• 3. Определете резервите от време на цялата работа и коефициента на интензивност на работата на предпоследната работа

Решение

За да решим проблема, прилагаме следната нотация.

Мрежов елемент	Име на параметъра	Символ на параметъра
Събитие i	Ранна дата на завършване на събитието
Късна дата на завършване на събитието
Отслабване на събитието
работа (i, j)	Работно време
Ранно начално време
Ранно приключване на работата
Късен начален час
Късен край на работа
Пълен резерв по време на работа
	Време за пътуване
Критична дължина на пътя
Резервно време за пътуване

За да се определят резервите от време за събитията в мрежата, се изчисляват най-ранната t p и най-късната t p дата за завършване на събитията. Всяко събитие не може да се случи, преди всички събития, които го предхождат, да са завършени и цялата предишна работа не е завършена. Следователно ранното (или очакваното) време tp(i) на i-тото събитие се определя от продължителността на максималния път, предхождащ това събитие:

t p (i) = max(t(L ni)) (1)

където L ni е всеки път, предхождащ i-тото събитие, т.е. пътят от първоначалното до i-тото събитие на мрежата.

Ако събитие j има няколко предишни пътя и следователно няколко предишни събития i, тогава е удобно да се намери ранната дата за завършване на събитие j, като се използва формулата:

t p (j) = max (2)

Забавянето на завършването на събитие i по отношение на неговата ранна дата няма да повлияе на времето за завършване на последното събитие (и следователно времето за завършване на комплекса от работи) до сумата от времето за завършване на това събитие и продължителността (дължината) на максимума от пътищата, следващи го, не надвишава дължината на критичния път. Следователно късният (или граничният) срок t p (i) на завършването на i-тото събитие е равен на:

t p (i) = t kp - max(t(L ci)) (3)

където Lci е всеки път, следващ i-тото събитие, т.е. пътя от i-тото до последното мрежово събитие.

Ако събитие i има няколко последващи пътя и следователно няколко последващи събития j, тогава късната дата на завършване на събитие i може да бъде намерена удобно с помощта на формулата:

t p (i) = min

Времевият резерв R(i) на i-то събитие се определя като разликата между късната и ранната дата на неговото завършване:

R(i) = t p (i) - t p (i)

Пропускът на дадено събитие показва колко време събитието може да бъде отложено, без да причини увеличаване на продължителността на работния пакет.

Критичните събития нямат забавяне, тъй като всяко забавяне в завършването на събитие по критичния път ще причини същото забавяне в завършването на крайното събитие. По този начин, след като определихме ранния срок на крайното събитие на мрежата, ние по този начин определяме дължината на критичния път.

Когато определяме ранното време на събития tp(i), ние се движим по мрежовата графика отляво надясно и използваме формули (1), (2).

Изчисляване на времето на събитията.

За i=0 (първоначално събитие), очевидно tp(0)=0.

i=1: t p (1) = t p (0) + t(0,1) = 0 + 0 = 0.

i=2: t p (2) = t p (1) + t(1,2) = 0 + 8 = 8.

i=3: t p (3) = t p (1) + t(1,3) = 0 + 3 = 3.

i=4: max(t p (2) + t(2,4);t p (3) + t(3,4)) = max(8 + 6;3 + 3) = 14.

i=5: tp(5) = tp(4) + t(4,5) = 14 + 0 = 14.

i=6: max(t p (4) + t(4,6);t p (5) + t(5,6)) = max(14 + 5;14 + 3) = 19.

i=7: t p (7) = t p (6) + t(6,7) = 19 + 9 = 28.

i=8: max(t p (2) + t(2,8);t p (6) + t(6,8);t p (7) + t(7,8)) = max(8 + 18;19 + 5; 28 + 4 ) = 32.

i=9: max(t p (5) + t(5,9);t p (7) + t(7,9)) = max(14 + 2;28 + 4) = 32.

i=10: max(t p (4) + t(4,10);t p (7) + t(7,10);t p (9) + t(9,10)) = max(14 + 4;28 + 2; 32 + 0) = 32.

i=11: max(t p (8) + t(8,11);t p (10) + t(10,11)) = max(32 + 12;32 + 4) = 44.

Дължината на критичния път е равна на ранната дата на завършване на последното събитие 11: t kp =tp(11)=44

Когато определяме късните дати за завършване на събития t p (i), ние се движим през мрежата в обратна посока, тоест отдясно наляво, и използваме формули (3), (4).

За i=11 (последното събитие), късната дата на събитието трябва да е равна на ранната му дата (в противен случай дължината на критичния път ще се промени): t p (11)= t p (11)=44

i=10: t p (10) = t p (11) - t(10,11) = 44 - 4 = 40.

i=9: t p (9) = t p (10) - t(9,10) = 40 - 0 = 40.

Преглеждат се всички редове, започващи с номер 8.

i=8: t p (8) = t p (11) - t(8,11) = 44 - 12 = 32.

Преглеждат се всички редове, започващи с номер 7.

i=7: min(t p (8) - t(7,8);t p (9) - t(7,9);t p (10) - t(7,10)) = min(32 - 4;40 - 4;40 - 2 ) = 28.

i=6: min(t p (7) - t(6,7);t p (8) - t(6,8)) = min(28 - 9; 32 - 5) = 19.

Преглеждат се всички редове, започващи с номер 5.

i=5: min(t p (6) - t(5,6);t p (9) - t(5,9)) = min(19 - 3;40 - 2) = 16.

i=4: min(t p (5) - t(4,5);t p (6) - t(4,6);t p (10) - t(4,10)) = min(16 - 0;19 - 5;40 - 4 ) = 14.

Преглеждат се всички редове, започващи с номер 3.

i=3: t p (3) = t p (4) - t(3,4) = 14 - 3 = 11.

i=2: min(t p (4) - t(2,4);t p (8) - t(2,8)) = min(14 - 6; 32 - 18) = 8.

i=1: min(t p (2) - t(1,2);t p (3) - t(1,3)) = min(8 - 8;11 - 3) = 0.

(0,1): 0 - 0 = 0;

Таблица 1 - Изчисляване на резерва от събития

Номер на събитието	Време на събитието: ранен tp(i)	Дати на събитието: късно tp(i)	Времеви резерв, R(i)

Попълване на таблица 2.

Списъкът на произведенията и тяхната продължителност ще бъдат прехвърлени във втората и третата колона. В този случай работата трябва да бъде записана в колона 2 последователно: първо, започвайки от номер 0, след това от номер 1 и т.н.

Във втората колона поставяме число, което характеризира броя на непосредствено предшестващите работи (KPR) на събитието, от което започва въпросната работа.

И така, за работата (1,2) в колона 1 поставяме числото 1, т.к номер 1 завършва 1 работа: (0,1).

Колона 4 се получава от таблица 1 (t p (i)). Колона 7 се получава от таблица 1 (t p (i)).

Стойностите в колона 5 се получават чрез сумиране на колони 3 и 4.

В колона 6 късното начало на работа се определя като разликата между късното завършване на тези работи и тяхната продължителност (данните в колона 3 се изваждат от стойностите на колона 7);

Съдържанието на колона 8 (общ пробив R(ij)) е равно на разликата между колони 6 и 4 или колона 7 и 5. Ако R(ij) е равно на нула, тогава работата е критична

Таблица 2 – Анализ на мрежовия модел във времето

работа (i,j)	Брой предишни работи	Продължителност tij	Ранни дати: началото на tijR.N.	Ранни дати: край tijР.О.	Късни дати: началото на tijP.N.	Късни дати: край tijP.O.	Резерви от време: пълен RijP	Независим времеви резерв Rij	Частен резерват от 1-ви вид, Rij1	Частен резерват тип II, RijC

Трябва да се отбележи, че в допълнение към пълния резерв на работно време има още три вида резерви. Частен интервал от първи тип R 1 - част от общия интервал от време, с която може да се увеличи продължителността на работа, без да се променя късната дата на нейното първоначално събитие. R 1 се намира по формулата:

R(i,j)= R p (i,j) - R(i)

Частична хлабина от втори тип или свободна хлабина Rc на работа (i, j) е част от общата хлабина, с която може да се увеличи продължителността на работа, без да се променя ранната дата на нейното крайно събитие. Rc се намира по формулата:

R(i,j)= R n (i,j) - R(j)

Стойността на свободното време на изпълнение показва местоположението на пропуска, необходим за оптимизация.

Независимият времеви резерв Rn на работа (i, j) е част от общия резерв, получен за случая, когато цялата предишна работа приключи късно и цялата следваща работа започне рано. Rн се намира по формулата:

R(i,j)= Rп(i,j) - R(i) - R(j)

критична пътека: (0,1)(1,2)(2,4)(4,6)(6,7)(7,8)(8,11)

Продължителност на критичния път: 44

Нека намерим коефициента на интензивност на работа на предпоследната работа. Тъй като дължината на критичния път е 44, максималният път през работа (1,10) е 32, тогава

K(1,10)=(32-28)/(44-28)=0,296.

4. Интернет доставчик в малък град има 5 специални канала за обслужване. Обслужването на един клиент отнема средно 25 минути. Системата получава средно 6 acza на час. Ако няма свободни канали, следва отказ. Определете характеристиките на услугата: вероятността от повреда, средният брой комуникационни линии, заети от услугата, абсолютната и относителна пропускателна способност, вероятността за услуга. Намерете броя на специалните канали, за които относителната пропускателна способност на системата ще бъде най-малко 0,95. Да приемем, че потоците от заявки и услуги са най-прости

Интензивност на потока на услугата:

Интензитет на натоварване:

c \u003d l * t obs \u003d 6 * 25/60 \u003d 2,5

Интензивността на натоварването c=2.5 показва степента на съгласуваност между входните и изходните потоци на заявките за обслужващ канал и определя стабилността на системата за масово обслужване.

Вероятността услугата:

канал 1 зает:

p 1 = с 1 / 1! p 0 = 2,5 1/1! * 0,0857 = 0,214

2 канала са заети:

p 2 \u003d c 2 / 2! p 0 = 2,5 2 /2! * 0,0857 = 0,268

3 канала са заети:

p 3 \u003d c 3 / 3! p 0 = 2,5 3 /3! * 0,0857 = 0,223

4 канала са заети:

p 4 = с 4 / 4! p 0 = 2,5 4 /4! * 0,0857 = 0,139

5 канала са заети:

p 5 = с 5 / 5! p 0 = 2,5 5 /5! * 0,0857 = 0,0697

Вероятността за провал е малка частотхвърлени заявления:

Това означава, че 7% от постъпилите заявления не се приемат за обслужване.

Вероятност за обслужване на входящи заявки- вероятност клиентът да бъде обслужен:

В системи с повреди, събитията от повреда и поддръжка представляват пълна група от събития, така че:

p отворено + p obs = 1

Относителна производителност Q = p наб .

p obs \u003d 1 - p otk \u003d 1 - 0,0697 \u003d 0,93

Следователно 93% от получените заявления ще бъдат обслужени. Среден брой канали, заети от услуга

n s \u003d s * p obs \u003d 2,5 * 0,93 \u003d 2,326 канала.

Средно неактивни канали.

n pr \u003d n - n z \u003d 5 - 2,326 = 2,7 канала.

Степен на заетост на канала за обслужване.

Следователно системата е 50% заета с поддръжка.

Абсолютна честотна лента

A \u003d pobs * l \u003d 0,93 * 6 \u003d 5,581 приложения / час.

Средно време на престой на QS.

t pr \u003d p otk * t obs \u003d 0,0697 * 0,417 \u003d 0,029 часа.

Среден брой обслужени заявки.

L obs \u003d s * Q \u003d 2,5 * 0,93 \u003d 2,326 единици.

Средно време на престой на приложение в CMO(формула на Литъл).

Брой заявки, отхвърлени в рамките на един час: l * p 1 = 0,418 заявки на час.

Номинална QS производителност: 5 / 0,417 = 12,002 приложения на час.

Действителната производителност на CMO: 5.581 / 12.002 = 47% от номиналната производителност.

Нека определим броя на каналите, необходими за осигуряване на работоспособността на системата с вероятността P ? 0,95

За да направим това, намираме n от условието:

Нека намерим вероятността, че ако има 6 канала в системата и всички те са заети: