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

       Содержание

         
 
 
 
 
 
 
 
 
 
 
 
 
 
 

       Введение 

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

       Работа  включает в себя:

1. расчет ожидаемой продолжительности выполнения работ
2. построение топологической модели сетевого графика
3. расчет параметров сетевого графика одним из предложенных методов
4. построение карты проекта сетевого графика
5. расчет показателей К_{H i, j}, X
6. оптимизация сетевого графика по времени
7. расчет параметров оптимизированного по времени сетевого графика
8. построение карты проекта оптимизированного сетевого графика
9. расчет показателей К_{H i, j}, X для оптимизированного графика
10. оптимизация сетевого графика по ресурсам

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

       1.Основные  методические положения 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. составление перечня работ, которые надлежит выполнить по объекту разработки для получения конечной цели.
2. установление топологии сети
3. построение сетевого графика
4. определение продолжительности работ
5. расчет параметров сети
6. анализ сети и оптимизация сетевого графика
7. функционирование сетевой модели.

 

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

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

 
 
 

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

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

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

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

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

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

       R_i = Т_пi - Т_рi    (1)

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

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

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

       Т_рi = t [ L (I – i)_max ]      (2)

       Поздний срок события I определяется по следующей формуле:

       Т_пi = t (L_кр) – t [ L ( i – C)_max ]      (3)

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

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

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

       T_{рн i,j} = Т_рi     (4)

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

       T_{пн i,j} = Т_пσ – t _i,j     (5)

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

       T_{ро i,j} = Т_рi + t _i,j     (6)

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

       T_{по i,j} = Т_пj     (7)

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

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

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

6. Полный резерв времени работы R_{п i,j} показывает, сколько имеется в запасе времени для выполнения данной работы, на которое можно увеличить продолжительность данной работы, не изменяя при этом продолжительности данного пути:

       R_{п i,j} = Т_пj - Т_рi - t _i,j     (9)

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

       R_{с i,j} = Т_рj - Т_рi - t _i,j     (10)

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

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

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

    

             (11)

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

    

                    (12)

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

    

                  (13)

    

          (14)

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

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