3.11. Динамическое программирование в задачах сетевого планирования

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

—               разработку технико-экономического обоснования;

—               разработку проектно-сметной документации;согласование проекта с различными контролирующими органи­зациями;

—               получение участка земли в органах муниципальной или феде­ральной власти;

—               выбор подрядчиков на выполнение отдельных работ;

—               получение кредитов в банке;

—               строительство производственных корпусов;

—               проведение отделочных и монтажных работ;

—               подведение и подключение коммуникаций;

—               прием в опытную и промышленную эксплуатацию.

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

—               формировать обоснованный календарный план выполнения ра­бот, заблаговременно заключать договоры и контракты со смеж­ными организациями;

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

—               рационально распоряжаться финансовыми, материальными, тру­довыми и иными ресурсами;

—               выявлять наиболее ответственные и напряженные участки работ и концентрировать внимание руководства на их состоянии;

—               оперативно принимать оптимальные решения при возникновении нештатных ситуаций;

—               использовать ЭВМ для контроля и оптимизации порядка вы­полнения комплекса работ.

В настоящем разделе будут рассмотрены лишь основные понятия и простейшие задачи сетевого планирования, при решении которых непосредственно используются методы ДП на графах. Другие харак­терные задачи, в частности, построение сетевых графиков и их оп­тимизация, в настоящем учебном пособии не рассматриваются. Для более полного ознакомления с методами сетевого планирования следует обратиться, например, к источникам [7, 8, 11, 13, 15, 18].

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

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

В сетевом планировании используется ряд специальных терминов, отражающих экономическое содержание данной предметной области. Первичными понятиями сетевого планирования являются события и ра­боты. Событие представляет собой некоторый момент времени, харак­теризующий состояние комплекса работ. События не имеют временной протяженности. Обозначаются события, как правило, натуральными числами 1,2,... или каким-либо иным образом. На сетевом графике события изображаются вершинами сети. Работа представляет собой некоторый процесс, требующий затрат времени и некоторых ресурсов на выполнение. Работа всегда связывает два события: начальное и ко­нечное по отношению к данной работе. Обозначаются работы парой чисел (г, -}) по номерам начального и конечного событий. На сетевом графике работы изображаются дугами. Время выполнения работы (г, з) будем называть длительностью работы и обозначать через Т(г,з)] это число можно трактовать как вес дуги (г,^), представляющей со­ответствующую работу.

Отдельные элементы сетевого графика могут быть связаны отно­шениями предшествования. Если (г,]) — некоторая работа, то:

—               событие г предшествует событию j, или событие ] следует за событием г;

—               событие г предшествует работе (г,;/), или работа (г,]) следует за событием г;

—               работа (1,]) предшествует событию з, или событие ] следует зг работой (г,з).

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

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

Событие, не имеющее предшествующих работ и представляющее начало всего комплекса работ, называется исходным и обозначаете? через I (что соответствует истоку сети). Событие, не имеющее по следующих работ и представляющее конец всего комплекса работ, на­зывается завершающим и обозначается через Р (что соответствует стоку сети). Будем полагать, что в рассматриваемых нами сетевых графиках имеется только одно исходное и одно завершающее событие.

Путь на сетевом графике определяется естественным образом как последовательность работ, соединяющая два события. Путь от собы­тия г к событию ] будем обозначать через Ь(г,])\ таких путей может быть несколько, один или ни одного. Суммарное время выполнения всех работ пути называется длиной, или протяженностью пути. Длину пути       будем обозначать через Т(Ь(г,])).

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

Т_кр=тах_№(/,_Л)},

где максимум длин путей Т(Ь(1,Р)) берется по всем полным путям Ь(1,Р). События и работы, располагающиеся на критическом пути, называются критическими. Критический путь на сетевом графике зачастую обозначается двойными дугами вида «=>».

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

1)               методом перечисления путей;

2)               методом ДП на орграфах.

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

С задачей поиска критического пути тесно связана задача расчета временных параметров событий и работ. К временным параметрам событий относятся:

1)               ранний срок свершения события;

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

3)               резерв времени события.

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

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

«_р(г) = тах{Т(Д/,»))}_>

Щ,г)

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

=                                     + ^Т(М)}>

в которой максимум берется по всем событиям /г, предшествующим со­бытию г. Данная формула отвечает методу ДП и полностью аналогична рассмотренной выше формуле (4) предыдущего раздела, применяемой при расчете максимального пути «с начала». Расчет начинается с ис­ходного события I и условия tp(I) = 0, а заканчивается вычислением tp(F) для завершающего события Р, причем Т_кр = tp(F). В ходе вы­числений необходимо каким-либо образом запоминать предшествующи« событию г работы, на которых достигается вычисляемый максимум эти работы играют роль аналогов условно-оптимальных управление в классическом методе ДП и используются далее при построении кри­тического пути.

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

 

Данная таблица аналогична таблицам, используемым при решении задачи о кратчайшем или максимальном пути с проведением расче­тов в направлении «от начала к концу». Запоминать работы можно, например, расставляя пометки (в виде стрелок или засечек на соот­ветствующих дугах сети) либо отмечая в таблице знаками «/» пред­шествующие события. После завершения расчетов критический путь определяется как и в задаче о кратчайшем или максимальном пути, начиная с завершающего события.

Поздний срок свершения события i (будем обозначать его через t_n(i))—наиболее поздний момент времени, с которого все после­довательности работ, начинающиеся с события i и заканчивающиеся завершающим событием F, могут завершиться в пределах критического срока. Таким образом, поздний срок свершения события определяется из соотношения

t„(i)+ max{T(L(z,F))} = Т_кр,

L(i,F)

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

<п(г)= min {t_n(j) -T(i,j)},

jev+W

в которой минимум берется по всем событиям j, следующим за со­бытием г. Расчет начинается с завершающего события F и условия t_n(F) = Т_кр (критический срок уже известен после расчета ранних сроков), а заканчивается исходным событием I; при этом должно по­лучиться tyi(I) = 0. Заметим, что критический путь уже построен при расчете ранних сроков; следовательно, в ходе расчета поздних сроков нет необходимости запоминать последующие за событием i ра­боты, на которых достигается вычисляемый минимум.

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

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

Г (г) = £_п(г) - £_р(г).

При этом г(г) ^ 0, а критические события имеют нулевой резерв времени.

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

В заключение раздела покажем, каким образом может быть уста­новлена приведенная выше формула для расчета поздних сроков (в ней впервые среди формул подобного типа встречается знак «минус»). Для этого учтем, что любой путь Ь(г,Р) от текущего события г к заверша­ющему событию .Р¹ обязательно проходит через одно из последующих к г событий ] £ У₊(г)\ следовательно,

Максимумы обеих частей последнего равенства также' равны: та х{Т(£(г,^))} = тах,{Т(г,з) + Т (Ц?, Л)}.

Выделяя первую работу (г,^) на пути Ь(г,Р), преобразуем правую часть полученного равенства:

тах{Т(г,Я+ТТО,^))}= тах {тах[Т(м)+Т(1(^))}}-

Слагаемое Т(г,]) в правой части последнего равенства можно вынести за знак внутреннего максимума, поскольку оно не зависит от после­дующего пути L(j,F):

Таким образом, получаем соотношение

wax{T (L(i, F))} = m^{T(i,j) + тж{Т (L(j,F))}}.

По определению позднего срока свершения события имеем: tn(i) = T_Kp- max {T(L(i,F))}.

L{i,F)

С учетом полученного выше соотношения можно записать: tu(i) = т_кр - max {T(i,j) + таx{T(L(j,F))}}.

jeV+(i)                              L(3,F)

Используя общую формулу

—max{F(x)} = min{—

X                                          X

уже упоминавшуюся в гл. 1, получаем:

Ш = Т_кр+ min {-T(i,j) - тах {Т (L(j, F))}}.

jeV+(i)                                L(j,F)

Критический срок Т_кр не зависит от выбора промежуточного состояния j (z V₊(i), так что его можно внести под знак минимума:

tn(i) = min {Т_кр- max{T(L(j,F))} -T(i,j)}.

jeV+(i)                      L(j,F)

Поскольку

Ткр - max{T(L(j,F))}=*_n(j),

L{],F)

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