Оптимизация сетевого графика методом “время –стоимость”
Обозначим аij – минимально возможное время выполнения работы (i,j), которому соответствуют затраты саij; bij – максимально возможное время выполнения работы (i,j), которому соответствуют затраты сbij. Предполагается, что ускорение работы связано с дополнительными затратами (на привлечение дополнительной рабочей силы и оборудования, сверхурочные доплаты и т.п.). Имеем аij ≤ tij ≤ bij , сbij ≤ сij ≤ саij; (2.4.15) сij – затраты, соответствующие времени выполнения tij. Пусть зависимость затрат от времени выполнения линейная, т.е. сij =zij – yijtij , откуда, используя (2.4.15), получаем выражение для коэффициента пропорциональности yij = (саij – сbij)/(bij – аij)=Δс/Δt. (2.4.16) Таким образом, yij характеризует затраты, связанные с сокращением продолжительности работы на единицу времени. Будем называть yij – “ценой” сокращения работы на единицу времени. Если на всех работах принять tij = аij, то будет получено наименьшее критическое время Ткрmin. Этому времени соответствуют наибольшие затраты, равные Са = ∑∀(i,j) саij; Если на всех работах принять tij = bij, то мы получим сетевой график, которому соответствуют наименьшие затраты, равные Сb=∑∀(i,j)сbij, и наибольшее критическое время Ткpmax. При наименьшем критическом времени Ткрmin можно уменьшить затраты, если «удлинить» некритические работы за счет их резервов времени. Ведь увеличение tij на единицу снижает ее стоимость на yij. Обозначим эти затраты через Сd, тогда можем утверждать, что для Т=
176 Ткрmin минимальная стоимость равна Сd, и, в общем случае, для любого Т∈[Ткрmin ,Ткрmах] существует план с минимальными затратами С(Т). График функции С(Т) приведен на рис 2.4.5. С Са
Сd С(Т) Сb
Рис 2.4.14. Т кр min Т кр mах Имея график оптимальной зависимости стоимости проекта от продолжительности его выполнения можно, с одной стороны, определять минимальную стоимость проекта при любом возможном сроке его выполнения, а с другой стороны, находить минимальную продолжительность выполнения проекта при заданной его стоимости. С помощью функции С(Т) можно также оценить дополнительные затраты, связанные с сокращением сроков завершения проекта. Если затраты линейно зависят от продолжительности работ, как мы выше предположили, то нахождение С(Т) можно свести к решению задачи линейного программирования вида: Найти такие продолжительности работ – tij, что 1. Тj – Тi – tij ≥ 0, для всех работ (i, j); 2. аij ≤ tij ≤ bij , 3. Tn0 ≤ Т, 4. С(Т)=∑∀(i,j) сij =∑∀(i,j) (zij – yijtij ) → min, что эквивалентно ∑∀(i,j) yijtij → mах. Однако решать такие задачи методами линейного программирования, как правило, неэффективно, в связи с чем используются специально разработанные эвристические алгоритмы. Разберем один из них на небольшом примере. Сеть приведена на рис.2.4.15. 10 13 Цифры над работами 16 6 8 10 означают 4 30 18 11 саij сbij 15 21 аij bij Рис.2.4.15. Примем tij = аij (выделено жирным шрифтом), тогда Ткрmin = 15, Са=∑∀(i,j)саij=16+13+30=59, Rп12=3, Rп23=3, Rп13=0. Определим цены сокращения работ на единицу, согласно (2.4.16) имеем: y12=(16 – 10)/(6 – 4)=3, y13=(30 – 18)/(21–15)=2, y23=(13–10)/(11– 8)=1, 1 2 3iJ
177 т.е. увеличение продолжительности работы (1,2) на единицу удешевляет ее на 3 и т.д. Увеличим продолжительность некритических работ (1,2), (2,3) в пределах их полных резервов (т.к. они находятся на одном пути, то полный резерв у них общий). Если увеличить продолжительность работы (2,3) на 3, то это удешевит первоначальный план на 3y23=3, если же удлинить работу (1,2), а ее можно удлинить только на 2 дня, то стоимость уменьшится на 2y12=6, и еще на 1 можно будет увеличить продолжительность работы (2,3), что даст экономию еще на 1, – всего сокращение стоимости составит 6+1=7. Мы получили самый дешевый план при Ткрmin = 15, стоимость которого Сd =59 – 7=52. И мы получили общее правило для выбора работ – приоритетом является «цена» сокращения. Мы рассматривали зависимости между затратами и временем выполнения работы, имея в виду лишь прямые затраты, поскольку выявить изменение косвенных (накладных) расходов от изменения продолжительности отдельной работы весьма затруднительно. Косвенные затраты существенно зависят от времени завершения всей программы в целом, причем известно, что с увеличением срока выполнения проекта косвенные затраты возрастают. В предположении линейной зависимости косвенных затрат от срока завершения проекта (что отображено на рис. 2.4.16 прямой LN) оптимальному плану (с учетом прямых и косвенных затрат) будет соответствовать точка М. С график функции суммарных прямых и косвенных Сd M затрат
Сb N L Рис 2.4.16. Т кр min Топт Т кр mах С помощью вышерассмотренной модели “затраты – время” можно решить иную по сути, но аналогичную по математической постановке задачу минимизации общего числа исполнителей, необходимых при выполнении проекта при заданном сроке его окончания. Будем трактовать саij как количество исполнителей, необходимое для выполнения работы (i,j) в минимально возможное время аij; соответственно сbij – количество исполнителей, необходимое для выполнения работы (i,j) в максимально возможное время bij. Имеем аналогичные (2.4.15) соотношения аij ≤ tij ≤ bij ,
178 сbij ≤ сij ≤ саij, где сij – количество исполнителей, соответствующее времени выполнения tij. В рассматриваемой задаче “цена” сокращения yij вычисляется также по формуле (2.4.16) и показывает, сколько исполнителей надо добавить, чтобы сократить время выполнения работы на единицу времени. Рассмотрим пример (рис. 2.4.17).
обозначения 12 11 3 5 6 6 6 yij 4 8 5 10 3 8 аij bij 10 4 Рис. 2.4.17 Пусть заданное время Т=22. Поставим на каждую работу минимально возможное количество исполнителей, тогда продолжительности работ будут максимальные, т.е. tij = bij. Время выполнения всего проекта в данном случае будет 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. Подобный подход и критерий оптимальности применяется в некоторых системах управления строительным производством, где план, обеспечивающий своевременный ввод объекта в эксплуатацию с минимальной суммой интенсивностей потребления ресурсов, считается наилучшим. В каких случаях целесообразно оптимизировать iJ12 3 4 5
179 план возведения объекта по этому критерию? Это целесообразно тогда, когда затраты на возведение объекта существенно зависят от общего количества привлеченных рабочих, например, при строительстве объектов в малоосвоенных районах страны, при прокладке линий электро-передач, газопроводов, железных дорог и т.п. При строительстве объектов в районах массовой застройки оптимизация по указанному критерию не имеет смысла, т.к. получим план выполнения работ на каждом из объектов меньшим количеством ресурсов, но при более длительном их использовании, тогда как лучшим может оказаться план, при котором на каждом из объектов концентрируется большее число рабочих, которые выполняют отдельные работы за более короткие сроки и переходят на другие объекты. Кроме того, критерий эффективности – “суммарная интенсивность выполнения работ” – представляет собой сумму интенсивностей потребления ресурсов различного вида на работах, выполняемых в различные промежутки времени. Относительная дефицитность ресурсов различных видов значительно изменяется во времени в зависимости от производственной ситуации, складывающейся на всем множестве объектов, питаемых ресурсами из одного “резервуара”. Поэтому возможна ситуация, при которой в некоторый период времени легче, например, добавить 50 отделочников, чем 10 монтажников. Расчеты сетевой модели отличаются простотой, но в то же время дают весьма важную информацию для календарного планирования сложных проектов. Вследствие этого сетевые методы пользуются большой популярностью на практике. Эффективность этих методов обеспечивается благодаря наличию широкого спектра программных средств на ЭВМ, позволяющих строить, анализировать и корректировать сетевые модели проектов.
Ви переглядаєте статтю (реферат): «Оптимизация сетевого графика методом “время –стоимость”» з дисципліни «Математична економіка»
