Сетевые модели с учетом ресурсов

А. Значение решаемых задач

На технологических моделях этого типа решаются так называемые ресурсные задачи, т. е. информационные задачи учета потребных ресурсов либо задачи рационального распределения ресурсов (см. с. 65). Классификация ресурсов с с точки зрения решаемых в процессе календарного планирования задач, их разделение на складируемые и нескладируемые достаточно полно раскрыты в гл. 4. Там же приведены способы фиксации потребности в ресурсах отдельных работ и комплекса в целом, учета наличия ресурсов, а также подробно охарактеризованы оба типа решаемых задач — учета потребности в ресурсах и их рационального распределения с одновременным построением соответствующих календарных планов строительства.

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

Б. Задача минимизации отклонения от заданных сроков (или минимизации сроков) при ограниченных ресурсах

Для примера задана простейшая одноцелевая детерминированная сетевая модель строительства объекта с временными и ресурсными характеристиками работ (рис. 6.24, а). Известно наличие ресурсов, например общее количество рабочих. Интенсивности работ постоянны и перерывы в их выполнении не допускаются.

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

Прежде всего перенесем все работы с сетевой модели на календарный график так, чтобы начало каждой из них совпадало с ранним сроком (рис. 6.24, б). В данном примере это сделано для наглядности, так как при машинной реализации в построении календарного графика нет необходимости. Нужные нам для последующих расчетов ранние сроки начала и полные резервы времени работ сетевой модели, показанной на рис. 6.24, а, таковы: для работы (0—1) они составят соответственно 0 и 1, для работы (0—2)—0 и 0, для работы (1—2)—2 и 1, для работы (1—3) — 2 и 7, для работы (2—3) —6 и 0, для работы (2—4) —6 и 5, для работы (3—5) — 14 и 0, для работы (4—5) — 13 и 5 (способы расчета, см. § 6.4).

Далее составим монотонно возрастающую последовательность моментов t1, t2,...,tкон, обозначающих даты начала и окончания всех работ, причем примем t1 = 0, а потому tкон=Ткр, т. е. критическому времени.

После этого рассмотрим первый промежуток времени t1t2. В указанный промежуток попадают все работы ij, у которых ранние сроки начала меньше t2, а ранние сроки окончания больше t1. Каждой такой работе присваивается та или иная оценка приоритета — ωij. Для работы ij оценка приоритета ωij связана с ее полным резервом времени :

где tx — момент окончания рассматриваемого промежутка времени; — ранний срок начала работы ij; ξ — некоторая константа, подбираемая на каждом промежутке с таким расчетом, чтобы во всех случаях было ωij≥0.

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

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

Здесь t1=0; t2=2; t3=5; t4 = 6; t5=7; t6=13; t7=14; t8=19; t9=24.

Определим по формуле (6.44) для первого промежутка t1t2 оценки приоритета, приняв ξ=3: ω01= 1—(2—0)+3=2; ω02 =  0—(2—0) + 3= 1 (работа критического пути).

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

Будем последовательно суммировать потребности в данном виде ресурсов в промежутке t1t2, начиная с работ, имеющих минимальную оценку приоритета ωij, и постепенно переходя к работам, имеющим все большую оценку. Как только сумма превысит число, определяющее уровень, установленный для данного промежутка, начало соответствующей работы сдвинем к моменту t2. После этого следует пересчитать ранние начала и окончания, а также полные резервы времени всех работ, начало которых передвинуто из промежутка t1t2 в t2t3. Далее, учитывая произведенный сдвиг некоторых работ, снова определяем все моменты t'3, t'4 и т. д. и переходим к рассмотрению промежутка t2t'3 по аналогии с тем, как был рассмотрен промежуток t1t2. При этом учитываем условие непрерывности работ, т. е. недопустимость перерывов в начатых работах, которым поэтому может быть присвоена еще меньшая оценка, чем критическим работам.

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

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

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

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

В промежутке t1 = 0; t2 = 2] выполняется критическая работа 0—2, характеризуемая оценкой ω0,2 = 0—(2—0)+3=1, на этой работе заняты 8 рабочих. Добавим к ним 10 человек, занятых в этом же промежутке выполнением работы 0—1 с ω0,1 = 1—(2—0)+ 3=2. Получаем 18 рабочих, что меньше 20.

Так как больше никаких работ в промежутке t1t2 не выполняется, перейдем к промежутку [t2 — 2; t3 = 5]. Здесь выполняются три работы — перешедшая из предыдущего промежутка работа — 0—2 [ω0,2=0—(5—0)+5=0], работа 1—2 [ω1,2= 1 —(5—2)+5=3] и 1—3 [ω1,3 = 7—(5—2) +5=9]. Прибавим к 8 рабочим, занятым на работе 0—2, 12 человек, занятых на работе 1—2. Получится 20 человек, т. е. наш лимит исчерпан. Приходится начало работы 1—3 (ω1,3 = 9) сдвинуть к моменту t3=5 (обозначено штрихами на рис. 6.24, б).

В результате этого действия изменятся некоторые последующие промежутки времени (вместо ts появится t's), которые теперь могут быть охарактеризованы так: t4 = 6; t'5=10; t6=13; t7= 14; t8=19; t9=24 (см. рис. 6.24, б).

Приступаем к следующему за t2t3 промежутку [t3=5; t4= 6].

Здесь выполняются только две работы — работа 0—2 с [ω0,2 = 0—(6—0) +6=0], на которой заняты 8 рабочих, и сдвинутая нами работа 1—3 (обозначена штрихами на рис. 6.24, б) с    = 5;    = 4 и ω_1,3 = 4—(6—5)+6=9, на которой заняты 12 человек. Таким образом, суммарное количество рабочих 20 соответствует заданному ограничению.

Переходим к следующему промежутку t4t'5. В первую очередь учитываем 8 рабочих, занятых на критической работе 2—3,  для которой ω2,3 = 0—(10—6)+4 = 0. К ним прибавляем 12 человек, занятых на работе 1—3, переходящей из предыдущего промежутка, для которой ω1,3 = 4—(10—5)+4 = 3. Таким образом, лимит на промежутке t4t'5 исчерпан, и начало оставшейся работы 2—4, для которой (ω2,4 = 5—(10—6)+4=5, должно быть сдвинуто к моменту t's (обозначено штрихами на рис. 6.24, б). Для этой работы будет теперь  =10, а окончание произойдет на 17-й день, т. е. полный резерв  =1 дню.

Одновременно надо сдвинуть начало работы 4—5 на 18-й день, так как согласно сетевой модели эту работу можно начать лишь после окончания работы 2—4.

Новые промежутки времени будут определяться точками t6'=14; t7'=17; t8'=23; t9'=24.

Рассмотрим промежуток t5't6'. Здесь переходящая из предыдущего промежутка работа 2—3 имеет ω2,3=0—(14—6)+8=0, а вновь начинаемая работа 2—4 имеет ω2,4=1—(14—10) +8=5. Сумма рабочих, занятых на этих работах, составляет 8 + 9 = 17< 20, т. е. ничего сдвигать не нужно.

Рассмотрим отрезок t6't7', где продолжается работа 2—4 [ω2,4 = 1—(17—10)+6=0] и начинается критическая работа 3—5 [ω3,5 = 0—(17—14)+6=3]. Так как нужное для этих работ суммарное количество рабочих 6+9=15, т. е. меньше заданного лимита, можно перейти к рассмотрению следующего промежутка е7't'8. Здесь выполняются лишь две работы — 3—5 и 4—5, и общее количество рабочих составляет 16 человек, что допустимо. Точно такое же вполне удовлетворительное положение в промежутке t8', t9', где одну работу 3—5 выполняют 6 человек.

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

Как видим, в этом примере полученное решение задачи минимизации времени строительства t9=24 совпадает с критическим временем Tкр. В общем случае это решение может превышать критическое время. В данном примере оптимизация осуществлялась только за счет сдвигов работ в соответствии с эвристическими правилами приоритета.

Значительно более гибкими оказываются другие методы, допускающие изменение интенсивности работ (в том числе и перерывы) в процессе их выполнения (следовательно, и переменные продолжительности). Хотя идея сдвигов здесь та же, происходит естественное усложнение алгоритмов и машинных программ. Наибольшее распространение получили алгоритмы типа «Калибровка» в применении к многосетевым задачам, характерным для случаев, когда рассматривается возведение нескольких объектов с использованием единого «резервуара» ресурсов (см. стр. 68).

• В. Задача оптимизации показателя равномерности использования ресурсов при заданных сроках строительства