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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

3.4.4 СИСТЕМЫ КОНВЕЙЕРНОГО ТИПА
Система называется системой конвейерного типа, если машины можно ранжировать таким образом,
что первая операция каждой работы выполняется на первой машине, вторая операция на второй и т.д.
Именно так обстоит дело при работе на конвейерах, и в связи с этим такие задачи получили название
конвейерных.
Пусть производительность работ задана табл. 3.4
3.4 Производительность машин конвейерного типа
Работа 1 111 122 133 144
Работа 2 211 222 233 244
Работа 3 311 322 333 344
Работа 4 411 422 433 444
Как и раньше, первый индекс i обозначает номер работы, второй индекс j обозначает номер опера-
ции. Третий индекс здесь уже лишний, так как он совпадает со вторым (ведь j-я операция любой работы
делается в конвейерной системе на j-й машине).
Конвейерные системы являются значительным упрощением задачи теории расписания общего вида,
хотя и имеет широкое применение. Для этих задач получен ряд частных результатов.
3.4.5 СИСТЕМА ИЗ ДВУХ МАШИН КОНВЕЙЕРНОГО ТИПА
Каждая работа такой системы имеют две операции (имеются две машины). Первая операция произ-
водится на первой машине, вторая операция – на второй машине.
Для обозначения длительности здесь достаточно двух индексов. Так, Р
ij
обозначает длительность j-й
операции для i-й работы, причем j = 1, 2. Или можно считать P
ij
длительностью i-й работы, выполняе-
мой на машине j (j = 1, 2).
В теории расписания доказывается, что в случае двух машин в системе конвейерного типа порядок
выполнения операций на первой машине в оптимальном случае совпадает с порядком выполнения
операций на второй машине.
Действительно, пусть имеются две работы I
1
= (α
1
, β
1
) и I
2
= (α
2
, β
2
), для которых указанное правило не
выполняется (рис. 3.20, а), а расписание оптимально: α
1
< α
2
,
β
2
< β
1
.
Очевидно, α
1
можно подвинуть, отрезок "bd" сдвинуть так, чтобы точка b
′
совпала с точкой а. То-
гда, так как отрезок "ad" не трогали, то после работы α
2
можно поместить операцию α
1
.
В результате получили α
2
α
1
и β
2
β
1
. Новое расписание (рис. 3.20, б) не хуже старого, а может
быть и лучше, если β
2
можно сдвинуть влево и β
1
также сдвинуть влево.
α
1
α
2
a b c d
β
2
β
1
a)
b d

Страницы