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). В ходе вычислений необходимо каким-либо образом запоминать предшествующи« событию г работы, на которых достигается вычисляемый максимум эти работы играют роль аналогов условно-оптимальных управление в классическом методе ДП и используются далее при построении критического пути.
Расчет ранних сроков свершения событий, критического срока и по иск критического пути можно сопровождать проведением записи на са мом сетевом графике или заполнением таблицы следующей структуры
Событие г |
Предшествующее событие к |
Длительность работы Т(М) |
Сумма *р (/1)+Т(М) |
Ранний срок |
... |
|
|
|
|
Данная таблица аналогична таблицам, используемым при решении задачи о кратчайшем или максимальном пути с проведением расчетов в направлении «от начала к концу». Запоминать работы можно, например, расставляя пометки (в виде стрелок или засечек на соответствующих дугах сети) либо отмечая в таблице знаками «/» предшествующие события. После завершения расчетов критический путь определяется как и в задаче о кратчайшем или максимальном пути, начиная с завершающего события.
Поздний срок свершения события i (будем обозначать его через tn(i))—наиболее поздний момент времени, с которого все последовательности работ, начинающиеся с события i и заканчивающиеся завершающим событием F, могут завершиться в пределах критического срока. Таким образом, поздний срок свершения события определяется из соотношения
t„(i)+ max{T(L(z,F))} = Ткр,
L(i,F)
где максимум берется по всем путям L(i,F) от события i до завершающего события F. Данная формула имеет отношение к трудоемкому методу перечисления путей. В то же время идеи, лежащие в основе метода ДП, позволяют получить иную существенно более эффективную методику вычисления поздних сроков, основанную на формуле
<п(г)= min {tn(j) -T(i,j)},
jev+W
в которой минимум берется по всем событиям j, следующим за событием г. Расчет начинается с завершающего события F и условия tn(F) = Ткр (критический срок уже известен после расчета ранних сроков), а заканчивается исходным событием I; при этом должно получиться tyi(I) = 0. Заметим, что критический путь уже построен при расчете ранних сроков; следовательно, в ходе расчета поздних сроков нет необходимости запоминать последующие за событием i работы, на которых достигается вычисляемый минимум.
Как и для ранних сроков, расчет поздних сроков свершения событий можно сопровождать проведением записи на самом сетевом графике или заполнением таблицы следующей структуры:
Событие г |
Последующее событие j |
Длительность работы T(i,j) |
Разность t„(j)-T(i,j) |
Поздний срок |
|
|
|
|
|
Данная таблица аналогична рассмотренным выше таблицам. |
Резерв времени события г (будем обозначать его через г(г)) — наибольший срок задержки события, не приводящий к нарушению критического срока. После вычисления ранних и поздних сроков резервы времени событий рассчитываются по формуле
Г (г) = £п(г) - £р(г).
При этом г(г) ^ 0, а критические события имеют нулевой резерв времени.
Отметим, что в отдельных случаях события на сетевых графиках обозначаются следующим образом, представленном на рис. 3.27. В таком обозначении указаны все временные параметры события.
|
В заключение раздела покажем, каким образом может быть установлена приведенная выше формула для расчета поздних сроков (в ней впервые среди формул подобного типа встречается знак «минус»). Для этого учтем, что любой путь Ь(г,Р) от текущего события г к завершающему событию .Р1 обязательно проходит через одно из последующих к г событий ] £ У+(г)\ следовательно,
Максимумы обеих частей последнего равенства также' равны: та х{Т(£(г,^))} = тах,{Т(г,з) + Т (Ц?, Л)}.
Выделяя первую работу (г,^) на пути Ь(г,Р), преобразуем правую часть полученного равенства:
тах{Т(г,Я+ТТО,^))}= тах {тах[Т(м)+Т(1(^))}}-
Слагаемое Т(г,]) в правой части последнего равенства можно вынести за знак внутреннего максимума, поскольку оно не зависит от последующего пути L(j,F):
Таким образом, получаем соотношение
wax{T (L(i, F))} = m^{T(i,j) + тж{Т (L(j,F))}}.
По определению позднего срока свершения события имеем: tn(i) = TKp- 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)
то окончательно получаем требуемую формулу для вычисления поздних сроков.
25 26 27 Наверх ↑