Лабораторная работа №6

№6.Построение сетевого графика

Лабораторная работа № 6

Тема: Построение сетевого графика. Алгоритм нахождения критического пути. Распределение ресурсов.

Цель работы: 1.Построить сетевой график.

2.Установить все критические пути и время выполнения всего комплекса работ двумя способами.

3.Оптимизировать сетевой график по ресурсам.

При организации работ над различными проектами, планировании комплексов работ широкое распространение получили методы сетевого планирования и управления.

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

Критерии, которым должен удовлетворять сетевой график:

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

• каждую пару событий должна соединять не более чем одна работа;

• в сетевом графике должно быть начальное и конечное событие.

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

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

№ работы	Предшествующие работы	Длительность выполнения
1	—	2
2	—	3
3	—	5
4	1	1
5	1	4
6	2	2
7	3,6	4
8	3	3
9	4	4
10	5,9	1
11	6	2
12	7,8,10	1

Табл.1

Проследим, как строится временной сетевой график на рис. 1.

Начинаем его с узла А₀, помещённого в начале координат. Из этого узла исходят три стрелки: а₁, а₂, а₃ (не имеющие предшествующих работ), проекции которых на ось 0t равны временам выполнения соответствующих работ: t₁=2, t₂=3, t₃=5. Работа а₄ опирается на работу а₁. Проекция стрелки а₄ равна t₄=1, следовательно, абсцисса узла А₄, в которой эта стрелка кончается, должна быть T₄=t₁+t₄=2+1=3. Аналогично строим а₅ (T₅=t₁+t₅=2+4=6) и а₆ (T₆=t₂+t₆=3+2=5). Работе а₇ предшествуют работы 3 и 6. Чтобы показать, что работы а₃ и а₆ могут выполняться одновременно, введём дополнительный узел А_3,6, соединяющийся с узлами А₆ и А₃ пунктирными линиями (фиктивные работы). Отметим необходимость введения узла А_3,6.

На рис.2 представлен вариант сетевого графика без введения узла А_3,6, при этом оказывается, что для работы a₁₁ предшествующими являются работы 3 и 6, что не соответствует действительности. Аналогичная ситуация возникает и в случае добавления ребра А₆А₃.

Работы а₃ и а₆ кончаются одновременно в t=5, следовательно стрелка а₇, начинающаяся в А_3,6 и имеющая проекцию на ось Ot равную t₇=4, кончается в А₇ с абсциссой T₇=5+t₇=9. Стрелка а₈ начинается в А₃ и имеет T₄=t₃+t₈=5+3=8. а₉ начинается в узле А₄ и заканчивается в узле А₉ с абсциссой T₉=T₄+t₉=3+4=7. Работа а₁₀ опирается на работы а₅ и а₉ и, следовательно, не может начинаться раньше, чем закончатся обе эти работы. Поэтому стрелку а₁₀ направим из узла А₉, имеющего по сравнению с а₅ большую абсциссу. Но при этом, чтобы показать, что а₅ предшествует а₁₀, соединим А₅ с А₉ пунктирной линией. T₁₀=T₉+t₁₀=7+1=8.

Стрелка а₁₁ начинается из А₆ и заканчивается в А₁₁ с T₁₁=T₆+t₁₁=5+2=7. Последней работе а₁₂ предшествуют работы а₇, а₈, а₁₀. Направим а₁₂ из узла А₇, имеющего большую абсциссу. А₁₁ и А₇, а также А₈ и А₇ соединим пунктирными линиями. T₁₂=T₇+t₁₂=9+1=10.

Так как работа а₁₂ завершается последней, то узел А₁₂=А означает окончание всего комплекса работ. Отметим этот узел жирным кружком и соединим с ним пунктирной стрелкой узел А₁₁- окончание работы А₁₁, на которую, кроме конца работ, никто не опирается.

Таким образом, временной сетевой график комплекса работ построен, время Т=10 от начального узла А₀ до завершающего А=А₁₂ представляет собой минимальное время, за которое может быть завершен комплекс работ.

Обратим внимание на следующее обстоятельство: время исполнения проекта представляет собой сумму времён исполнения не всех работ, а только некоторых из них: T=t₃+t₇+t₁₂=t₂+t₆+t₁₂=10.

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

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

На рисунке критические работы показаны жирными стрелками. В нашем примере критическими являются работы: а₂, а₃, а₆, а₇, а₁₂. Каждая из “некритических” работ имеет временные резервы и может быть закончена с некоторым опозданием без того, чтобы это отразилось на сроке выполнения комплекса в целом.

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

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

На рис. 1 имеются четыре не критические дуги:

А₀а₁А₁а₄А₄а₉А₉а₁₀А₁₀А₇, А₀а₁А₁а₅А₅А₉а₁₀А₇, А₆а₁₁А₁₁А₁₂, А₃а₈А₈А₇.

На первой из дуг лежат 4 некритические работы, на второй - 3, на третьей и четвёртой - по 1.

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

Например, на первой дуге лежат 4 некритических работы, на замыкающем её отрезке критического пути А₀а₂А₂а₆А₆А_3,6а₇А₇ - 3 критических работы. Резерв времени, приходящийся на работу а₁, а₄, а₉, а₁₀ равен R_1,4,9,10=t₂+t₆+t₇-(t₁+t₄+t₉+t₁₀)=3+2+4-(2+1+4+1)=1.

Аналогично найдём резервы на остальных некритических дугах:

R_1,5,10=t₂+t₆+t₇-(t₁+t₅+t₁₀)=3+2+4-(2+4+1)=2

R₁₁=t₇+t₁₂-t₁₁=4+1-2=3

R₈=t₇-t₈=4-3=1.

Критические пути: a₃a₇a₁₂ и a₂a₆a₇a₁₂.

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

Пусть t₁,...,t_n - работы, t_i - время выполнения i-й работы.

Обозначим:

ES(i) - самый ранний момент, в который работа t_i может быть начата;

ET(i) - время возможного наиболее раннего окончания работы t_i;

LS(i) - время возможного наиболее позднего начала работы t_i.

LT(i) - время наиболее позднего завершения работы t_i.

Алгоритм.

1) Прямой просмотр работ (по таблице от начала до конца) для определения ES(i), ET(i)

2) Обратный просмотр (по таблице от конца до начала)

Определяем - время выполнения всего проекта.

Критические работы i, тогда Резерв(i)=0.

Пример.

Расчет для проекта, представленного в Табл.1:

№	Пред. работы	Длит. выпол.	ES(i)	ET(i)	LS(i)	LT(i)	Резерв
1	—	2	0	2	1	3	1
2	—	3	0	3	0	3	0
3	—	5	0	5	0	5	0
4	1	1	2	3	3	4	1
5	1	4	2	6	4	8	2
6	2	2	3	5	3	5	0
7	3,6	4	5	9	5	9	0
8	3	3	5	8	6	9	1
9	4	4	3	7	4	8	1
10	5,9	1	7	8	8	9	1
11	6	2	5	7	8	10	3
12	7,8,10	1	9	10	9	10	0

Табл.2