Сетевое планирование и управление (стр. 1 )

2. СЕТЕВОЕ ПЛАНИРОВАНИЕ И УПРАВЛЕНИЕ

2.1. Построение сетевого графика экономического процесса

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

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

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

Если все соединения в графе изображаются дугами, то граф называется ориентированным, или орграфом.

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

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

Контур с одной вершиной - петля.

Вершина, из которой дуги только выходят, но не входят, называется истоком.

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

Любой путь от истока к стоку называется полным.

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

Вершина ("предок") предшествует в графе вершине ("потомок"), если существует путь из в .

Граф является упорядоченным, если в нем порядковый номер "предка" всегда меньше порядкового номера "потомка".

Графический способ упорядочения графа реализуется по алгоритму Фалкерсона:

1-ый шаг) выделяем вершины, не имеющие "предков", и последовательно нумеруем их в произвольном порядке;

2-ой шаг) мысленно вычеркиваем из графа все вершины, имеющие номера, и дуги, из них выходящие;

3-ий шаг) в получившемся графе повторяем процедуры 1-ого и 2-ого шагов до тех пор, пока все вершины не будут пронумерованы.

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

Сетевой график - это связанный упорядоченный взвешенный орграф без контуров (петель).

На изображении с помощью сетевого графика основано сетевое планирование и управление (СПУ).

Основными понятиями СПУ являются работа и событие.

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

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

Подготовка исходных данных для построения сетевого графика включает:

-  определение начального и конечного событий;

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

-  составление списка работ, соединяющих намеченные события;

-  определение продолжительности выполнения каждой работы.

При построении сетевого графика для СПУ должны учитываться следующие четыре правила:

-  график должен иметь только одно начальное событие (исток) и только одно конечное событие (сток);

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

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

-  график должен быть упорядоченным.

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

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

-  критический путь;

-  резервы времени событий;

-  резервы времени работ.

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

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

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

Пример

Определение критического пути в сетевом графике:

Полные пути и их продолжительности:

1)  5 Þ 2+3+5+6=16;

2)  Þ 2+9+6=17; критический срок (путь)

3)  Þ 4+5+6=15.

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

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

Ранний срок свершения события - это ранний срок, необходимый для выполнения всех работ, предшествующих данному событию:

где - ранний срок свершения события ;

- продолжительность работы;

- множество работ, входящих в событие .

Пример

Определение ранних сроков свершения событий в сетевом графике:

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

,

где - поздний срок свершения события ;

- продолжительность работы ;

- множество работ, выходящих из события .

Пример

Определение поздних сроков свершения событий в сетевом графике:

Тогда резерв времени события равен:

.

Пример

Определение резервов времени событий в сетевом графике:

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

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

.

Пример

Определение полных резервов времени работ в сетевом графике:

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

.

Пример

Определение свободных резервов времени работ в сетевом графике:

Получается, что резерв времени события связан с резервами времени входящей в него работы следующим образом:

.

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

Резервы времени критических событий и критических работ равны нулю.

2.3. Оптимизация сетевого графика комплекса работ

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

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

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

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

-  минимизация времени выполнения комплекса работ при заданных затратах на это выполнение;

-  минимизация затрат на выполнение комплекса работ при заданном времени этого выполнения.

Таким образом, нельзя добиться выполнения комплекса работ одновременно в минимальные сроки и с наименьшими затратами.

Пример

Построен взвешенный график выполнения работ.

Веса означают: первый вес - нормальный срок, второй вес - ускоренный срок.

Упорядочим график по алгоритму Фалкерсона:

В итоге, построим сетевой график выполнения работ.

Проведем анализ сетевого графика:

Полные пути	Продолжительность (сутки)
Нормальный режим	Ускоренный режим
1 – 2 – 4 – 6	19	13
1 – 2 – 5 – 6	20	11
1 – 3 - 6	22	11

Таким образом, наименьшая продолжительность выполнения всего комплекса работ не может быть меньше 13 суток.

Заданы два варианта (нормальный и ускоренный) выполнения работ и связанных с ними затрат:

Работы	Нормальный вариант	Ускоренный вариант	Прирост затрат на одни сутки ускорения
Время (сутки)	Затраты (у. е.)	Время (сутки)	Затраты (у. е.)
1 - 2	4	100	3	120	20
1 - 3	10	150	5	225	15
2 - 4	6	50	4	100	25
2 - 5	5	70	2	100	10
3 - 6	12	250	6	430	30
4 - 6	9	180	6	300	40
5 - 6	11	260	6	435	35
	ВСЕГО	1060	ВСЕГО	1710

Требуется оптимизировать по критерию минимизации затрат сетевой график при заданной продолжительности выполнения всего комплекса работ за 13 суток.

Оптимизацию можно провести двумя способами.

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

Представим алгоритм решения поставленной оптимизационной задачи первым способом в таблице:

№ шага	Суточный прирост затрат	Работа	Количество сокращаемых суток	Продолжительность полного пути	Общий прирост затрат
1-2-4-6	1-2-5-6	1-3-6
0	-	-	-	19	20	22	-
1	10	2-5	3	-	17	-	+30
2	15	1-3	5	-	-	17	+75
3	20	1-2	1	18	16	-	+20
4	25	2-4	2	16	-	-	+50
5	30	3-6	4	-	-	13	+120
6	35	5-6	3	-	13	-	+105
7	40	4-6	3	13	-	-	+120
В С Е Г О	+520

Итак, при снижении продолжительности выполнения всего комплекса работ с 22 суток до 13 суток оптимальные затраты составляют 1060+520=1580 (у. е.).

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

Представим алгоритм решения поставленной оптимизационной задачи вторым способом в таблице:

№ шага	Суточный прирост затрат	Работа	Количество наращиваемых суток	Продолжительность полного пути	Общее снижение затрат
1-2-4-6	1-2-5-6	1-3-6
0	-	-	-	13	11	11	-
1	40	4-6	-	13	-	-	-
2	35	5-6	2	-	13	-	-70
3	30	3-6	2	-	-	13	-60
В С Е Г О	-130

Итак, при повышении продолжительности выполнения всего комплекса ускоренного режима работ до 13 суток оптимальные затраты составляют =1580 (у. е.).

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

Выводы по второму разделу

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

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

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

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

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

Вопросы для самопроверки

- Как можно представить наглядно граф?

- Какой граф называется орграфом?

- Что называется путем в орграфе?

- Какая вершина называется истоком, а какая – стоком?

- Какой путь называется полным?

- Какой граф называется взвешенным?

- Какой граф является упорядоченным?

- Какой граф называется связанным?

- Что представляет собой сетевой график?

- Что понимается под работой и событием и как они обозначаются на сетевом графике?

- Что включают основные параметры сетевого графика?

- Какой из полных путей называется критическим?

- Что показывает резерв времени события?

- Что означают ранний и поздний сроки свершения события?

- Чему равен резерв времени события?

- Какие бывают резервы времени работы?

- Что показывают полный и свободный резервы времени работы?

- Как выражается резерв времени события через резервы времени входящей в него работы?

- Какое численное значение имеют резервы времени критических событий и критических работ?

- По каким критериям может осуществляться оптимизация сетевого графика?

- Какими способами можно провести оптимизацию сетевого графика?

Примеры решения задач

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

События (предки)	начало работ	готовность деталей	готовность документации	поступление дополнительного оборудования	готовность блоков
События (потомки)
готовность деталей			составление инструкций (11/6)	изготовление деталей (4/3)
готовность документации				подготовка документации (5/2)
поступление дополнительного оборудования	закупка дополнительного оборудования (10/5)
готовность блоков		сборка блоков (6/4)
готовность изделия			установка дополнительного оборудования (12/6)		компоновка изделия (9/6)

Работы	Нормальный вариант	Ускоренный вариант	Прирост затрат на одни сутки ускорения
Время (сутки)	Затраты (у. е.)	Время (сутки)	Затраты (у. е.)
изготовление деталей	4	100	3	120	20
закупка дополнительного оборудования	10	150	5	225	15
сборка блоков	6	50	4	100	25
подготовка документации	5	70	2	100	10
установка дополнительного оборудования	12	250	6	430	30
составление инструкций	11	260	6	435	35
компоновка изделия	9	180	6	300	40

Требуется оптимизировать по критерию минимизации затрат сетевой график при заданной продолжительности выполнения всего комплекса работ за 25 суток.

Решение.

Построим сетевой график. Для этого пронумеруем события и тем самым работы.

События (предки)	начало работ (1)	готовность деталей	готовность документации	поступление дополнительного оборудования	готовность блоков
События (потомки)
готовность деталей			составление инструкций (11/6)	изготовление деталей (4/3)
готовность документации				подготовка документации (5/2)
поступление дополнительного оборудования	закупка дополнительного оборудования (10/5)
готовность блоков		сборка блоков (6/4)
готовность изделия (6)			установка дополнительного оборудования (12/6)		компоновка изделия (9/6)

События (предки)	начало работ (1)	готовность деталей	готовность документации	поступление дополнительного оборудования (2)	готовность блоков
События (потомки)
готовность деталей			составление инструкций (11/6)	изготовление деталей (4/3)
готовность документации				подготовка документации (5/2)
поступление дополнительного оборудования (2)	закупка дополнительного оборудования (10/5)
готовность блоков		сборка блоков (6/4)
готовность изделия (6)			установка дополнительного оборудования (12/6)		компоновка изделия (9/6)

События (предки)	начало работ (1)	готовность деталей (4)	готовность документации (3)	поступление дополнительного оборудования (2)	готовность блоков
События (потомки)
готовность деталей (4)			составление инструкций (11/6)	изготовление деталей (4/3)
готовность документации (3)				подготовка документации (5/2)
поступление дополнительного оборудования (2)	закупка дополнительного оборудования (10/5)
готовность блоков		сборка блоков (6/4)
готовность изделия			установка дополнительного оборудования (12/6)		компоновка изделия (9/6)

События (предки)	начало работ (1)	готовность деталей (4)	готовность документации (3)	поступление дополнительного оборудования (2)	готовность блоков (5)
События (потомки)
готовность деталей (4)			составление инструкций (11/6)	изготовление деталей (4/3)
готовность документации (3)				подготовка документации (5/2)
поступление дополнительного оборудования (2)	закупка дополнительного оборудования (10/5)
готовность блоков (5)		сборка блоков (6/4)
готовность изделия (6)			установка дополнительного оборудования (12/6)		компоновка изделия (9/6)

Проведем анализ сетевого графика:

Полные пути	Продолжительность (сутки)
Нормальный режим	Ускоренный режим
1 – 2 – 3 – 6	27	13
1 – 2 – 4 – 5 - 6	29	18
1 – 6	41	23

Представим алгоритм решения поставленной оптимизационной задачи первым способом в таблицах:

№ шага	Суточный прирост затрат	Работа	Количество сокращаемых суток (максимально возможное)	Продолжительность полного пути	Общий прирост затрат
1-2-3-6
0	-	-	-	27	29	41	-
1	10	2-3	(3)
2	15	1-2	(5)
3	20	2-4	(1)
4	25	4-5	(2)
5	30	3-6	(6)
6	35	3-4	(5)
7	40	5-6	(3)
В С Е Г О

№ шага	Суточный прирост затрат	Работа	Количество сокращаемых суток (максимально возможное)	Продолжительность полного пути	Общий прирост затрат
1-2-3-6		1-2-3-4-5-6
0	-	-	-	27	29	41	-
1	10	2-3	(3) 3	24	-	38	30
2	15	1-2	(5)
3	20	2-4	(1)
4	25	4-5	(2)
5	30	3-6	(6)
6	35	3-4	(5)
7	40	5-6	(3)
В С Е Г О

№ шага	Суточный прирост затрат	Работа	Количество сокращаемых суток (максимально возможное)	Продолжительность полного пути	Общий прирост затрат
1-2-3-6	1-2-4-5-6	1-2
0	-	-	-	27	29	41	-
1	10	2-3	(3) 3	24	-	38	30
2	15	1-2	(5) 5	19	24	33	75
3	20	2-4	(1)
4	25	4-5	(2)
5	30	3-6	(6)
6	35	3-4	(5)
7	40	5-6	(3)
В С Е Г О

№ шага	Суточный прирост затрат	Работа	Количество сокращаемых суток (максимально возможное)	Продолжительность полного пути	Общий прирост затрат
1-2-3-6	1-2-4-5-6
0	-	-	-	27	29	41	-
1	10	2-3	(3) 3	24	-	38	30
2	15	1-2	(5) 5	19	24	33	75
3	20	2-4	(1) -	-	-	-	-
4	25	4-5	(2)
5	30	3-6	(6)
6	35	3-4	(5)
7	40	5-6	(3)
В С Е Г О

№ шага	Суточный прирост затрат	Работа	Количество сокращаемых суток (максимально возможное)	Продолжительность полного пути	Общий прирост затрат
1-2-3-6	1-2-4-5-6	1-2-3-4-5-6
0	-	-	-	27	29	41	-
1	10	2-3	(3) 3	24	-	38	30
2	15	1-2	(5) 5	19	24	33	75
3	20	2-4	(1) -	-	-	-	-
4	25	4-5	(2) 2	-	22	31	50
5	30	3-6	(6)
6	35	3-4	(5)
7	40	5-6	(3)
В С Е Г О

№ шага	Суточный прирост затрат	Работа	Количество сокращаемых суток (максимально возможное)	Продолжительность полного пути	Общий прирост затрат
1-2-3-6
0	-	-	-	27	29	41	-
1	10	2-3	(3) 3	24	-	38	30
2	15	1-2	(5) 5	19	24	33	75
3	20	2-4	(1) -	-	-	-	-
4	25	4-5	(2) 2	-	22	31	50
5	30	3-6	(6) -	-	-	-	-
6	35	3-4	(5)
7	40	5-6	(3)
В С Е Г О

№ шага	Суточный прирост затрат	Работа	Количество сокращаемых суток (максимально возможное)	Продолжительность полного пути	Общий прирост затрат
1-2-3-6		1-2-3-4-5-6
0	-	-	-	27	29	41	-
1	10	2-3	(3) 3	24	-	38	30
2	15	1-2	(5) 5	19	24	33	75
3	20	2-4	(1) -	-	-	-	-
4	25	4-5	(2) 2	-	22	31	50
5	30	3-6	(6) -	-	-	-	-
6	35	3-4	(5) 5	-	-	26	175
7	40	5-6	(3)
В С Е Г О

№ шага	Суточный прирост затрат	Работа	Количество сокращаемых суток (максимально возможное)	Продолжительность полного пути	Общий прирост затрат
1-2-3-6	1-2-4-5-6	5-6
0	-	-	-	27	29	41	-
1	10	2-3	(3) 3	24	-	38	30
2	15	1-2	(5) 5	19	24	33	75
3	20	2-4	(1) -	-	-	-	-
4	25	4-5	(2) 2	-	22	31	50
5	30	3-6	(6) -	-	-	-	-
6	35	3-4	(5) 5	-	-	26	175
7	40	5-6	(3) 1	-	21	25	40
В С Е Г О	370

Итак, при снижении продолжительности выполнения всего комплекса работ с 41 суток до 25 суток оптимальные затраты составляют 1060+370=1430 (у. е.).