16.1. Оптимизация сетевой схемы программы

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

и сам растеряешься.

Н. И. Пирогов

Сетевая схема программы отображает взаимосвязь проектов.

Сетевая схема состоит из дуг и узлов. Дуге соответствует выполняемая работа (обозначается стрелкой); узлу — событие, т. е. состояние перед работой (обозначается кружком).

Исходные данные, необходимые для составления сети, представляют в форме таблицы, которая включает последовательность работ и продолжительность выполнения каждой работы (табл. 16.1).

Таблица 16.1 Описаниеработ Рабо

та Содержание Следует

после

работ Продолжи

тельность Обозна

чение Закупка и доставка оборудования - 1 1-2 а2 Разработка технологии - 2 1-3 д.( Монтаж и наладка оборудования я. 4 2-3 а\ Обучение рабочих-операторов Я, 3 2-4 аа Пуск линии в эксплуатацию атаЛ 6 3-4 На рис. 16.1 сети числа над дугами показывают продолжительность каждой работы, события обозначаются порядковыми номерами.

Рис. 16.1. Сетевая схема программы

Событие

Начало работ Оборудование получено

Технология разработана, оборудование отлажено Персонал обучен, производство запушено

Работа обозначается двумя индексами / —у, где / — номер события, после которого начинается работа,) — номер события, которым заканчивается работа (см. также табл. 16.2). Последовательность работ, в которой конец предыдущей работы совпадает по времени с началом последующей, называется путем (табл. 16.3).

Таблица 76.3 Описание путей Путь Последовательность работ Продолжительность работ 1 1-2-4 1+3 = 4 2 1-2-3-4 1 +4 + 6=11 3 1-3-4 2 + 6 = 8 Путь наибольшей продолжительности называют критическим (второй). Увеличение продолжительности работ критического пути приводит к более позднему наступлению конечного события. Работы, не лежащие на критическом пути, могут быть позже начаты или позже окончены, или иметь большую продолжительность без изменения срока окончания всех работ.

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

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

Так как третье событие может наступить после выполнения работ 2-3 и 1-3, запишем:

Гз>7;+?и=0 + 2 = 2, В. 5. Г3 > 2|

Т3>Тг+^ъ = 1 + 4 = 5, В, 5. ТЛ >5} значит, Г, - 5.

Аналогично найдем время наступления последнего события:

Окончательно время наступления событий будут равны Г, = 0; Г2 = 1; Тг5; Т= И (рис. 16.2).

Из рис, 16.2 видно, что резерв работы 1-3, который будем обозначать равен 5 — 2 = 3. Значит, работа 1-3 может бьпь начата не в начальный момент времени, а спустя 3 ед. времени или продолжаться на 3 ед. больше, чем первоначально предполагалось, т. е. может длить-

Рис. 16.2. Пример сети

ся 2 + 3 = 5 ед. без увеличения момента наступления конечного события «4».

Аналогично = Г4 — (Г2 + 11 — (1 + 3) = 7, т. е. продолжительность работы 2-4 может быть увеличена на 7 ед. Очевидно, что для работ критического пути резерв времени равен 0, т. е. 0[г = = 0.

Для третьего события можно записать

Тз " Г1 + *13 + Ли-

Отсюда (Г3-Г,)-?))3-Г13.

Выражение (Гя — Г,) записано в скобках, чтобы было наглядно видно, что это интервал времени между двумя последовательными событиями. И этот интервал за вычетом резерва ?>[3 равен продолжительности работы 1-3. В этой зависимости нам задана продолжительность работы ( - 2 (правая часть уравнения), остальные величины — искомые переменные. Если их обозначить:

Т г г Г) — х ' Т X ‘ Т “ Ь

-V 13 ?*13* 1 1* 13 и13’

то можно записать:

(х3-х;)-ххи=Ь>3 и получить линеиное уравнение с тремя неизвестными.

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

(Гг-т;)-л12=^;

(Га ) ^-13 =^1Э'

03 ~ Г_Л > ^73 ~~ Г23 >

(3'«-Га)-Дя=?и;

Эта система описывает топологию (структуру) нашей сети.

Если вместо t? подставить их известные (заданные) значения, получим;

Эта система структуры сети содержит пять линейных уравнений с девятью неизвестными. Значит, она имеет бесчисленное множество решений. Чтобы ее решить, надо добавить граничные условия и ЦФ.

При этом возможны две постановки задач оптимизации.

Первая постановка: задаемся временем начала работ, т. е. значением Г|7 например 7'1=0, и стремимся закончить комплекс работ как можно раньше:

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

Поста

новка

2 ЦФ Граничные Т - п Г, —>шах Г,-15 Обе постановки — это задачи линейного программирования, которые можно решить (табл. 16.4).

Та^тл! ю Л г, т

*1 Аи д.. 0 1 5 11 0 3 0 7 0 4 5 9 15 0 3 0 7 0 на +4 больше, чем в 1-й постановке Из таблицы видно, что резерв не зависит от постановки задачи. Времена окончания работ в первой постановке и начала работ во второй постановке определяются заданными граничными условиями.

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

В общем виде топология сети запишется:

(*) (Т. - Т.) - 01;=^(для всех г,

Если обозначить 5 — число событий, R — число работ, то система, описывающая сеть, будет включать п переменных, где п = + К, так как каждому 1-му событию соответствует неизвестная Т(, а каждой работе — неизвестная Д^ А число ограничений т = R, т. е. каждой работе соответствует ограничение.

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

Тогда общие постановки запишутся:

где 7Х,Т — заданные плановые сроки начала и окончания работ сети.

Например, для графика (рис. 16.3) из 11 событий и 20 работ (всего лишь) первая постановка при У" = 0 будет иметь вид:

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