<< Предыдущая

стр. 7
(из 8 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

операции с одинаковой степенью критичности (с равными полными
резервами времени) получают ресурс таким образом, что их степени
критичности остаются одинаковыми.
Покажем, что в этом случае операции с одинаковой степенью
критичности должны получать ресурс прямопропорционально
величинам ai. Действительно, если ui = ?ai для операций с одинаковыми
степенями критичности, и это распределение ресурсов имело место в
течении интервала ?, то минимальная продолжительность этих
операций уменьшилась на ? = ui?/ai = ??, то есть на одну и ту же
величину. На эту же величину увеличился поздний момент начала
оставшейся невыполненной части операции, а значит, полные резервы
времени этих операций остались равными. Из сказанного выше следует
простое свойство полных резервов времени.
Свойство при применении правила СК. Полные резервы
времени с течением времени не увеличиваются.
Доказательство. Заметим, что если бы все операции фронта
получили максимальное количество ресурса в интервале
F(t)
длительности ?, то их минимальные продолжительности уменьшились
бы на ?, и полные резервы времени остались бы без изменения.
Однако, в силу правила СК, ресурсы в первую очередь получают
критические операции. Поэтому уменьшение минимальных
продолжительностей критических операций всегда не меньше, чем

47
всех остальных операций фронта. Поэтому полный резерв любой
операции не увеличивается. Отсюда, в частности, следует, что
критические операции остаются всегда критическими.
Опираясь на это свойство, докажем оптимальность правил СК
для случая независимых операций.
Теорема 2. В случае независимых операций правило СК всегда
дает оптимальное решение.
Доказательство. Рассмотрим пример графика использования
ресурсов, изображенного на рис. 2.4. Момент завершения комплекса
определяется моментом завершения критических операций.


u(t) N(t)




t
Т
a b
Рис. 2.4.


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


48
Рассмотрим теперь комплекс операций, который состоит из m
независимых путей, каждый из которых, в свою очередь, состоит из ni
операций. Обозначим aij – максимальное количество ресурсов на j-ой
операции i-ой цепочки.

Теорема 3. Если aij ? aij+1, j = 1, n i ? 1 , i = 1, m , то правило СК

всегда дает оптимальное решение.
Доказательство, по сути дела, повторяет доказательство
теоремы 2.


2.3. Задача календарного планирования при учете
совмещения агрегированных операций

Интересным вариантом агрегированного описания сложного
проекта является его представление в виде n агрегированных операций,
зависимость между которыми учитывается с помощью так называемых
коэффициентов совмещения.
Коэффициент совмещения по началу kij означает, что работу j
можно начинать только когда выполнена определенная часть kij работы
i. Коэффициент совмещения по концу qij означает, что после
завершения работы i необходимо выполнить не менее определенной
части qij работы j. С помощью коэффициентов совмещения можно
описывать как технологические, так и ресурсные зависимости.
Наличие коэффициентов совмещения kij и qij не означает, что работа i
должна начаться (окончиться) раньше чем начнется (окончится) работа
j, а означает только, что они имеют смысл, если работа i начнется
(завершится)ранее работы j. Более того, работа j может начаться
(окончиться) раньше, чем работа i. В этом случае появляются,
соответственно, коэффициенты совмещения kji и qji. Если очередности

49
начала и окончания работ определены, можно построить обычную
сетевую модель, и задача сводится к оптимальному распределению
ресурсов на этой модели. Для того, чтобы убедиться в этом,
достаточно рассмотреть две работы – i, j.
Пусть работа i начинается и заканчивается раньше работы j. В
этом случае получаем сетевой график, показанный на рис. 2.5.


kij (wi - kij)
Работа i

(wj - qij) qij
Работа j

Рис. 2.5.


Если работа i начинается раньше работы j, а заканчивается
позже, то получаем сетевой график, показанный на рис. 2.6.


qji
kij (wi - kij- qji)
Работа i

wj
Работа j

Рис. 2.6.


Аналогично можно изобразить остальные случаи.
Пример Рассмотрим проект из трех операций,
2.4.
коэффициенты совмещения которых приведены ниже:

?0 1 2? ? 0 3 1?
? ? ? ?
K = ? 3 0 4 ?, Q = ? 2 0 3 ? .
?4 2 0? ? 4 2 0?
? ? ? ?

50
Пусть очередность начала и окончания работ одна и та же – (1, 2, 3), то
есть работа 1 начинается (заканчивается) раньше работы 2, а работа 2 –
раньше работы 3.Сетевой график, соответствующий такой очередности
начала и завершения работ приведен на рис. 2.7.


[1] [7]
(1) (6)
1 работа 0 1 5
[5] [10]
[1] [7]
2 работа 2 3 6 7
(3)
(2)
(4)
(3) (3)
3 работа 4 8 9
[5] [10] [13]

Рис. 2.7.


Примем, что продолжительности работ заданы и коэффициенты
совмещения измеряются в единицах времени. Продолжительность
первой работы равна 7, второй – 9, третей – 6. Продолжительность
проекта, определяемая критическим путем (показан на рис. 2.7
толстыми дугами) равна 13.
Задача. Определить очередность начала и окончания работ, при
которой продолжительность проекта минимальна.
Поставленная задача относится к классу NP-трудных задач типа
задачи коммивояжера. Поэтому для ее решения следует применять
либо эвристические методы, либо методы локальной оптимизации,
либо методы типа ветвей и границ. Рассмотрим метод получения
оценки снизу для данной задачи, предполагая, что очередность начала
работ такая же, как очередность их окончания. Для этого определим


51
a i = min k ij ,
j? i

b i = min q ji ,
j?i

di = ?i – bi.
Рассмотрим задачу, которая является несколько более общей,
чем задача Джонсона о двух станках.
Имеется n деталей. Каждая деталь сначала обрабатывается на
первом станке в течении времени ai. Затем деталь доставляется на
второй станок (время доставки равно (di – ai))и обрабатывается на нем
в течении времени bi. Одновременно на одном станке может
обрабатываться только одна деталь. Требуется определить очередность
обработки деталей, при которой продолжительность обработки всех
деталей минимальна. Пусть детали обрабатываются в очередности их
номеров. Тогда продолжительность обработки определяется
выражением

? i ?1 ? ? i ?1 ?
n
T = max ? ? a j + d i + ? b j ? = B + max ? ? c j + d i ? ,
i? ? i? ?
? j=1 ? ? j=1 ?
i

n

?b
где B = , cj = aj – bj.
j
1

Обозначив S = T – B, приведем это выражение к виду
i ?1
S ? ? c j ? d i , i = 1, n . (2.3.1)
j=1

Системе неравенств (2.3.1) можно дать другую содержательную
интерпретацию.
Задача о лекторе. Лектор должен посетить n городов. Для
поездки в город i ему нужна сумма di. В городе i лектору оплачиваются
транспортные расходы di, кроме того, он получает за лекцию



52
некоторую сумму bi, а тратит в городе i сумму ai. Какую минимальную
сумму нужно иметь лектору, чтобы посетить все города?
Очевидно, что условие (2.3.1) является необходимым условием
поездки в город i, если до этого лектор посетил города от 1 до (i-1). Из
этой содержательной интерпретации сразу следует правило выбора
оптимальной очередности посещения городов. Очевидно, что сначала
следует посещать города, в которых оплата лекций bi превышает
расходы ai, то есть после посещения которых сумма денег у лектора
увеличивается. Столь же очевидно, что эти города лектору следует
посещать в очередности возрастания (неубывания) транспортных
расходов di. Далее лектор посещает города, в которых он тратит
больше чем получает, но уже в очередности убывания (невозрастания)
транспортных расходов.
Пример 2.5. Получим оценку снизу для задач из примера 2.4.
Имеем:
a1 = 1, b1 = 2, c1 = -1, d1 = 5;
a2 = 3, b2 = 2, c2 = 1, d2 = 7;
a3 = 2, b3 = 1, c3 = 1, d3 = 5.
Согласно полученному правилу, сначала обрабатывается первая
деталь, затем - вторая, и затем – третья. Продолжительность обработки
составит 11 дней. Фактическая продолжительность проекта при этой
очередности равна13, как было показано ранее. Теперь можно
организовать ветвление, то есть разбиение множества всех решений на
подмножества.
Рассмотрим три подмножества. В первом подмножестве первой
выполняется первая операция. Оценка снизу остается прежней, то есть
Т(1) = 11, хотя фактическая продолжительность равна 13.

53
Во втором подмножестве первой выполняется вторая операция.
Оценка снизу равна Т(2) Заметим, что фактическая
= 12.
продолжительность в данном случае также равна 12, то есть оценка
снизу является точной.
В третьем подмножестве первой выполняется третья операция.
Оценка снизу также равна 12 и определяется очередностью (3, 1, 2).
Однако, фактическая оценка при этой очередности равна 14.
Таким образом, оптимальное решение находится в
подмножестве 2. Ему соответствует очередность работ (2, 1, 3) с
продолжительностью проекта Т = 12 (рис. 2.8).


[3] [9]
(3) (6)
2 работа 0 1 5
[5] [11]
[3] [9]
1 работа 2 3 6 7
(2)
(3)
(2)
(5) (1)

<< Предыдущая

стр. 7
(из 8 стр.)

ОГЛАВЛЕНИЕ

Следующая >>