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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Рис. 3.2 Задание Р
ijk
для составления расписания
t
машина 1
Рис. 3.3 Представление машины
P
ijk
141 t
машина 1
Рис. 3.4 Длительность операции
При составлении расписания обычно принимаются следующие допущения:
1 Машина под одним номером единственна, эта машина всегда исправна, т.е. в любой момент вре-
мени можно назначить выполнение операции, если эта операция действительно выполняется на данной
машине и если в необходимый момент машина свободна.
Таким образом, машину можно представить себе как временную ось (рис. 3.3).
2 Прерывание операций отсутствует. Это означает, что на временной оси каждая операция обозна-
чается отрезком [a, b], причем длительность операции при этом Р
ijk
= b – a. Таким образом, назначить
выполнение операции на машине 1 в момент t – это значит поместить соответствующий блок из табл.
3.1 на ось t машины 1 (рис. 3.4).
В записи (141) цифра 1 – это и есть номер машины, на которой выполняется четвертая операция
первой работы.
3 В каждый момент времени машина может выполнять не более одной работы. Это означает, что
прямоугольники не могут налезать друг на друга, т.е. если есть две операции [а
х
, b
х
] и [а
y
, b
y
], то для со-
ответствующих отрезков должно выполняться либо [а
х
, b
х
] < [а
y
, b
y
], либо [а
y
, b
y
] < [а
х
, b
x
].
4 Операции строго упорядочены и не пересекаются. Это очень важное допущение, оно означает что
j + 1-я операция одной и той же работы i должна начаться только после того, как кончится j-я операция той
же работы независимо от машины, на которой они выполняются (рис. 3.5)
Для операций j и j + 1 одной и той же работы справедливо
н
1
+j
t
к
j
t≥ .
н
j
t
к
j
t
н
1
+j
t
к
1
+j
t
Рис. 3.5 Отношение между операциями
Сформулированные допущения не обязательны, есть задачи, в которых они не приемлемы, но эти
задачи чрезвычайно сложны и почти не рассматривались.
Задача теории расписания считается заданной, если заданы число машин – m, число работ – n, число
операций для каждой работы – q
j
, j = 1, 2, 3, ..., n, время выполнения j-й операции i-й работы на k-й машине
– P
ijk
, причем множество P
ijk
может быть задано в форме, представленной на рис. 3.2, момент готовности к
выполнению i-й работы (момент наступления i-й работы) – r
i
, плановый срок выполнения i-й работы – d
i
.
В теории расписания обычно рассматривается случай, когда момент прихода всех работ единовре-
менный, т.е. r
1
= r
2
= r
3
= ... . Таким образом, рассматривается статический случай: все работы извест-
ны, нужно их распределить по машинам. При этом можно считать r
i
≡ 0. Иногда, однако, r
i
различны,
т.е. необходимо рассматривать динамический процесс составления и коррекции расписания.
Однако характерными случаями разновременного прихода работ (r
i
= var) занимается теория массо-
вого обслуживания.
В дальнейшем считается, что r
i
= const, величина d
i
– срок выполнения i-й работы.
Таким образом, продолжительность i-й работы
пр
i
T определяется как
машина 1
машина 2
i
j
k
i, j + 1, 2

Страницы