Сетевые модели. Тема10_Сетевые модели_net_lec. Тема 10 Сетевые модели
 Скачать 1.35 Mb.
|
|
0 ≈ 7 человек. Задача сводится к определению плана, доставляющего минимум отклонения от среднего min z = min max t { | n ср -n t |}, т.е. требуется построить такой календарный план (график) реализации программы, при котором по- требности в рабочей силе будут наиболее равномерными на протяжении всего срока осуществления программы. Заметим, что для выполнения операций (0, 1) и (1,3) рабочая сила не требуется, на что указы- вает, нулевое количество человек для каждой из этих операций. Вследствие этого календарные сроки операций (0,1) и и (1,3) можно выбирать независимо от процедуры выравнивания потребностей в ре- сурсах.) На рис. 5.6 a, показана потребность в рабочей силе при условии выбора в качестве календар- ных сроков некритических операций начала их ранних сроков (так называемый ранний, или левый, календарный план), а на рис. 5.6 б — потребность в рабочей силе при выборе наиболее поздних сро- ков (так называемый поздний, или правый, календарный план). Пунктирной линией представлена по- требность критических операций, которая должна быть обязательно удовлетворена, если нужно вы- полнить программу в минимально возможный срок. (Отметим, что для операций (0, 1) и (1, 3) ресур- сы рабочей силы не требуются.) Как показывают потребности в ресурсах критической операции (2, 3), для реализации программы необходимо, по крайней мере, 7 человек. При раннем календарном плане некритических операций мак- симальная потребность в ресурсах составляет 10 человек, а при позднем — 12. Этот пример наглядно показывает, что максимальные потребности в ресурсах зависят от использования резервов времени не- критических операций. Однако, как видно из рис. 5.6, независимо от распределения этих резервов мак- симальная потребность в рабочей силе для рассматриваемой программы не может быть меньше 10 че- ловек, так как интервал времени, в пределах которого можно выполнять операцию (2, 4), совпадает с интервалом критической операции (2, 3). График потребности в рабочей силе при раннем календарном плане можно улучшить, выбрав поздние календарные сроки для операции (3, 5) и назначив выполнение операции (3, 6) непосредственно после завершения операции (4, 6). Новый график потребности в рабочей силе, приведенный на рис. 11, обеспечивает более равно- мерное распределение ресурсов с максимальным отклонением от среднего на 3 человека. Рис. 11. Оптимальное распределение ресурсов. При реализации некоторых программ может ставиться цель не просто обеспечения равномер- ного использования ресурсов, а ограничения максимальной потребности в них определенным преде- лом. Если этой цели не удается достичь путем перепланирования календарных сроков некритических операций, то, чтобы снизить потребность в ресурсах, приходится увеличивать продолжительность некоторых критических операций. Из-за математических трудностей пока что не разработан метод, обеспечивающий оптималь- ное решение задачи равномерного использования ресурсов, т. е. задачи минимизации максимальной потребности в ресурсах в любой момент процесса выполнения программы. Поэтому приходится пользоваться эвристическими алгоритмами, подобными приведенному выше. Все эти алгоритмы по- строены на правилах использования резервов времени некритических операций. 5.4. Оптимизация плана с учетом стоимости. 5.4.1. Стоимостные факторы, учитываемые при календарном планировании программ Стоимостный аспект вводится в схему календарного планирования программ путем определе- ния зависимости ―затраты (стоимость) — продолжительность‖ для каждой операции программы. При этом рассматриваются только элементы так называемых прямых затрат, а косвенные затраты типа административно-управленческих расходов не принимаются во внимание. Однако их влияние учи- тывается при выборе окончательного календарного плана программы. Рис.12. Линейная аппроксимация стоимости операции. На рис.12 показана типичная линейная зависимость стоимости операции от ее продолжитель- ности, используемая для большинства программ. Точка (tn, Cn), где tn — продолжительность опера- ции, а Сn — ее стоимость, соответствует так называемомунормальному режиму выполнения опера- ции. Продолжительность операции t n можно уменьшить (―сжать‖), увеличив интенсивность исполь- зования ресурсов (т. е. количество ресурсов, затрачиваемых на выполнение операции в единицу вре- мени), а следовательно, увеличив и стоимость операции. Однако существует предел, называемый ми- нимальной продолжительностью операции. За точкой, соответствующей этому пределу (точкой мак- симально интенсивного режима), дальнейшее увеличение интенсивности использования ресурсов ве- дет лишь к увеличению затрат без сокращения продолжительности операции. Этот предел обозначен на рис.12 точкой с координатами (t c , C c ). Линейная зависимость ―затраты — продолжительность‖ принимается прежде всего из соображений удобства, так как ее можно определить для любой операции всего по двум точкам нормального и максимально интенсивного режимов, т. е. по точкам (t n , С n ) и (t c ,C c ). Использование нелинейной зависимости существенно усложняет вычисления. Однако иногда нелинейную зависимость можно аппроксимировать кусочно-линейной. При таких условиях операция разбивается на части, каждая из которых соответствует одному линейному отрезку. Отметим, что наклоны этих отрезков при переходе от точки нормального режима к точке максимально интенсив- ного режима возрастают. Если это условие не выполняется, то аппроксимация не имеет смысла. Определив зависимость ―затраты — продолжительность‖, для всех операций программы при- нимают нормальную продолжительность. Далее производится полный расчет сети и фиксируется сумма прямых затрат на программу при этой продолжительности операций. На следующем шаге рас- сматриваются возможности сокращения продолжительности программы. Поскольку этого можно до- стичь за счет уменьшения продолжительности какой-либо критической операции, только такие опе- рации и подвергаются анализу. Чтобы добиться сокращения продолжительности выполнения про- граммы при минимально возможных затратах, необходимо в максимально допустимой степени сжать ту критическую операцию, у которой наклон кривой ―затраты — продолжительность‖ наименьший. Отрезок, на который можно ―сжать‖ продолжительность операции, ограничен точкой макси- мально интенсивного режима. Однако, чтобы точно определить, насколько следует сжимать продол- жительность выбранной таким образом критической операции, нужно учесть и другие ограничения, которые подробно рассматриваются в приведенном ниже примере. В результате ―сжатия‖ критической операции получают новый календарный план, возможно, с новым критическим путем. Стоимость программы при новом календарном плане должна быть обяза- тельно выше стоимости при непосредственно предшествующем календарном плане. Рис 13. Графики затраты - продолжительность. Далее этот новый план вновь подвергается сжатию за счет следующей критической операции с минимальным наклоном кривой ―затраты — продолжительность‖, при условии что продолжительность этой операции не достигла минимального значения. Описанная процедура повторяется, пока все крити- ческие операции не будут выведены в режим максимальной интенсивности, т. е. не окажутся сжатыми до минимума". В результате расчетов получаются кривые ―затраты — продолжительность‖. Для всех допустимых календарных планов программ и оцениваются затраты, соответствующие каждому из этих планов. Типичная кривая такого рода показана на рис.13 нижней сплошной линией. Как уже отмечалось ранее, эта кривая определяет только прямые затраты. Естественно считать, что с увеличением продолжительности выполнения программы косвен- ные затраты должны возрастать, как показано на рис.6 штриховой кривой. Сумма прямых и косвен- ных затрат определяет общие затраты на программу (верхняя сплошная кривая на рис.13). Опти- мальный календарный план соответствует минимуму общих затрат. 5.4.3. Пример оптимизации календарого плана по стоимости Рассмотрим сетевую модель, приведенную на рис.14. Рис.14. Сетевая модель в нормальном режиме затрат. Таблица 16 . Затраты на операции. В таблице 16 указаны продолжительность и затраты на каждую операцию, соответствующие нормальному и максимально интенсивному режимам ее выполнения. Требуется определить кален- дарные планы минимальной стоимости, которые можно реализовать в интервале между точками нормального и максимально интенсивного режимов. Решение рассматриваемой задачи основано главным образом на учете наклона кривых ―затраты — продолжительность‖ для различных операций. Таблица 17. Аппроксимация функций затрат. Операция Наклон прямой Операция Наклон прямой (1,2) 50 (2,5) 60 (1,3) 100 (3,4) 25 (2,4) 40 (4,5) 10 Наклон аппроксимирующей прямой вычисляется по формуле: наклон = (C c —C n )/(t n —t c ). Вычисленные наклоны прямых для операций сети приведены в таблице. На первом шаге вычислений предполагается, что все операции программы имеют нормальную продолжительность. На рис.14приведены результаты расчета сети при этих условиях. Критический путь состоит из операций (1,2) и (2,5). Продолжительность выполнения программы равна 18 едини- цам времени, а соответствующие затраты (нормальные) составляют 580. Второй шаг состоит в сокращении продолжительности программы за счет ―сжатия‖ (макси- мально возможного) критической операции с минимальным наклоном кривой ―затраты — продолжи- тельность‖. В сети рис.7 всего две критические операции (1, 2) и (2, 5), Поскольку у операции (1, 2) наклон этой кривой меньше, она и выбирается для сжатия. В соответствии с кривой ―затраты — про- должительность‖ эту операцию можно сжать на две единицы времени, т. е. до предела, определяемо- го точкой максимально интенсивного режима, которая в дальнейшем называетсяпределом интенсив- ности.Однако уменьшение продолжительности критической операции до этого предела не обяза- тельно приводит к сокращению продолжительности всей программы на ту же величину. Это объяс- няется тем, что при сжатии критической операции может возникнуть новый критический путь. В та- ком случае необходимо перейти к рассмотрению операций нового критического пути. Один из способов оценки появления нового критического пути до момента достижения преде- ла интенсивности заключается в анализе свободных резервов времени некритических операций. По определению свободный резерв времени некоторой операции не зависит от сроков начала других не- критических операций. Таким образом, если при сжатии какой-либо критической операции положи- тельный свободный резерв времени некоторой некритической операции становится равным нулю, то следует прекратить сжатие этой критической операции и проверить, не стала ли некритическая опе- рация с нулевым свободным резервом времени критической. Следовательно, помимо предела интен- сивности необходимо учитывать и предел свободного резерва времени. Чтобы определить предел свободного резерва времени, нужно сократить продолжительность выбранной для сжатия критической операции на одну единицу времени, пересчитать свободные ре- зервы времени всех некритических операций и определить, у каких из них положительный свобод- ный резерв уменьшился также на одну единицу времени. Наименьший свободный резерв времени всех таких операций (до сокращения) определяет искомый предел свободного резерва. Применение этого правила к сети рис.14 дает свободные резервы времени (ρ), проставленные у соот- ветствующих операций. Сокращение продолжительности операции (1,2) на одну единицу времени приводит к уменьшению свободного резерва времени операции (3, 4) на величину от единицы до ну- ля. Свободный резерв времени операции (4, 5) при этом не меняется, оставаясь равным 5. Таким об- разом, предел свободного резерва времени равен единице. Поскольку предел интенсивности для опе- рации (1, 2) составляет 2 единицы, еепредел сжатия равен минимуму из пределов интенсивности и свободного резерва времени, т. е. min{2,1}=1. Новый календарный план показан на рис.15. Рис.15. Сетевая модель после первого шага оптимизации. Продолжительность программы составляет теперь 17 единиц времени, а ее стоимость равна сумме стоимости предыдущего плана и дополнительным затратам, обусловленным сокращением продолжительности операции (1, 2) на единицу времени, т. е. она составляет 580+(18—17)*50=630. Хотя свободный резерв времени определяет предел сжатия, критический путь не изменился. Следо- вательно, при задании предела сжатия с помощью предела свободного резерва времени не всегда справедливо утверждение о возникновении нового критического пути. Поскольку операция (1, 2) все еще наиболее выгодна для сжатия, вычисляются соответствующие ей пределы интенсивности и свободного резерва времени. Однако в связи с тем, что предел интенсивно- сти операции (1, 2) равен единице, в данном случае нет необходимости определять ее предел свобод- ного резерва времени, так как любой положительный свободный резерв не может быть меньше 1. Поэтому операция (1, 2) сжимается еще на единицу времени и тем самым достигает своего предела интенсивности. Результаты расчетов приведены на рис.16, из которого видно, что критический путь не изме- нился. Продолжительность программы составляет теперь 16 единиц времени, а ее стоимость равна 630+(17—16)*50=680. Рис.16. Сетевая модель после второго шага оптимизации. Операцию (1, 2) теперь уже больше сжать невозможно, так как для нее достигнут максималь- но интенсивный режим. Поэтому для дальнейшего сокращения продолжительности программы вы- бирается операция (2, 5). Для этой операции имеем: предел интенсивности (10—5=5); предел свобод- ного резерва времени 4, соответствующего операции (4, 5); предел сжатия min{5, 4} =4. Результаты выполненных вычислений приведены на рис.17. Теперь в сети получилось два критических пути: (1, 2, 5) и (1, 3, 4, 5). Продолжительность но- вого календарного плана составляет 12 единиц времени, его стоимость: 680+(16—12)*60=920. Появление двух критических путей свидетельствует о том, что для дальнейшего сокращения продолжительности программы необходимо уменьшить длину двух критических путей одновремен- но. Приведенное выше правило выбора критических операций для сжатия справедливо и в этом слу- чае. В пути (1, 2, 5) операцию (2, 5) можно сжать на одну единицу времени, в пути (1, 3, 4, 5) наименьший наклон кривой ―затраты — продолжительности‖ у операции (4, 5), а ее предел интен- сивности равен двум единицам времени. Поэтому предел интенсивности двух путей равен min{l, 2} =1. Предел свободного резерва времени определяется как минимум этих пределов для каждого пути в отдельности. Однако, поскольку предел интенсивности равен единице, предел свободного резерва времени вычислять не требуется. Рис.17. Сетевая модель после третьего шага оптимизации. Новый календарный план показан на рис.18. Рис 18. Сетевая модель после четвертого шага оптимизации. Продолжительность плана составляет 11 единиц времени, стоимость: 920+(12—11)*(10+60)=990. Два критических пути больше не меняются. Так как все операции критического пути (1, 2, 5) сжаты до предела интенсивности, дальнейшее сокращение продолжительности программы невоз- можно. Следовательно, календарный план является планом максимальной интенсивности. Окончательные результаты выполненных расчетов иллюстрирует рис.19, на котором приведена кри- вая прямых затрат по рассмотренной программе. Рис. 19. График изменения прямых затрат. А — точка режима максимальной интенсивности, В - точ- ка нормального режима. С учетом косвенных затрат, соответствующих каждому из возможных календарных планов, можно найти план, минимизирующий общие затраты, т. е. оптимальный календарный план програм- мы. Например, если функция косвенных затрат имеет вид 100+60 * t , то последовательные оценки полученных ранее планов следующие: 1760, 1750, 1740, 1740,1750. План минимальной стоимости представлен на рис.17 и имеет продолжительность 12 единиц. В примере применены все правила сжатия операций в соответствующих рассмотренному слу- чаю условиях. Однако встречаются ситуации, когда для сокращения продолжительности выполнения про- граммы приходится увеличивать уже сжатые операции. Рис. 5.16 соответствует одной из таких ти- пичных ситуаций. В сети три критических пути: (1, 2, 3, 4), (1, 2, 4) и (1, 3, 4). Продолжительность операции (З, 4) была сокращена от нормальной, составляющей 8 единиц времени, до 5. Продолжи- тельность программы можно уменьшить, одновременно сжимая одну из операций критических путей (1, 2, 4) и (1, 3, 4), либо сжимая операции (1, 2) и (3, 4) и в то же время увеличивая продолжитель- ность операции (2, 3). Рис.20. План, в котором все операции критические. Выбирается вариант с наименьшей суммой наклонов. Отметим, что при сжатии операций (1, 2) и (3, 4) и увеличении продолжительности операции (2, 3) сумма наклонов представляет собой сумму наклонов для операций (1, 2) и (3, 4) за вычетом наклона для операций (2, 3). Во всех осталь- ных случаях, когда отсутствует возможность увеличения продолжительности операций, сумма наклонов равна сумме наклонов сжатых операций. Если требуется увеличить продолжительность, то помимо пределов интенсивности и свобод- ного резерва времени необходимо учесть предел расширения. Этот предел равен разности между нормальной продолжительностью и продолжительностью операции, сжатой до некоторого уровня. Таким образом, предел сжатия представляет собой минимум трех величин: предела интенсивности, предела свободного резерва времени и предела расширения. 5.4.4. Упрощенный метод выявления новых критических путей Выше для определения возможности появления новых критических путей использовался пре- дел свободного резерва времени. Если этот предел велик и равен пределу сжатия, то продолжитель- ность программы можно сокращать большими шагами. По существу, преимущество такого метода заключается в том, что он позволяет свести к минимуму число календарных планов, рассчитываемых в интервале от точки нормального режима до точки максимально интенсивного режима. Это в свою очередь означает, что минимизируется число циклов полного расчета календарного плана програм- мы. Однако для определения пределов свободного резерва времени необходимы дополнительные вычисления, объем которых увеличивается с ростом числа критических путей в сети программы. Та- ким образом, применение метода определения предела свободного резерва времени не гарантирует минимизации объема вычислений. Разработан другой метод, полностью исключающий необходимость определения предела сво- бодного резерва времени. При рассмотрении примера указывалось, что если предел интенсивности равен единице, то вычислять предел свободного резерва времени не требуется, так как любой поло- жительный свободный резерв времени по крайней мере равен 1. В связи с этим новый метод предусматривает сокращение продолжительности программы в точности на одну единицу времени на каждом цикле вычислений, что, как и прежде, реализуется пу- тем сжатия критической операции с наименьшим наклоном. Эту процедуру повторяют для нового календарного плана [и нового критического пути (путей), если он появляется], пока не получают ка- лендарный план для режима максимальной интенсивности. Отметим, что при использовании такого метода продолжительность программы сокращается на каждом цикле вычислений на одну единицу времени. Следовательно, если интервал между нормальной продолжительностью программы и про- должительностью при максимально интенсивном режиме содержит п единиц времени, то требуется выполнение п циклов вычислений. Убедительных доказательств большей эффективности одного из описанных методов по сравне- нию с другим нет. Литература 1. В.М.Бондаpев, В.И.Рублинецкий, Е.Г.Качко. Основы пpогpаммиpования. Хаpьков/Ростов- на-Дону, 1997 2. Кристофидес Н. ―Теория графов. Алгоритмический подход‖. Москва. Мир, 1978. 3. Ахо А. , Хопкрофт Дж.. Ульман Дж. ―Построение и анализ вычислительных алгоритмов‖ Москва. Мир, 1979. 4. Фролов А.Б. и др. ―Прикладные задачи дискретной математики и сложность алгоритмов‖. Москва. Издательство МЭИ, 1997. 5. Емеличев В. А. «Лекции по теории графов». Москва. Наука. 1990 6. Таха Х. Введение в исследование операций. Т. 1, М., Мир, 1985. 7. Дягтерев Ю. И. Методы оптимизации. Сов. радио, 1980. 8. Габасов Р., Кириллова Ф.М. Методы оптимизации. 9. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М., Наука, 1980. 10. Таха Х. Введение в исследование операций. Т. 1, М., Мир, 1985. |