Оптимизация сетевой модели

СОДЕРЖАНИЕ 

     Введение.…….……………………………..………………………..……..2

     Принятые  условные обозначения………...……………………......……..3

     Основные понятия сетевой модели………...……………………......…...4

     Правила построения сетевого графика……………………………………7

     Основные  параметры сетевого графика………………………….……….8

     Определение продолжительности работ……………………………..….10

     Расчет  параметров сетевого графика графическим  методом…………..11

     Расчет  параметров сетевого графика табличным  методом………….....16

     Построение  карты проекта сетевого графика…………………………...18

     Оптимизация сетевого графика по времени………………………….…19

     Оптимизация сетевого графика по ресурсам……………………..……..27

     Заключение……………………………………………………..…………32

     Список  использованной литературы……………………………..……...33 

      ВВЕДЕНИЕ 

     Актуальность  сетевого планирования на предприятиях в настоящее время не вызывает сомнения. Наряду с линейными графиками и табличными расчетами сетевые методы планирования находят широкое применение при разработке перспективных планов и моделей создания сложных производственных систем и других объектов долгосрочного использования.

     Сетевое планирование служит основой экономических  и математических расчетов, графических  и аналитических вычислений, организационных  и управленческих решений, оперативных  и стратегических планов, обеспечивающих не только изображение, но и моделирование, анализ и оптимизацию проектов.

     СПУ применяется:

     - в научно-исследовательских разработках,  опытно-конструкторских работах,  в проектировании;

     - в опытном производстве;

     - в государственных программах (развития  района, охраны окружающей среды);

     - в строительстве промышленных  и гражданских объектов;

     - в подготовке и проведении  крупных организационных мероприятий  (конференций, компаний);

     - в разведке и освоении новых  месторождений полезных ископаемых;

     - в ремонте промышленного оборудования  и средств труда; 

     - в материально-техническом снабжении  и пр.

     Целью курсового проекта является развитие навыков построения, расчета, анализа и оптимизации сетевой модели (графика, сети).

     Задачи  курсового проекта:

     На  основе исходных данных (таблица 1) необходимо:

     1) рассчитать ожидаемую продолжительность выполнения работ;

     2) построить топологическую модель сетевого графика;

     3) рассчитать параметры сетевой модели графическим и табличным методами;

     4) построить карту проекта сетевой модели;

     5) рассчитать показатели: вероятность свершения завершающего события, коэффициенты напряженности работ;

     6) оптимизировать сетевую модель  по времени:

     а) путем изменения топологии одной  из работ критического пути, разбив ее на две параллельно выполняемые  работы с соотношением продолжительностей  1/3 : 2/3;

     б) путем перераспределения ресурсов с работ, имеющих большие резервы (Кн < 0,8) на самую продолжительную  работу критического пути, тем самым  добиться сокращения ее продолжительности  в два раза;

     7) рассчитать параметры оптимизированной  по времени сетевой модели  табличным методом;

     8) построить карту проекта оптимизированной  модели;

     9) рассчитать показатели: вероятность  свершения завершающего события,  коэффициенты напряженности работ  для оптимизированной модели;

     10) оптимизировать сетевую модель  по ресурсам, если известно, что  для выполнения работ выделено 10 человек;

     11) сделать выводы.

     Принятые  условные обозначения

t_i,j – ожидаемая продолжительность данной работы;

B_i,j – численность исполнителей по работе;

T_i,j, T_i,j – поздний и ранний сроки свершения события;

R_i – резерв времени i-го события;

T_{pн i,j} ,T_{nн i,j} – ранний и поздний сроки начала работы (i,j);

T_{poij  ,}T_{no i,j} – ранний и поздний сроки окончания работы (i,j);

R_nij – полный резерв работы (i,j);

- часть полного резерва работы;

R_cij – свободный резерв работы (i,j);

t (L_i) – продолжительность полного пути;

t (L_kp) – продолжительность критического пути;

t (L_max) – продолжительность максимального полного пути, проходящего через данную работу

- продолжительность отрезка  пути t (L_max), совпадающего с критическим путем;

K_нij – коэффициент напряженности работ;

T_kp – срок свершения завершающего события (по расчету);

T_д – заданный (директивный) срок свершения завершающего события;

- сумма дисперсии работ,  лежащих на критическом пути.

     Основные  понятия о сетевой  модели

     Для планирования и управления комплексами  работ (технологических операций, проектов, научно технических разработок и  т.д.) применяются системы сетевого планирования и управления (СПУ). СПУ  основано на построении графического изображения определенного комплекса  работ, отражающего их логическую последовательность, взаимосвязь и длительность, с  последующим анализом и оптимизацией разработанного графика.

     Сетевая модель (график, сеть) представляет собой  графическую модель, в которой  изображаются взаимосвязи и результаты все работ планируемого комплекса (рис. 1)

     Рис. 1 График сетевой модели

     Основными элементами графика являются события  и работы.

     События – это результат выполнения одной  или нескольких работ. Событие –  это свершившийся факт, оно занимает лишь один момент во времени и не имеет продолжительности. Оно указывает  на начало каких-либо работ и может  быть одновременно итогом завершения других работ. Событие формулируется  в совершенной форме (например, «задание выполнено», «механическая обработка  деталей закончена»). Различают две  группы событий: для всей совокупности работ – исходное I и завершающее С, а для каждой работы – начальное i и конечное j.

     В сетевом графике событие изображается геометрической фигурой (кружком, прямоугольником, квадратом, шестиугольником и т.д.), в котором указывается порядковый номер или шифр события, а иногда и название события (см. рис. 1).

     Работами  называются любые процессы, действия, приводящие к достижению определенных результатов (событий).

     Работа  может быть действительной или фиктивной. Действительная работа – процесс, требующий  затрат времени и исполнителей («разработка  маршрутной технологии», «изготовление  штампов», «разработка чертежей», механическая обработка деталей», «старение отливок»). Графически действительная работа изображается сплошной линией со стрелкой, которая  означает затрату времени, необходимого для выполнения данной работы. Затрачиваемое на работу время указывается над стрелкой, а число исполнителей под стрелкой. Фиктивная работа устанавливает только логическую связь между работами, она не требует затрат времени и исполнителей (передача по телефону или телетайпу необходимой информации), на сетевом графике изображается пунктирной линией (см. рис. 1).

     Любая последовательность работ  в сетевом  графике, в которой конечное событие  одной работы совпадает с начальным  событием следующей за не работы, называется путем. В сетевом графике следует  различать несколько видов путей:

     а) от исходного события до завершающего события – полный путь;

     б) от исходного события да данного  – путь, предшествующий данному  событию;

     в) от данного события до завершающего – путь, последующий за данным событием;

     г) между двумя какими-либо промежуточными событиями i и j – путь между событиями i и j;

     д) путь между исходными и завершающим  событием, имеющий небольшую продолжительность  – критический путь. 

     Сетевое планирование и управление включает семь этапов:

     1 – составления перечня работ,  которые надлежит выполнить по  объекту разработки для получения  конечной цели;

     2 – установление типологии сети, т.е. четкой последовательности  и взаимосвязи данной, предшествующей  и последующей работ;

     3 – построение графика;

     4 – определение продолжительности  работ;

     5 – расчет параметров сети;

     6 – анализ сети и оптимизация  сетевого графика;

     7 – функционирование сетевой модели. 

     Правила построения сетевого графика

1. При построении сетевого графика необходимо соблюдать технологическую последовательность выполняемых работ планируемого комплекса.
2. В сетевом графике не должно быть пересекающихся стрелок.
3. Направление стрелок в сетевом графике должно быть слева направо.
4. В сетевом графике не должно быть событий, которым не предшествует ни одна работа (кроме исходной).
5. В построенном сетевом графике должно быть одно начальное и одно завершенное событие.
6. В сетевых графиках необходимо соблюдать последовательность в нумерации событий от исходного, которому обычно присваивается нулевой номер, к завершающему. При этом для любой работы i-j одним из условий правильного построения сетевого графика является обязательным выполнения неравенства i<j.

     Для любого из этих событий максимальное число стрелок пути, соединяющего их с событием нулевого ранга, равно 1. События первого ранга в произвольном порядке получают номера 1, 2, 3, …  n₁ (n₁ – число событий первого ранга).

     Далее вычеркиваются стрелки, выходящие  из событий первого ранга, получается вновь некоторое число событий  без входящих стрелок. Их называют событиями  второго ранга. Максимальное число  последовательно расположенных  стрелок, соединяющих любое из этих событий с событием нулевого ранга, равно 2. События второго ранга  получают номера n₁+1; n₁+2, …, n₁+n₂ (n₂ – число событий второго ранга).

     Основные  параметры сетевого графика

     К основным параметрам сетевого графика  относятся критический путь, резервы  времени событий и работ. Эти  параметры являются исходными для  получения ряда дополнительных характеристик, а также для анализа сети.

     1) Критическим путем называют наибольший  по продолжительности из всех  путей графика от исходного  события до завершающего. В сетевом  графике имеются и другие пути, опирающиеся на исходное и  завершающее событие (полные пути), которые могут либо полностью  проходить вне критического пути, либо частично совпадать с  критической последовательностью  работ. Эти пути называются  не напряженными. Ненапряженные  пути – это полные пути сетевого  графика, которые по продолжительности  меньше критического пути.

     Ненапряженные пути обладают важным свойством: на участках, не совпадающих с критической  последовательностью работ, они  имеют резервы времени. Это означает, что задержка в совершении событий, не лежащих на критическом пути, до определенного момента не влияют на срок завершения разработки в целом. Критические пути резервами времени  не располагают.

     2) резерв времени события – это  такой промежуток времени, на  который может быть отсрочено  свершение этого события без  нарушения сроков завершения  разработки в целом.

     Резерв  времени события R_i определяется как разность между поздним Tn_i и ранним Tpi сроками наступления события:

     R_i = Tn_i – Tpi                             (1)

     3) Поздний срок Tn_i – это такой срок свершения i-го события, превышение которого вызовет задержку завершающего события.

     Ранний  из возможных сроков свершения i-го события Tpi – минимальный срок, необходимый для выполнения всех работ, предшествующих данному событию.

     Ранний  срок свершения события i определяется как продолжительность во времени максимального из путей L_max, ведущих от исходного события I до данного события i:

     T_pi = t [L(I+i)_max]                       (2)

     Поздний срок свершения события i определяется разностью между продолжительностями критического пути t(L_кр) и максимального из последующих за данным событием путей до завершающего события:

     Tni = t(L_кр) – t [L(i-C)_max]             (3)

     Путь, соединяющий события с нулевыми резервами времени, являются критическим.

     4) Резервами времени располагают  также работы. Зная ранние и  поздние сроки наступления событий,  можно для любой работы (i,j) определить ранние и поздние сроки начала и окончания работы.

     Ранний  срок начала работы

     T_{pн i,j} = T_pi                                                                               (4)

     Поздний срок начала работы

     T_{nн i,j} = T_nj – t_i,j                                                                         (5)

     Ранний  срок окончания работы

     T_poij = T_pi + t_i,j                                                                          (6)

     Поздний срок окончания работы

     T_{no i,j} = T_nj                                                                                (7)

     5) Разница во времени между длиной  критического пути t (L_кр) и длиной любого другого пути t (L_i) называется полным резервом времени пути. Он равен

     R (L_i) = t (L_кр) – t (L_i)                   (8)

     Полный  резерв пути показывает, насколько  могут быть увеличены продолжительности  всех работ, принадлежащих пути L_i.

     6) Полный резерв времени работы  R_nij показывает, сколько имеется в запасе времени для выполнения данной работы, на которое можно увеличить продолжительность данной работы, не изменяя при этом продолжительности критического пути:

     R_nij = T_nj - T_pi - t_i,j                            (9)

     7) У отдельных работ помимо полного  резерва времени имеется свободный  резерв времени R_cij, являющийся частью резерва. На время этого резерва можно увеличить продолжительность работы, не изменяя ранних сроков начала последующих работ.

     R_cij = T_pj – T_pi – t_ij                                 (10)

     Резервы времени работы, особенно свободный, позволяют маневрировать сроками  начала и окончания работ, их продолжительностью.

     Определение продолжительности  работ

     При построенной сетевой модели для  каждой работы определяется ожидаемая  продолжительность ее выполнения, которая  проставляется над соответствующей  стрелкой в графике. Для определения  продолжительности работ пользуются установленными нормами времени, при  их отсутствии используют систему вероятностных  оценок. В таких случаях ожидаемое  время выполнения работ t_i,j определяют на основе экспертных оценок по формуле

     Дисперсия, или мера разброса для принятого  в СПУ закона распределения:

     Для двух оценок:

     где  t_min – минимально возможное время выполнения работ;

            t_max – максимально возможное время выполнения работ;

            t_нв – наиболее вероятное время выполнения работ.

     Результаты  расчетов заносятся в табл. 1.

     Таблица 1

     Определение продолжительности работ:

     Расчет  параметров сетевого графика графическим  методом

     Существует  несколько методов расчета сетевых  графиков: графический, табличный, матричный, метод Форда и др.

     Графический метод можно применять в тех  случаях, когда число событий  невелико (до 15-20). При этом каждый кружок, изображающий событие, делится на четыре сектора (рис.3).

     Рис. 3. Секторы событий сетевого графика

     Верхний сектор отводится для номера события; левый – для ранних сроков свершения  событий; правый – для поздних  сроков свершения событий; нижний –  для резервов времени свершения  событий; левая часть стрелки  – для полного резерва работы; правая часть стрелки – для  свободного резерва работы.

     Рассмотрим  последовательность расчета на примере  сетевого графика, изображенного на рис. 4, построенного по данным табл.1.

     Рис.4. Сетевой график

     1) Осуществляется проход сетевого графика от исходного (I) события к завершающему (С) и последовательно определяются ранние сроки свершения конечных событий (правый сектор, рис.5)

     Для исходного события ранний срок свершения  события равен 0 (T_p0=0).

     Для события 1, в которое входит одна работа (0,1), ранний срок свершения события  равен:

     T_p1 = 0+7=7 дней

     Для события 2, в которое входит одна работа (0,2):

     T_p2 = 0+10=10 дней

     Для события 3, в которое входит одна работа (1,3):

     T_p3 = 7+2=9 дней

     Для события 4, в которое входит одна работа (3,4):

     T_p4 = 9+16=25 дней

     Рис. 5. Вычисление параметров непосредственно  на сетевом графике

     Для события 5, в которое входит две  работы (3,5); (4,5):

     28 дней

     Для события 6, в которое входит две  работы (4,6); (5,6):

     36 дней

     Для события 7, в которое входит одна работа (6,7):

     T_p7 = 36+3=39 дней

     Для события 8, в которое входит одна работа (6,7):

     T_p8 = 39+4=43дня

     Для события 9, в которое входит две  работы (6,9); (7,9):

     49 дней

     Для события 10, в которое входит две  работы (9,10); (8,10):

     52 дней

    2) Осуществляется проход сетевого  графика от завершающего события  к исходному и последовательно  определяются поздние сроки свершения  начальных событий (правый сектор  кружочка):

     Для завершающего события поздний срок свершения события равен полученному  значению его раннего срока свершения (Т_п10 = Т_р10 = 52 ).

     Для события 9, из которого выходит одна работа:

     Т_п9 = 52-3=49 дней

     Для события 8, из которого выходит одна работа:

     Т_п8 = 52-4=48 дней

     Для события 7, из которого выходят две работы:

     39дней

     Для события 6               Т_п6 = 39-3=36 дней.

     Для события 5               Т_п5 = 36-8=28 дней.

     Для события 4               Т_п4 = 28-3=25 дней.

     Для события 3               Т_п3 = 25-16=9 дней.

     Для события 2               Т_п2 = 39-2 = 37 дней.

     Для события 1               Т_п1 = 9-2 = 7 дней.

    Для события 0              0 дней.

     3) Определяется резерв времени  каждого события как разность  между правым и левым сектором  события (нижний сектор кружочка, рис.5,б).