Материал: УП - Методы оптимальных решений

29.	9	21	22	14	10	18		30.	12	15	9	19	22	40
	30	34	42	23	26	12			20	15	11	2	19	30
	8	17	30	27	9	20			21	26	23	7	16	25
	11	20	24	7	25	18			11	24	8	3	29	15
	14	11	17	15	14				34	39	24	8	8

7. Элементы сетевого планирования

7.1. Основные понятия

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

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

1. Они должны иметь только одно исходное событие (исток сети J) – начало работ комплекса;

2. Они должны иметь только одно завершающее событие (сток сети S) – окончание всех работ комплекса;

3. Прежде чем строить сеть, надо составить подробный спи­сок работ комплекса. В отношении каждой работы выяснить:

а) ее связи с другими работами;

б) ее место в комплексе;

в) ее конечные ре­зультаты (события).

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

Пример 29. По данным табл. 39 построить сеть.

Таблица 39

Обозначение работы	а1	а2	а3	а4	а5	а6	а7	а8	а9
Непосредственно предшест­вующие работы	–	–	–	а1	а1 а2	а1 а2	а3 а5	а4 а6 а7	а3 а5
Продолжительность работы	3	6	4	5	1	9	6	8	5

Решение: работы а₁, а₂, а₃ не имеют предшествующих, поэтому реа­лизация комплекса начинается с этих работ и изображаем их прямыми, выходящими из одного события 1 (исток J сети) (рис. 18).

Рис. 18

Дуги а₁, а₂, а₃ и так далее располагаются произвольно. Работе а₄ предшествует работа а₁. Далее надо изобразить работы а₅ и а₆, им предшествуют одни и те же работы а₁ и а₂. Во избежание путаницы на сетях не рекомендуется изображать параллельными дугами одновременно выполняемые работы. В подобных случаях вводятся дополнительные события и фиктивные работы (нулевой продолжительности), которые изображаются штриховыми линиями. Их назначение – показать, что данная работа не может быть выполнена ранее какого-либо события или работы. Учитывая это, введем фиктивную работу, соединив событие 2 работы а₁ с событием 3 работы а₂. После этого изобразим а₅ и а₆ дугами, выходящими из события 3, причем дуги а₃, а₅ должны прийти в одно событие (работа а₇ начинается после них), такое событие уже есть – это 4, а дуги а₄, а₆ аналогично идут в событие 5. Так как работа а₈ может быть начата только после работ а₄, а₆ и а₇, поэтому работу а₇ направим в событие 5. И, наконец, дуги а₈ и а₉ моделируют заключительные работы комплекса, поэтому сведем их в одно завершающее событие 6 (сток сети S).

Замечание. Правильность нуме­рации событий (вершин графа) можно проверить алгоритмом Фалкерсона (упорядочить граф).

7.2. Временные параметры сети (рассмотрим на примере)

Пример 30. Сеть некоторого комплекса построена и известна продолжительность каждой работы (в днях). Определить за ка­кое минимальное время можно выполнить все работы комплекса?

Решение.

Рассмотрим все пути от J до S (рис. 19).

Рис. 19

1) L₁: 1 – 2 – 4 – 5 => t(L₁) = 2 + 1 + 5 = 8;

2) L₂: 1 – 3 – 4 – 5; => t(L₂) = 4 + 3 + 5 = 12;

3) L₃: 1 – 3 – 5 => t(L₃) = 4 + 2 = 6.

Наиболее продолжительным оказался путь L₂. Его называют кри­тическим. Он и определяет максимальное время выполнения всех работ данного комплекса. Это максимальное время называют критическим сроком и обозначают t_КР. Итак t_КР = 12. Работы и события, лежащие на критиче­ском пути называются критическими, остальные работы и события сети – некритическими. Если выполнение какой-либо критической работы будет задержано, это вызовет задержку выполнения всего комплекса на тот же срок. Однако, некритические работы допускают некоторое запаздывание их выполнения без нарушения критического срока. Чтобы определить время, на которое можно задержать выполнение некритических работ, введем понятие резерва времени событий и работ.

П

i

од свершением события будем понимать момент времени, к которому за­канчиваются все входящие в него работы. Событие может иметь не­который интервал свободы свершения. Поясним это: событие 2 может свершиться через 2 дня по окончании работы (1 – 2). Но оно может наступить и позже, если доба­вить время из резерва на выполнение работы (1 – 2), а это сделать можно, так как на пути L₁ есть резерв времени R(L₁) = t_КР – t(L₁) = 12 – 8 = 4. Поэтому работу (1 – 2) можно выполнить и за 2 + 4 = 6 дней, и это не повлияет на критический срок. Следовательно, для события различают ранний и поздний сроки свершения. Ранним сроком t_p(j) свершения события j назовем самый ранний период времени, к которому завершаются все работы, предше­ствующие этому событию. Получаем формулу t_p (j) = max (t_p(i) + t(i, j)), где i, j – мно-

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

Тогда имеем t_p (1) = 0, t_p (5) = t_КР = 12 (и вообще t_p (J) = 0, а t_p (S) = t_КР). Тогда t_p (2) = 2 или t_p (2) = 0 + 2 = t_p (1) + t(1, 2), где t(1, 2) – время вы­полнения работы (1 – 2). Аналогично t_p (3) = 0 + 4 = t_p (1) + t(1,3). Для события 4: по работе (2 – 4) имеем t_p (2) + t(2, 4) = 2 + 1 + 3, а по работе (3 – 4) => t_p (3) + t(3, 4) = 4 + 3 = 7, так как к моменту t_p (4) должны закончиться все предшествую­щие работы, тогда t_p (4) = max (t_p (2) + t(2, 4); t_p (3) + t(3, 4)) = max (3; 7) = 7.