<<
>>

2.2. Оптимальность эвристического правила по степени критичности операций

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

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

Пример 2.3. Рассмотрим комплекс из шести операций с линейными зависимостями скоростей операций от количества ресурсов и выполняемых ресурсами одного вида (рис. 2.2).

Пример 2.3. Рассмотрим комплекс из шести операций с линейными зависимостями скоростей операций от количества ресурсов и выполняемых ресурсами одного вида (рис. 2.2).

Рис. 2.2

Рис. 2.2

.

0

5 iN(t) t —1— > 2 4 6 8 10 12 14 16 18 20 22 24

Рис. 2.3.

Для этого следует в первую очередь начать операцию 1, направив на нее все ресурсы. Через 4,8 дня операция 1 будет завершена. Далее выполняются операции 2 и 3, затем 4 и 5 и, наконец, операция 6. Продолжительность комплекса будет минимальной и равна 21,6 дня.

Таким образом, наличие «узких мест» на графике использования ресурсов является признаком возможной неоптимальности календарного плана.

Рассмотрим некоторый фронт работ F(t) в момент t , то есть множество операций, которые выполняются или могут выполняться в этот момент.

Как уже отмечалось, степенью критичности операции i е F(t) называется ее полный резерв времени в этот момент,

Верхнее число в вершине на рис. 2.2 указывает номер операции, нижнее слева - минимальную продолжительность ть нижнее справа - максимальное количество ресурсов ai. Пусть N = 5. Поскольку обе операции 1 и 2 являются критическими, то распределяем ресурсы прямопропорционально величинам ai и а2, то есть ui = 3, u2 = 2. Нетрудно показать, что распределение ресурсов, прямопропорциональное величинам аi критических операций, сохраняет их критическими. Через 8 дней операция 1 завершится и начнется операция 3. При этом количество ресурсов на операции 2 увеличивается до u2 = 4, так как операция 3 требует всего одной единицы ресурсов. Через 2 дня завершается операция 2 и начинается операция 4. С этого момента используется всего две единицы ресурсов в течении четырех дней, пока не закончится операция 3. Далее процесс идет опять при полной загрузке ресурсов, и комплекс завершается за 24 дня. На рис. 2.3 приведен график использования ресурсов. Видно, что график имеет «провал» в интервале (10, 14). Этот провал называется «узким местом» графика. В данном случае процесс следует организовать так, чтобы минимизировать ширину «узкого места».

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

Покажем, что в этом случае операции с одинаковой степенью критичности должны получать ресурс прямопропорционально величинам ai. Действительно, если ui = gai для операций с одинаковыми степенями критичности, и это распределение ресурсов имело место в течении интервала Д, то минимальная продолжительность этих операций уменьшилась на 5 = uiD/ai = уД, то есть на одну и ту же величину. На эту же величину увеличился поздний момент начала оставшейся невыполненной части операции, а значит, полные резервы времени этих операций остались равными. Из сказанного выше следует простое свойство полных резервов времени.

<< | >>
Источник: Баркалов С.А., Бурков В.Н., Гилязов Н.М.. Методы агрегирования в управлении проектами. М.: ИПУ РАН, 1999- 55 с.. 1999

Еще по теме 2.2. Оптимальность эвристического правила по степени критичности операций:

  1. Глава 8. Теория доказательства:пропозициональные правила
  2. 2.2. Роль моды в социально-групповой идентификации студентов
  3. 4. ОСНОВНЫЕ ПРАВА ЛИЧНОСТИ (Н.И. Матузов)
  4. 2. ВИДЫ ФОРМ ПРАВА
  5. 2.1. Сети с упорядоченными событиями
  6. 2.2. Оптимальность эвристического правила по степени критичности операций
  7. §7. ПОРЯДОК ЗАКЛЮЧЕНИЯ ДОГОВОРА СТРАХОВАНИЯ. ПРАВА И ОБЯЗАННОСТИ СТОРОН
  8. 7.4. Элементы эвристической деятельности, их основные характеристики
  9. Степени сравнения имён прилагательных
  10. § 1. Сервитуты как основание ограничения и обременения прав собственника недвижимого имущества
  11. § 2. Понятие и виды (формы) злоупотребления правом