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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Рис. 3.16 Варианты расписаний:
а – первый вариант; б – второй вариант
Для первого варианта (рис. 3.16, а) имеем 2
1
=
T , 0
1
=
W , 2
1
=W и следовательно,
.12/)20(,42/)62( =+==+= WT
Для второго варианта (рис. 3.16, б) – 4
2
=
T , 6
1
=
T , 0
2
=
W , 4
1
=
W ; 22/)40(,52/)64( =+==+= WT . Оба
средних показателя
WT ,
лучше там, где вначале проходила короткая работа.
Для общего случая последовательности работ, отличающихся лишь тем, что работы i, j меняются
местами, варианты расписаний представлены на рис. 3.17.
P
i
P
j
P
j
P
i
i j j i
τ τ
a) б)
Рис. 3.17 Варианты расписаний для общего случая:
а – первый вариант; б – второй вариант
Средние значения времени ожидания в расписании первого (I) и второго (II) вариантов будут
[] [ ] [ ]
[] [ ] [ ]
),(
1
;)(
1
IIIIII
2
II
1
II
II
III
2
I
1
I
I
n
ji
n
ji
WWWWW
n
W
WWWWW
n
W
++++++=
++++++=
KK
KK
где
[]
α
W – время ожидания работ, стоящих на α-м месте.
Очевидно, что
.,
;,
IIII
II
iij
iji
PWW
PWW
+τ=τ=
+τ=τ=
Отсюда
.)(
1
)(
1
III
jiji
PP
n
PP
n
WW −=−τ−τ−+τ+τ=−
Пусть
ji
PP >
, тогда 0
III
>−WW , т.е. .
III
WW >
Таким образом, работа с меньшей длительностью должна выполняться раньше, чем работа с боль-
шей длительностью.
Расписание должно быть составлено так, чтобы работы возрастали по длительности
[] [ ] [ ]
.
21 n
PPP ≤≤≤ K
Это правило носит название правила кратчайших операций.
В оптимальном решении первой должна выполняться операция с наименьшей длительностью.
Алгоритм, который ранжирует работы и назначает порядок в соответствии с возрастанием ее про-
должительности, называется алгоритмом SPT (shortest-processing-timesennencing). Он основан на теоре-
ме: среднее время ожидания W при одной машине минимально, если
[] [ ] [ ]
,
21 n
PPP ≤≤
≤
K и максимально,
если после упорядочения длительности работ последняя не возрастает
[] [ ] [ ]
.
21 n
PPP ≥≥≥ K
Оптимальное по одному среднему критерию расписание будет оптимально и по другому среднему
критерию .,,,,
к
zLTtW

Страницы