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

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

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

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

разработку проектно-сметной документации;

согласование проекта с различными контролирующими организациями;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В сетевом планировании используется ряд специальных терминов,

отражающих экономическое содержание данной предметной области.

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

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

числами 1,2,... или каким-либо иным образом. На сетевом графике

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

некоторый процесс, требующий затрат времени и некоторых ресурсов

на выполнение. Работа всегда связывает два события: начальное и конечное по отношению к данной работе. Обозначаются работы парой

чисел по номерам начального и конечного событий. На сетевом

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

будем называть длительностью работы и обозначать через T(i,j);

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

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

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

событие г предшествует работе или работа следует

за событием г;

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

Если при этом (j, к) также является работой, то говорят, что работа предшествует работе (j,k), или работа (j, к) следует зг

работой (г, j). Предшествующая работа для некоторой другой работь:

называется опорной работой.

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

Событие, не имеющее предшествующих работ и представляющее начало всего комплекса работ, называется исходным и обозначаете? через / (что соответствует истоку сети). Событие, не имеющее ПО следующих работ и представляющее конец всего комплекса работ, на

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

Путь на сетевом графике определяется естественным образом как последовательность работ, соединяющая два события. Путь от события і к событию j будем обозначать через L(i,j); таких путей может быть несколько, один или ни одного. Суммарное время выполнения всех работ пути называется длиной, или протяженностью пути. Длину пути L(i,j) будем обозначать через T(L(i,j)).

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

^кр= max{T(L(/,F))},

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

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

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

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

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

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

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

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

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

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

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

tp(i) = mfx{T(L(I,i))},

Ь(1,г)

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

*р(») = max {tp(fc) + T(M)},

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

Ранний срок

Длительность работы T(h,i)

Сумма tp(h) + T(h,i

Событие і

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