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

Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...

Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...

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

2017-12-12 275
Оптимизация сетевого графика методом “время – стоимость”. 0.00 из 5.00 0 оценок
Заказать работу

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

аij £ tij £ bij,

сbij £ сij £ саij; (26)

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

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

сij =zij – yijtij ,

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

yij = (саij – сbij)/(bij – аij)=Dс/Dt. (27)

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

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

Если на всех работах принять tij = bij, то мы получим сетевой график, которому соответствуют наименьшие затраты, равные Сb = =å"(i,j) сbij, и наибольшее критическое время Ткpmax.

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

С

Са

 

Сd С(Т)

Сb

 

Рис 15.

Ткр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ах.

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

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

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

4 30 18 11 саij сbij

15 21 аij bij

Рис.16.

Примем tij = аij (выделено жирным шрифтом), тогда Ткрmin = 15,

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

y12=(16 – 10)/(6 – 4)=3, y13=(30 – 18)/(21–15)=2, y23=(13–10)/(11– 8)=1,

т.е. увеличение продолжительности работы (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. И мы получили общее правило для выбора работ – приоритетом является «цена» сокращения.

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

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

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

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

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

Сd M затрат

 

Сb

N

L Рис 17.

Ткрmin Топт Ткрmах

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

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

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

аij £ tij £ bij,

сbij £ сij £ саij,

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

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

 

 

обозначения

12 11 3 5

6 6 6 yik

4 8 5 10 3 8 аik bik

10 4

Рис.18

Пусть заданное время Т=22. Поставим на каждую работу минимально возможное количество исполнителей, тогда продолжительности работ будут максимальные, т.е. tik = bik. Время выполнения всего проекта в данном случае будет 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= f1+f2w®min,

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

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

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

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

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

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

f1zÎМ1z*– Тzдир], (28)

f1zÎМ1z*– Тzдир]2, (29)

f1zÎМ1 êТz*– Тzдирê, (30)

f1zÎМ11z*– Тzдир], (31)

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

f1zÎМ1z*– Тzдир]xz, (32)

где xz = x1z для zÎМ11,

x2z для zÎМ12

12ÌМ1 – множество объектов, для которых получено Тz* < Тzдир),

f1=махzÎМ1z*– Тzдир]. (33)

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

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

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

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

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

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

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

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


Поделиться с друзьями:

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

Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...

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

Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.05 с.