Оптимизация сетевого графика с целью сокращения длины критического пути

Понятие продолжительности критического пути имеет определяющее значение в системах СПУ.

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

В реальных задачах, решаемых с помощью методов сетевого моделирования, кроме ограниченности по времени, приходится сталкиваться с ограниченностью ресурсов, таких, например, как рабочая сила, оборудование и т.п. Тогда возникает задача такого распределения этих ресурсов, которое минимизировало бы время выполнения проекта.

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

Математическая формулировка этой задачи выглядит так.

Найти минимум функции Z=Tn при ограничениях:

где d_ij — ограничение продолжительности работы снизу;

D_ij — ограничения продолжительности работы сверху).

— линейный вариант

или

— выпуклый вариант,

где С — стоимость ресурсов.

Задача для линейного варианта — задача линейного программирования, задача для выпуклой функции — задача выпуклого программирования.

Если положить t_ij=D_ij и найти соответствующую стоимость проекта См, то при С<См задача неразрешима. Если же положить Tn=m (где m — жесткое ограничение для критического времени) и найти соответствующую минимальную стоимость Cm проекта, то при С³Cm =m=Тп будет минимальным временем.

Контрольные вопросы и упражнения

1. Какова основная цель использования сетевого моделирования?

2. Что представляет собой система СПУ и её основной плановый документ?

3. Какие основные этапы планирования и управления комплекса работ охватывает система СПУ?

4. В каких областях практической деятельности человека нашли применение сетевые графики?

5. Что такое граф? Какие типы графов встречаются?

6. Дайте определение сетевого графика.

7. Определите основные элементы сетевого графика. Как они изображаются на графике?

8. Какие разновидности работ встречаются в сетевом графике? Дайте характеристику каждой разновидности и приведите примеры.

9. Дайте определение предшествующего и последующего событий, исходного и завершающего. Приведите примеры.

10. Какие виды путей различают в сетевых графиках?

11. Каковы основные правила построения сетевых графиков?

12. Что понимается под правильной нумерацией сетевых графиков? Для чего она нужна и как достигается?

13. Пронумеруйте события в сетевом графике описанным выше методом (рисунок 19).

14. Постройте сетевой график по данным таблицы 2.

Таблица 2

15. Какие временные параметры рассчитываются для событий и работ?

16. Какой путь называется критическим?

17. Что представляют собой ненапряженные пути, и каким важным свойством они обладают?

18.

19. Что представляют собой резервы времени пути, события и работ?

20. В чем состоит сущность, анализ и оптимизация сети по времени? Какие способы сокращения критического пути существуют?

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

Таблица 3

22. Изобразите данный проект при помощи стрелочного графа. При условии, что компания «Альфа» является участником некоторого проекта, детали которого приведены в таблице 4.

Таблица 4

23. Необходимо выполнить следующее:

1. Составить сетевой график работ всего проекта;

2. Найти критический путь;

3. Найти ранние и поздние сроки свершения событий;

4. Определить резервы времени;

5. Записать итог решения задачи.

При условии, что производится строительство контейнерной площадки для отгрузки овощей на базу (таблица 5).

Таблица 5