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

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

ОГЛАВЛЕНИЕ

Следующая >>




1 2 3 4 5
i
t iп 0 1 1 2 5


Применяя вышеприведенное эвристическое правило, получим
следующее решение:
x1 = (1, 1, 0, 0, 0), u 1 = 2
x2 = (0, 1, 1, 0, 0), u 2 = 2
x3 = (0, 0, 1, 1, 0), u 3 = 4
x4 = (0, 0, 0, 1, 1), u 4 = 1
x5 = (0, 0, 0, 0, 1), u 5 = 1

39
Продолжительность комплекса составляет
5
T = ? u s = 10 .
s =1


Выразим векторы yi через базисные векторы:
y5 = x5, b5 = 1
y4 = x4 - x5, b4 = 0
y3 = x3 - x4 + x5, b3 = 1
y2 = x2 – x3 + x4 - x5, b2 = 0
y1 = x1 – x2 + x3 – x4+ x5, b1 = 1
Получаем следующую задачу о ранце:
x1 + x3 + x5 > max ,
6x1 + 4x3 + 7x5 ? 1.
Задача разделяется на три независимых подзадачи:
x1 + x3 > max ,
(2.1.7)
6x1 + 4x3 ? 11;
x3 > max ,
(2.1.8)
4x3 ? 11;

x3 + x5 > max ,
(2.1.9)
4x3 + 7x5 ? 11.
Оптимальное решение задачи (2.1.7): x1 = x3 = 1, задачи (2.1.8):
x3 = 1, задачи (2.1.9): x3 = x5 = 1. Решение задач (2.1.7) и (2.1.9) имеют
одну и ту же величину с = 2.Поэтому вводим в базис любой вектор,
например
x6 = (0, 0, 1, 0, 1) = y 3 + y5 = x3 – x4 + 2x5.
Определяем согласно процедуре симплекс-метода



40
?u u ? 1
u 6 = min? 3 ; 5 ? =
?1 2? 2
и исключаем вектор х5. Новое решение
1
u1 = u1 = 2; u1 = u 2 = 2; u1 = u 3 ? = 3,5;
1 2 3
2
1 1
u1 = u 4 + = 1,5; u1 = ; T1 = 9,5 .
4 6
2 2
Заменяя вектор
x5 = ?(x6 – x3 + x4)
в формулах для yi, мы получим
y1 = x1 – x2 + 1/2x3 – 1/2x4+ 1/2x6, b1 = 1/2
y2 = x2 – 1/2x3 + 1/2x4 - 1/2x6, b2 = 1/2
y3 = 1
/2x3 - 1/2x4 + 1/2x6, b3 = 1/2
y4 = 1/2x1 + 1/2x3 1
/2x6, b4 = 1/2
-
y5 = - 1/2x3 + 1/2x4 + 1/2x6, b5 = 1/2
Новые задачи о ранце имеют вид:
?(x1 + x2 +x3) > max,
6x1 + 5x2 + 4x3 ? 11;

?(x2 + x3 +x4) > max ,
5x2 + 4x3 + 4x4 ? 11;

?(x3 + x4 +x5) > max ,
5x2 + 4x3 + 4x4 + 7x5 ? 11.
Все три задачи имеют оптимальное значение с = 1. Поэтому
полученное решение является оптимальным.
Последовательность векторов xs полученного оптимального
решения не является единственной. Этим в ряде случаев можно
воспользоваться для того, чтобы найти решение с минимальным

41
числом прерываний операций. В работе [3] показано, что задача
минимизации числа прерываний операций сводится к задаче
коммивояжера. В нашем примере число прерываний равно 1 и
уменьшить его нельзя, поскольку при выполнении комплекса без
прерываний операций продолжительность его будет целым числом.
Заметим, что начальное решение, полученное на основе
эвристического правила является оптимальным решением без
прерываний операций, поскольку продолжительность комплекса в
этом решении Т = 10 является ближайшим целым числом, которое
больше минимальной продолжительности Т1 = 9,5.
Как уже отмечалось выше, описанный метод дает оптимальное
решение при заданном упорядочении событий сети. Если возможных
упорядочений несколько, то необходимо решить задачу при каждом из
них и выбрать лучшее решение. Однако, в ряде случаев можно судить
об оптимальности полученного решения без перебора других
упорядочений событий. Для этого необходимо решить задачу о ранце,
не предполагая упорядоченности всех событий сети. Если в результате
решения этой задачи будет получен вектор со значением c > 1, то
следует решить задачу при новом упорядочении, при котором этот
вектор будет допустимым. В нашем примере достаточно рассмотреть
следующую задачу о ранце:

?(x1 +x2 + x3 + x4 +x5) > max,
6x1 + 5x2 + 4x3 + 4x4 + 7x5 ? 11.
Легко видеть, что в оптимальном решении этой задачи с = 1, так что
лучшего решения не существует, какое бы упорядочение событий мы
ни взяли.


42
Для иллюстрации изменения упорядочения событий рассмотрим
следующий пример.
Пример 2.2. Рассмотрим тот же сетевой график, что и в примере
2.1 с данными, приведенными в таблице 4.
Таблица 4.

i 1 2 3 4 5
?i 4 5 3 2 6
6 5 4 4 6
ai


Начальное решение в данном случае будет следующим:
x1 = (1, 1, 0, 0, 0), u 1 = 4
x2 = (0, 1, 1, 0, 0), u 2 = 1
x3 = (0, 0, 1, 0, 1), u 3 = 2
x4 = (0, 0, 0, 1, 1), u 4 = 2
x5 = (0, 0, 0, 0, 1), u 5 = 2
Продолжительность комплекса Т = 11. Действуя, как и в примере 2.1,
мы получим следующую задачу о ранце:

x2 + x5 > max ,
5x2 + 6x5 ? 11.
При заданном упорядочении событий эта задача распадается на две
независимые задачи и, очевидно, каждая из них будет иметь величину
с = 1. Следовательно, полученное начальное решение является
оптимальным при заданном упорядочении.
Заметим, однако, что если изменить очередность событий II и
III, то операции 2 и 5 становятся независимыми. В этом случае
оптимальное решение задачи о ранце будет следующим:


43
x2 = x5 = 1
со значением с = 2. Поэтому вводим в базис вектор
x6 = y2 + y5 = x2 – x3 + 2x5,
?u u ?
u 6 = min ? 2 ; 5 ? = 1 .
?1 2?
Исключаем из базиса любой из векторов, например вектор x5. Имеем
u1 = u1 = 4; u1 = u 2 ? u 6 = 0; u 1 = u 3 + u 6 = 3;
1 2 3

u1 = u 4 = 2; u1 = 1; T1 = 10 .
4 6


Повторяя процедуру, убеждаемся, что полученное решение
является оптимальным.
Предложенный метод решения задачи позволяет также
определить, на какую величину необходимо увеличить количество
ресурса для того, чтобы было возможно дальнейшее уменьшение
продолжительности комплекса. Для этого достаточно определить
уровень ресурсов N, при котором решение задачи о ранце с больше
чем 1, что позволит ввести в базис новый вектор.


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

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

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


1 3 5
4 6 6 1 6 4




2 4 6
6 4 6 1 4 6


Рис. 2.2.


Верхнее число в вершине на рис. 2.2 указывает номер операции,
нижнее слева – минимальную продолжительность ?i, нижнее справа –
максимальное количество ресурсов ai. Пусть N = 5. Поскольку обе
операции 1 и 2 являются критическими, то распределяем ресурсы
прямопропорционально величинам a1 и а2, то есть u1 = 3, u2 = 2.
Нетрудно показать, что распределение ресурсов,
прямопропорциональное величинам аi критических операций,
сохраняет их критическими. Через 8 дней операция 1 завершится и
начнется операция 3. При этом количество ресурсов на операции 2
увеличивается до u2 = 4, так как операция 3 требует всего одной
единицы ресурсов. Через 2 дня завершается операция 2 и начинается
операция 4. С этого момента используется всего две единицы ресурсов
в течении четырех дней, пока не закончится операция 3. Далее процесс

45
идет опять при полной загрузке ресурсов, и комплекс завершается за
24 дня. На рис. 2.3 приведен график использования ресурсов. Видно,
что график имеет «провал» в интервале (10, 14). Этот провал
называется «узким местом» графика. В данном случае процесс следует
организовать так, чтобы минимизировать ширину «узкого места».


N(t)
5




2

t
0 10 12 14 16 18 20 22 24
2 4 6 8

Рис. 2.3.


Для этого следует в первую очередь начать операцию 1,
направив на нее все ресурсы. Через 4,8 дня операция 1 будет
завершена. Далее выполняются операции 2 и 3, затем 4 и 5 и, наконец,
операция 6. Продолжительность комплекса будет минимальной и равна
21,6 дня.
Таким образом, наличие «узких мест» на графике использования
ресурсов является признаком возможной неоптимальности
календарного плана.
Рассмотрим некоторый фронт работ F(t) в момент t , то есть
множество операций, которые выполняются или могут выполняться в
этот момент. Как уже отмечалось, степенью критичности операции i ?
называется ее полный резерв времени в этот момент,
F(t)

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

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

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

ОГЛАВЛЕНИЕ

Следующая >>