Оптимизация сетевого графика методом “время – стоимость”.

Обозначим а_ij – минимально возможное время выполнения работы (i,j), которому соответствуют затраты с^а_ij; b_ij – максимально возможное время выполнения работы (i,j), которому соответствуют затраты с^b_ij. Предполагается, что ускорение работы связано с дополнительными затратами (на привлечение дополнительной рабочей силы и оборудования, сверхурочные доплаты и т.п.). Имеем

а_ij £ t_ij £ b_ij ,

с^b_ij £ с_ij £ с^а_ij; (26)

с_ij – затраты, соответствующие времени выполнения t_ij.

Пусть зависимость затрат от времени выполнения линейная, т.е.

с_ij =z_ij – y_ijt_ij ,

откуда, используя (26), получаем выражение для коэффициента пропорциональности

y_ij = (с^а_ij – с^b_ij)/(b_ij – а_ij)=Dс/Dt. (27)

Таким образом, y_ij характеризует затраты, связанные с сокращением продолжительности работы на единицу времени. Будем называть y_ij – “ценой” сокращения работы на единицу времени.

Если на всех работах принять t_ij = а_ij, то будет получено наименьшее критическое время Т^кр_min. Этому времени соответствуют наибольшие затраты, равные С_а = å_"(i,j) с^а_ij;

Если на всех работах принять t_ij = b_ij, то мы получим сетевой график, которому соответствуют наименьшие затраты, равные С_b = =å_"(i,j) с^b_ij, и наибольшее критическое время Т^кp_max.

При наименьшем критическом времени Т^кр_min можно уменьшить затраты, если «удлинить» некритические работы за счет их резервов времени. Ведь увеличение t_ij на единицу снижает ее стоимость на y_ij. Обозначим эти затраты через С_d, тогда можем утверждать, что для Т= Т^кр_min минимальная стоимость равна С_d, и, в общем случае, для любого ТÎ[Т^кр_min ,Т^кр_mах] существует план с минимальными затратами С(Т). График функции С(Т) приведен на рис 15.

С

С_а

С_d С(Т)

С_b

Рис 15.

Т^кр_min Т^кр_mах

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

Если затраты линейно зависят от продолжительности работ, как мы выше предположили, то нахождение С(Т) можно свести к решению задачи линейного программирования вида:

Найти такие продолжительности работ – t_ij, что

1. Т_j – Т_i – t_ij ≥ 0, для всех работ (i, j);

2. а_ij £ t_ij £ b_ij ,

3. T_n⁰ £ Т,

4. С(Т)=å_"(i,j) с_ij =å_"(i,j) (z_ij – y_ijt_ij ) ® min, что эквивалентно

å_"(i,j) y_ijt_ij ® mах.

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

10 13Цифры над работами

16 6 8 10 означают

4 30 18 11 с^а_ij с^b_ij

^{15 21} а_ij b_ij

Рис.16.

Примем t_ij = а_ij (выделено жирным шрифтом), тогда Т^кр_min = 15,

С_а = å_"(i,j)с^а_ij=16+13+30=59, R^п₁₂=3, R^п₂₃=3, R^п₁₃=0. Определим цены сокращения работ на единицу, согласно (27) имеем:

y₁₂=(16 – 10)/(6 – 4)=3, y₁₃=(30 – 18)/(21–15)=2, y₂₃=(13–10)/(11– 8)=1,

т.е. увеличение продолжительности работы (1,2) на единицу удешевляет ее на 3 и т.д. Увеличим продолжительность некритических работ (1,2), (2,3) в пределах их полных резервов (т.к. они находятся на одном пути, то полный резерв у них общий). Если увеличить продолжительность работы (2,3) на 3, то это удешевит первоначальный план на 3y₂₃=3, если же удлинить работу (1,2), а ее можно удлинить только на 2 дня, то стоимость уменьшится на 2y₁₂=6, и еще на 1 можно будет увеличить продолжительность работы (2,3), что даст экономию еще на 1, – всего сокращение стоимости составит 6+1=7. Мы получили самый дешевый план при Т^кр_min = 15, стоимость которого С_d =59 – 7=52. И мы получили общее правило для выбора работ – приоритетом является «цена» сокращения.

Мы рассматривали зависимости между затратами и временем выполнения работы, имея в виду лишь прямые затраты, поскольку выявить изменение косвенных (накладных) расходов от изменения продолжительности отдельной работы весьма затруднительно.

Косвенные затраты существенно зависят от времени завершения всей программы в целом, причем известно, что с увеличением срока выполнения проекта косвенные затраты возрастают.

В предположении линейной зависимости косвенных затрат от срока завершения проекта (что отображено на рис.17 прямой LN) оптимальному плану (с учетом прямых и косвенных затрат) будет соответствовать точка М.

С график функции суммарных

прямых и косвенных

С_d ^M затрат

С_b

_N

_L Рис 17.

Т^кр_min Т_опт Т^кр_mах

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

Будем трактовать с^а_ij как количество исполнителей, необходимое для выполнения работы (i,j) в минимально возможное время а_ij; соответственно с^b_ij – количество исполнителей, необходимое для выполнения работы (i,j) в максимально возможное время b_ij.

Имеем аналогичные (8.2) соотношения

а_ij £ t_ij £ b_ij ,

с^b_ij £ с_ij £ с^а_ij,

где с_ij – количество исполнителей, соответствующее времени выполнения t_ij.

В рассматриваемой задаче “цена” сокращения y_ij вычисляется также по формуле (27) и показывает, сколько исполнителей надо добавить, чтобы сократить время выполнения работы на единицу времени. Рассмотрим пример (рис. 18).

обозначения

12 11 3 5

6 6 6 y_ik

4 8 5 10 3 8 а_ik b_ik

10 4

Рис.18

Пусть заданное время Т=22. Поставим на каждую работу минимально возможное количество исполнителей, тогда продолжительности работ будут максимальные, т.е. t_ik = b_ik. Время выполнения всего проекта в данном случае будет 8+10+8=26 (длина другого пути 8+11+6=25), что на 4 единицы больше заданного времени.

Кажется естественным найти на критическом пути работу с наименьшей ценой сокращения (это будет работа (4,5)) и сократить ее продолжительность на 4 единицы, что потребует дополнительно 3*4=12 исполнителей. Теперь другой путь стал критическим, и наименьшая цена сокращения у работы (3,5). Для сокращения ее продолжительности на 3 единицы потребуется дополнительно 5*3=15 исполнителей, таким образом, всего понадобится дополнительно 12+15=27 исполнителей.

Однако существует лучшее решение. Работу (1,2), которая является общей для обоих путей, сократим на 4 единицы времени. Это потребует 6*4=24 дополнительных исполнителей. Т^кр=Т=22.

Еще более эффективное решение может быть получено следующим образом: работу (1,2) сокращаем на 3 единицы, что потребует дополнительно 6*3=18 исполнителей, и работу (4,5) на 1 единицу с привлечением дополнительно 3*1=3 человек. Получили Т^кр=Т=22, число дополнительных рабочих 18+3=21.

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

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

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

Кроме того, критерий эффективности – “суммарная интенсивность выполнения работ” – представляет собой сумму интенсивностей потребления ресурсов различного вида на работах, выполняемых в различные промежутки времени. Относительная дефицитность ресурсов различных видов значительно изменяется во времени в зависимости от производственной ситуации, складывающейся на всем множестве объектов, питаемых ресурсами из одного “резервуара”. Поэтому возможна ситуация, при которой в некоторый период времени легче, например, добавить 50 отделочников, чем 10 монтажников.

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

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

4.5. Многопроектные задачи сетевого планирования с учетом ограниченности ресурсов и сроков.

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

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

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

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

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

В зависимости от специфики проекта применяются следующие критерии:

f= f₁+f₂w®min,

где w – коэффициент взвешивания цели; w предполагается существенно меньшим единицы.

Первое слагаемое целевой функции f₁ определяет меру соответствия полученных при временном расчете сроков ввода объектов директивным срокам для объектов zÎМ₁ – подлежащих вводу в планируемый период.

Второе слагаемое f₂ определяет меру соответствия выполнения объемов работ по задельным объектам zÎМ₂ согласно выделенным ассигнованиям.

При достаточно малом значении взвешивающего коэффициента w (w<<1) влияние второго слагаемого целевой функции на расписание работ по объектам zÎМ₁ неощутимо, что соответствует принципу концентрации ресурсов на сдаточных объектах.

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

Пусть Т_z* – расчетный срок ввода объекта z, Т_z^дир – директивный срок, тогда мера соответствия расчетных сроков ввода объектов директивным может быть выражена с помощью следующих функций:

f₁=å_zÎМ1[Т_z*– Т_z^дир], (28)

f₁=å_zÎМ1[Т_z*– Т_z^дир]², (29)

f₁=å_zÎМ1 êТ_z*– Т_z^дирê, (30)

f₁=å_zÎМ11[Т_z*– Т_z^дир], (31)

где М₁₁ÌМ₁–множество объектов, для которых получено Т_z*> Т_z^дир,

f₁=å_zÎМ1[Т_z*– Т_z^дир]x^z, (32)

где x^z ₌ x₁^z для zÎМ₁₁,

x₂^z для zÎМ₁₂

(М₁₂ÌМ₁ – множество объектов, для которых получено Т_z* < Т_z^дир),

f₁=мах_zÎМ1[Т_z*– Т_z^дир]. (33)

Коэффициенты x₁^z, x₂^z характеризуют соответственно потери или прибыль от задержки или досрочного ввода объекта в эксплуатацию.

В случае критерия (28) оптимальный план, которому соответствует минимальная алгебраическая сумма отклонений, допускает форсирование строительства одних объектов за счет других.

Критерий (29) является одной из лучших мер равномерности. Однако, использование этой функции не всегда целесообразно, так как она в равной мере оценивает как досрочный ввод, так и превышение директивного срока, что не совсем соответствует действительности.

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

Функции (31) присущи те же недостатки, что и (28), но в существенно меньшей степени, что определяет допустимость использования такого критерия для решения практических задач.

Функция (32) наилучшим образом отвечает специфике строительного производства. Однако, использование критерия такого вида предполагает обоснованное определение для каждого объекта коэффициентов x₁^z, x₂^z.

Функция (33) достаточно хорошо характеризует степень достижения основных целей строительной организации. И хотя экономическое «содержание» этой функции беднее, чем у (32), сравнительная простота алгоритмов решения задач на минимум максимального превышения расчетных сроков над директивными предопределяет ее выбор для практического использования.

Функция f₂ может принимать выражения, аналогичные (28)-(33), где множество М₁ заменено на М₂, Т_z*– на Т_z^**( Т_z^** срок завершения фрагмента сети, состоящей из работ объекта z, упорядоченных по возрастанию поздних сроков их начала, суммарная сметная стоимость которых равна выделенным ассигнованиям на данный объект), Т_z^дир на Т^пл. В силу принятых обозначений условие выполнения заданного объема работ в стоимостном выражении по объекту zÎМ₂ в течение планируемого периода может быть представлено как Т_z^** £ Т^пл.