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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

α
2
α
1
а c
′
d
′
β
2
β
1
б)
Рис. 3.20 Расписание для двух машин:
а – правило конвейерной системы не выполняется;
б – оптимальное расписание
Таким образом, можно считать, что при работе на двух машинах порядки выполнения работ на од-
ной машине и на второй совпадают.
Для целевой функции максимальной длительности прохождения работ Джонсоном доказана теоре-
ма.
В конвейерной системе из двух машин при одновременном доступе всех работ минимизация мак-
симальной длительности прохождения этих работ min(
max
T ) осуществляется следующим образом:
работа I
1
= (α
1
, β
1
) предшествует работе I
2
= (α
2
, β
2
), т.е. I
1
< I
2
, если
min(α
1
, β
2
) ≤ min(α
2
, β
1
). (3.25)
Пример 3.1
Пусть I
1
= (5, 2), I
2
= (10, 4), тогда min(5, 4) = 4, min(10, 2) = 2, откуда 4 > 2 и следовательно I
2
< I
1
.
На основе теоремы Джонсона построен алгоритм ранжирования работ.
Доказано, что условие (3.25) тождественно следующему.
Работа I
1
< I
2
, если
а) α
1
≤ β
1
, α
2
≤ β
2
, α
1
< α
2
;
б) α
1
≤ β
1
, α
2
> β
2
; (3.26)
в) α
1
≥ β
1
, α
2
≥ β
2
, β
1
> β
2
.
Условия (3.26) делят все множество работ на два типа (табл. 3.5).
3.5 Формирование расписания для двух машин
Работа I типа Работа II типа
W
I
= {I
i
}
α
i
≤ β
i
W
II
= {I
j
}
α
j
> β
j
Порядок следования
[] [ ] [ ]
[] [ ] [ ]
k
k
III
α≤≤α≤α K
K
21
21
,,,
[][ ] []
[] [ ] []
nkk
nkk
III
β≥≥β≥β
++
++
K
K
21
21
,,,
Пример 3.2
3.6 Исходные данные
Ν
1 2 3 4 5 6 7 8
α
i
7 9 1 3 4 6 10 3
β
i
5 11 8 1 9 3 2 6

Страницы