Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 56
Текст из файла (страница 56)
Однако в некоторых из них используются довольно сложные стандартные подпрограммы, способные объединять взаимодополняющие ресурсы, устанавливать уровни потребления ресурсов и осуществлять прогнозирование. 4ПЗ. ЗАДАНИЕ ПРЕДЕЛЬНОГО КОЛИЧЕСТВА РЕСУРСОВ В процессе рассмотренного выше выравнивания потребления ресурсов расход различных ресурсов можно регулировать в зависимости от имеющихся резервов времени для выполнения работ.
Однако такой процесс не всегда дает удовлетворительные календарные планы, если количество имеющихся ресурсов строго ограничено. Например, на рис. 4.25,в окончательная потребность в рабочей силе составляет 10 человек в сутки, за исключением 2, 4 и 7-го дней, когда потребность больше. Если число работников, выделяемых для этого проекта, не может превышать 10 человек в сутки и если потребность работ в ресурсах нельзя сократить соответствующим образом, то единственным способом срезать пики, чтобы получить календарный план, обеспеченный требуемыми ресурсами, является последующее изменение календарного плана, что приведет к увеличению продолжительности проекта.
Например, из рис. 4.25,з видно, что выровнять потребность в рабочей силе можно, перенеся начало работы 1 с 7-го на 8-й день. Это позволит задержать работу 5 Я о о .3 ОЗ Ц ки го о. о « о СО .«о о а М! о ОО ОО о г" « о о с л в и о $~ к $ йв к о о о о. к и «. с с ОГ о. о о го х ,о г о о с о с у г $ о о, о о воъинъоявв вивиан па г ог-а еъояед « « « О' «О ~» а«« «х ох "о аа „х ао О « «О Оо 3 « «В « «к «о «« О,Ъ о О о« « « Я« .О Х « « о г О « Ф Я «и о« « ао гг «ъ .Я. « « 9 «=' 346 Глава 4 на один день и выполнять ее одновременно с работой 7, а также задержать работу 2 на один день и выполнять ее одновременно с работой 6.
Поскольку в течение всего периода потребность в рабочей силе не превышает 10 человек в сутки, такой календарный план является выпплнимым с точки зрения наличия ресурсов. Однако в этом случае, как показано на рис. 4.26,а, продолжительность проекта увеличивается на одни сутки.
4.16. ОГРАНИЧЕННЫЕ РЕСУРСЫ Рассмотренное в данном примере изменение календарного плана относится к другой категории процедур анализа сетей, называемой календарным планированием при ограниченных ресурсах. Эти методы предназначены для составления календарных планов, не требующих большего количества ресурсов, чем имеется в любой данный промежуток времени, и продолжительность проекта увеличивается по сравнению с первоначальной, определенной с помощью МКП, как можно меньше.
Процедуры календарного планирования в сетях с ограниченными ресурсами были впервые предложены вскоре после появления общих моделей критического пути и ПЕРТ. Например, Келли и Уолкер 1221 описали в одной из своих ранних статей разработку программы для ЭВМ 1ВМ-650, способной регулировать загрузку до четырех различных видов рабочей силы на одну работу и до девяти — на проект. В 1961 г. эта процедура уже использовалась для нескольких проектов и обеспечила снижение максимальной потребности в рабочей силе на 35— 504/в при увеличении продолжительности проекта в среднем примерно на 5'/в. Огромное множество процедур календарного планирования с ограниченными ресурсами можно разбить на две большие группы на основе используемых методов и их полезности для руководителей.
К первой самой крупной группе относятся эвристические, или приближенные процедуры, предназначенные для составления хороших календарных планов, выполнимых с точки зрения наличия ресурсов. Напротив, ко второй группе относятся процедуры, предназначенные для составления наилучших (оптимальных) планов и основанные на использовании линейного программирования, метода частичного перебора и других подходов.
Эти математические методы оптимизации могут применяться для решения значительно менее сложных задач, чем эвристические. 4.16.1. ЭВРИСТИЧЕСКИЕ МЕТОДЫ Поскольку эвристические методы играют важную роль в календарном планировании при ограниченных ресурсах, необходимо понять их общие принципы и некоторые особенности. Для Методы праве«иве еров«тами 347 этого лучше всего обратиться к некоторым иллюстративным примерам. Рассмотрим снова календарный план проекта продолжительностью 11 сут, представленный на рис. 4.26,а, который был получен в результате выравнивания потребления ресурсов (рис.
4.25, в). В большинстве эвристических процедур решение этой задачи начинается с рассмотрения первоначального календарного плана, определенного с помощью МКП, в котором все работы начинаются в наиболее ранние возможные сроки (рис. 4.25, а). Необходимо рассмотреть каждый промежуток времени календарного плана с целью определить, не превышен ли предельный уровень рабочей силы — 10 человек. Если этот уровень превышен, необходимо изучить список работ, планируемых к одновременному выполнению в этом периоде. Следует применять некоторое принятое правило, или эвристику, например, такое, как «вначале выполняется самая короткая работа», чтобы определить, выполнение каких работ следует задержать.
В случае наличия «связки», т. е. нескольких работ одинаковой продолжительности, должна применяться другая эвристика, разрывающая «связку», например «вначале выполняется работа, имеющая наименьший порядковый номер». Эти правила последовательно применяются механически в каждом промежутке времени (и для каждого вида ресурсов, если их более одного) всего календарного плана, обеспечивая перенос сроков рассматриваемых и следующих за ними работ до тех пор, пока не будут заданы сроки выполнения всех работ и будет получен календарный план, осуществимый с точки зрения обеспеченности ресурсамн.
В качестве иллюстрации данного процесса применение описанной здесь эвристики «вначале выполняется самая короткая работа» позволяет получить календарный план продолжительностью 13 сут, изображенный на рис. 4.26,б. Этот календарный план действительно осуществим с точки зрения обеспеченности ресурсами, но является менее удовлетворительным, чем предыдущий план продолжительностью 11 сут. Легко показать, почему применение правила «вначале выполняется самая короткая работа» позволяет получить такие результаты.
Например, в промежутке времени 1 механическое применение этой эвристики приводит к задержке работы 4, а работы 2 н 3 выполняются одновременно. Однако очевидно, что лучше было бы перенести срок выполнения работы 2, а работы 3 и 4 выполнять одновременно.
Это позволило бы иметь другое распределение работ в последующих периодах и получить менее продолжительный календарный план с более высокими уровнями использования рабочей силы. Использование других, значительно более сложных эврнстик позволяет получить «наилучший из числа возможных», т. е. Глава 4 рассмотренный ранее календарный план продолжительностью 11 сут. Однако на практике даже при использовании более сложных правил невозможно заранее сказать, какая эвристика или комбинация эвристик обеспечит получение результатов, наилучших для данной задачи.
Эвристики, являющиеся неудов- Требуемое число единиц ресурса каждого типа <з,г, О <з, Ц21 <з,г,з> л, л, я, Начальная фиктивн работа Завершаюв<ая фиктивная работа Продолжительность операции Ограничения на ресурсы: йт = 6 человек,<чг = 7 человек, р< = 6 человек ~ Обозначает первоначальный продолжительностью 16 сут критический путь Рис, 4.27. Задача с тремя видами ограниченных ресурсов.
летворительными для одной задачи, могут оказаться хорошими для другой. Например, на рис. 4.27 показана иная, несколько более сложная сеть для трех видов ресурсов. Вследствие указанных ограничений, налагаемых на ресурсы, первоначальная продолжительность критического пути, равная 18 сут, не может быть достигнута. На рис. 4.28 показаны календарные планы, полученные с помощью двух различных эвристик, в сравнении с календарным планом оптимальной продолжительности, определенным с помощью алгоритма, приведенного в статье Дэвиса и Хейдорна 11<11.
В этом случае правило «вначале выполняет- Метода упрпеления проектами Работа ы о о ))з СЬ от с о )2) 20 25 26 10 15 Число суток 8. 1 5 Ку )ту Я) 1 5 1О 15 б ге у л»2 Я) 1 5 1О 15 20 Рис. 4.28. Сравнение эвристических н оптимальных календарных графиков для задачи с тремя видами ресурсов. и — график продолжительностью уб сут, осуществимый с точки зрения обеспечеиностя ресурсами и полученный с помощью еврйстпки (метод календарного планирования ресурсов); б — графяк продолжительностью 23 сут, осуществимый с точки зренвя обеспеченности ресурсамн н полученный с помощью еврнстнки «вяачале выполняется самая короткая работа»; е — график продолжительностью уп сут [оптимальный срок), осуществимый с точки зрения обеспеченноств ресурсами.
350 Глава 4 ся самая короткая работа» дает лучшие, чем метод планирования ресурсов, результаты [411, которые весьма близки к календарному плану оптимальной продолжительности. Эвристические процедуры календарного планирования при ограниченных ресурсах находят широкое применение. Одна из причин этого состоит в том, что они являются единственным способом получения календарных планов, осуществимых с точки зрения наличия ресурсов, в случае больших и сложных задач, часто встречающихся на практике. Другой причиной является то, что, хотя получаемые календарные планы не являются наилучшими, часто они оказываются достаточно хорошими для целей планирования, если учесть, что обычно фактическая продолжительность работ и потребность в ресурсах точно не известны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
