Методы исследования операций при принятии решений. Бодров В.И - 60 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

При такой диспетчеризации из {S
so
}
k
выбирается не та операция, у которой меньше время ожидания
от момента освобождения Т
k
, а та у которой меньше сумма времени ожидания и времени выполнения
(рис. 3.23)
[minarg)(
ij
ij
=
W
ijk
+ P
ijk
].
W
ijk
ijk машина k
T
k
i, j – 1, l машина l
Рис. 3.23 Диспетчеризация по минимуму времени выполнения операций
Диспетчеризация по минимуму времени ожидания и незадерживающимся операциям называется
моделированием процесса, так как сам процесс составления расписания моделирует реальное выполне-
ние расписания.
3 Моделирование по приоритетам.
Приоритет является числовой характеристикой, показывающей важность работы.
Сначала выбираются те машины, которые имеют высший приоритет, затем с более низким.
3.5.2 ТОЧНЫЕ МЕТОДЫ ОПРЕДЕЛЕНИЯ РАСПИСАНИЯ
К точным методам составления расписания относится метод ветвей и границ. Для применения мето-
да из теории графов известно, что для этого необходимо:
1) правильно сформулировать, что такое состояние (вершина);
2) формализовать функцию оценки вершины.
Таким образом, состояние – это фрагмент расписания, которое уже построено. Ветвление – операции,
идущие за этим фрагментом. Функция оценки
,
nnn
qQ
ψ
+
=
где
n
q – оценка уже пройденного пути (т.е. оценка фрагмента расписания);
n
ψ – функция прогноза,
обещание эффективности оставшегося фрагмента расписания, т.е. длительности, ожидания и т.д. до це-
левой вершины.
Из теории графов известно, что метод будет тем эффективнее, чем ближе функция к (к
точному значению), тем меньше количество вершин потребуется раскрыть. Причем, если для
всех вершин меньше , метод ветвей и границ найдет оптимальное расписание, а если для не-
которой вершины будет больше – метод ветвей и границ не гарантирует нахождение оптималь-
ного решения.
Для каждой конкретной задачи формализация функции происходит нестандартно. Часто
расчет для каждого узла сам по себе сложная задача, требующая длительных расчетов. При
этом встает задача компромисса между точностью оценки нижней границы и временем, необ-
ходимым для расчета этой оценки. Может оказаться, что целесообразно загрубить , что приво-
дит к большему числу вершин, которые нужно раскрыть, однако, времени на расчет функции оцен-
ки этих вершин затрачивается мало.
Наиболее распространены следующие методы расчета оценок.
1 Используя уже составленный до данной вершины фрагмент расписания, формализуется все рас-
писание одним из методов диспетчеризации. При этом значением ψ
n
для этой вершины будет значение
максимального идеального времени прохождения работ полученного расписания.
ψ
*
n
ψ
n
P
ijk
ψ
n
ψ
*
n
ψ
*
n
ψ
n
ψ
n
ψ
∗
n
ψ
n
ψ
n
ψ
*
n
ψ
*
n

Страницы