Продолжительность критического пути сетевой модели

4.Сетевой график и его назначение. Полный путь. Критический путь.

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

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

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

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

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

Продолжительность критического пути определяет критический срок проекта tкр. Все остальные (некритические) полные пути выполняются параллельно с критическим путем (цепочкой работ) и завершаются раньше. Критический срок, таким образом, показывает, за какое минимальное время может быть завершен весь проект. Очевидно, что увеличение сроков выполнения проекта больше tкр невыгодно.

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

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

Критическим является полный путь μ2, т.к. он имеет наибольшую продолжительность. Критический путь принято выделять на графике жирной линией (рис.2.3.).

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

Для каждого события рассчитывают ранний и поздний сроки свершения.

На их основе определяют резервы времени всех событий и работ.

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

5 Параметры событий сетевого графика. Параметры работ.

Ранний срок свершения события – это самый ранний момент, к которому завершаются все работы, предшествующие этому событию.

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

, т.е. начало проекта принимается за нулевой момент времени;

, если событию j предшествует только одна работа;

, если событию предшествует несколько работ.

Здесь ij – множество работ, заканчивающихся j-м событием (дуги, входящие в вершину j);

–ранний срок свершения события, с которого начинается работа (i,j);

–продолжительность работы (i,j).

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

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

Резервы работ определяются на основе параметров свершения событий по следующей формуле:

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

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

Источник

Этап 3. Расчет параметров сетевой модели графическим методом; определение критического пути и его продолжительности.

• Ранний срок свершения события ;
• Поздний срок свершения события ;
• Резерв времени события ;
• Полный резерв времени события ;
• Свободный резерв времени события .

Рис 3. Результат расчета параметров сетевой модели графическим методом. Критический путь: 1-2-3-4-7-8-10-14-18-24-25-26, 1-2-3-4-7-8-12-16-20-24-25-26. Длина критического пути T(Lкр) = 104. Этап 4. Расчет коэффициентов напряженности работ. Коэффициенты напряженности работ, находящихся на критическом пути: Коэффициенты напряженности для остальных участков сетевого графика вычисляются по формуле . Работы 8-9, 9-13, 13-17, 17-24 являются работами подкритического пути. Этап 5. Построение сетевой модели выполнения комплекса работ в шкале времени.Рис 4. Сетевой график в шкале времени. Этап 6. Построение графиков загрузки исполнителей по каждой профессии (отдельно) в шкале времени (на одном листе с сетевым графиком).Рис 5. Сетевой график в шкале времени и график загрузки ведущих инженеров. Рис 6. Сетевой график в шкале времени и график загрузки старших инженеров. Рис 7. Сетевой график в шкале времени и график загрузки инженеров. Этап 7. Оптимизация сетевой модели по времени с помощью сокращения продолжительности критического пути Т_кр, т.е. длительности цикла выполнения комплекса работ, на одну — две единицы времени. Для оптимизации выбрана работа 8-11 с коэффициентом напряженности . Переведем одного старшего инженера с работы 8-11 на работу критического пути 8-10 и одного старшего инженера на работу критического пути 8-12. Таким образом, продолжительность критического пути сократилась на 1 неделю и составляет теперь 103 недели. Этап 8. Отображение результатов оптимизации на сетевом графике в шкале времени.Рис 8. Сетевой график выполнения комплекса работ в шкале времени после оптимизации по времени. Этап 9. Построение графика загрузки исполнителей по каждой профессии (отдельно) в шкале времени после оптимизации (на одном листе с сетевым графиком).Рис 9. Сетевой график выполнения комплекса работ в шкале времени и график загрузки ведущих инженеров после оптимизации по времени. Рис 10. Сетевой график выполнения комплекса работ в шкале времени и график загрузки старших инженеров после оптимизации по времени. Рис 11. Сетевой график выполнения комплекса работ в шкале времени и график загрузки инженеров после оптимизации по времени. Этап 10. Оптимизация сетевой модели по численности исполнителей и их загрузке; отображение результатов оптимизации на сетевом графике в шкале времени. 1) Численность ведущих инженеров будет оптимизирована за счет работ 2-4, 2-5, 6-7, так как наибольшая нагрузка ведущих инженеров наблюдается во время выполнения данных работ. Объём работы 2-4: Сократим численность до 1 человека. Объём работы 2-5: Сократим численность до 2 человек. Объём работы 6-7: Сократим численность до 3 человек. 2) Загрузка старших инженеров максимальна на участке 39-43. Резерв времени позволяет провести оптимизацию работы 8-9. Объём работы 8-9: Сократим численность до 3 человек. 3) Загрузка инженеров максимальна на участках 45-49 и 65-67. Резерв времени позволяет провести оптимизацию на работах 17-24 и 11-15. Объём работы 17-24: Сократим численность до 3 человек. Объём работы 11-15: Сократим численность до 2 человек. В результате оптимизации сетевой модели по численности количество ведущих инженеров сократилось на 3 человек, количество старших инженеров – на 1 человека, количество инженеров – на 2 человек. К тому же, появился новый критический путь.

Источник

Определение критического пути

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

Путь— последовательность взаимосвязанных работ, ведущая из одной вершины проекта в другую вершину. Например (см. Рисунок 48), и – два различных пути.

Рисунок 48. Различные пути на сетевом графике

Длина пути— суммарная продолжительность выполнения всех работ пути.

Полный путь— это путь от исходного к завершающему событию.

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

Очевидно, что минимальное время, необходимое для выполнения любого проекта равно длине критического пути. Именно на работы, принадлежащие критическому пути, следует обращать особое внимание. Если такая работа будет отложена на некоторое время, то время окончания проекта будет отложено на то же время. Если необходимо сократить время выполнения проекта, то в первую очередь нужно сократить время выполнения хотя бы одной работы на критическом пути.

Для того, чтобы найти критический путь, достаточно перебрать все пути и выбрать тот, или те из них, которые имеют наибольшую суммарную продолжительность выполнения работ. Однако для больших проектов реализация такого подхода связана с вычислительными трудностями. Метод критического пути (метод CPM — Critical Path Method) позволяет получить критический путь намного проще.

Расчет сетевой модели начинают с временных параметров событий, которые вписывают непосредственно в вершины сетевого графика (Рисунок 49):

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

Рисунок 49. Параметры событий Ранние сроки наступления событий рассчитываются от исходного (S) к завершающему (F) событию следующим образом:

1. для исходного события S: ;
2. для всех остальных событий i: ,

где максимум берется по всем работам (k,i), входящим в событие i; — длительность работы (k,i) (см. Рисунок 50). Рисунок 50. Ранние сроки наступления событий Поздние сроки наступления событий рассчитываются от завершающего к исходному событию:

1. для завершающего события F: ;
2. для всех остальных событий i: ,

где минимум берется по всем работам (i,j), выходящим из события i; — длительность работы (i,j) (см. Рисунок 51). Рисунок 51. Поздние сроки наступления событий Условия критичности пути:

• необходимое условие: нулевые резервы событий, лежащих на критическом пути ;
• достаточное условие: нулевые полные резервы работ, лежащих на критическом пути .— показывает максимальное время, на которое можно увеличить длительность работы (i,j) или отсрочить ее начало, чтобы не нарушился срок завершения проекта в целом.

Пример Рассмотрим пример. Компания разрабатывает строительный проект. Исходные данные по основным операциям проекта представлены в таблице. Нужно построить сетевую модель проекта, определить критические пути и проанализировать, как влияет на ход выполнения проекта задержка работы D на 4 недели.

Работа	Непосредственно предшествующая работа	Длительность, недели
A	—	4
B	—	6
C	A, B	7
D	B	3
E	C	4
F	D	5
G	E,F	3

Сетевой график проекта показан на рисунке ниже (см. Рисунок 52). Рисунок 52. Пример. Сетевой график проекта Согласно необходимому условию два полных пути сетевой модели (см. Рисунок 52) имогут быть критическими. Проверим достаточное условие критичности для работ (1,2) и (1,3) , . Путь , начинающийся с работы (1,3) не является критическим, т.к. поскольку как минимум одна из его работ не является критической. Работа (1,3) имеет ненулевой полный резерв, а значит может быть задержана с выполнением, что недопустимо для критических работ. Таким образом, сетевая модель имеет единственный критический путь длительностью 20 недель. За выполнением работ этого пути необходим особый контроль, т.к. любое увеличение их длительности нарушит срок выполнения проекта в целом. Работа D или (2,5) не является критической, ее полный резерв равен 3-м неделям. Это означает, что при задержке работы в пределах 3-х недель срок выполнения проекта не будет нарушен. Поэтому если согласно условию работа D задержится на 4 недели, то весь проект закончится на 1 неделю позже.

Источник