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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Для таких систем мало конечных результатов составления оптимального расписания.
Для целевой функции, представляющей собой средние регулярные критерии
WT ,
и другие, дока-
зана теорема [1]:
В оптимальном расписании должен быть одинаковый порядок выполнения работ на первых двух
машинах, если все работы доступны одновременно.
Для целевой функции, минимизирующей максимальную продолжительность
max
T
, доказана сле-
дующая теорема:
В оптимальном расписании должен быть одинаковый порядок работ на двух первых машинах и на
двух последних, т.е. на машинах 1, 2 и на m – 1, m, если все работы доступны одновременно.
Решение данной задачи осуществляется методом ветвей и границ.
3.5 Алгоритм решения общей задачи составления расписания
Алгоритмы решения общей задачи составления расписания подразделяются на диспетчерские (при-
ближенные) и точные.
3.5.1 АЛГОРИТМЫ ДИСПЕТЧЕРИЗАЦИИ
В алгоритмах диспетчеризации включение в расписание операции производится один раз и навсегда.
Операции назначаются одна за другой и также выполняются.
Таким образом, процесс назначения операции и выполнение ее можно совместить, именно поэтому
такие алгоритмы называются алгоритмами диспетчеризации.
Пусть {S
so
} – множество ожидающих операций. Если операция взята из {S
so
} и включена в распи-
сание, назад в {S
so
} она вернуться не может, то это алгоритм диспетчеризации.
Наиболее часто используются следующие типы алгоритмов диспетчеризации.
1 Незадерживающая диспетчеризация. Множество {S
so
} разбивается на m подмножеств {S
so
}
k
опе-
раций, которые ожидают освобождения k-й машины и для которых предшествующие операции выполнены.
Пусть
{
S
so
}
k
=
{
(i, j, k), (i
1
, j
1
, k), (i
2
, j
2
, k),
…}
; T
k
– момент освобождения k-й машины.
Для машины с номером k выбирается та операция, для которой предыдущая операция выполнена,
если такой нет, то выбирается та, у которой минимально время ожидания до начала операции на k-й ма-
шине
,minarg)(
,
ijk
ji
Wij
=
где W
ijk
= S
ijk
– T
k
, S
ijk
– момент возможности начала операции j на машине k, т.е. момент, когда все пре-
дыдущие операции этой машины выполнены. Выбор операции для машины с номером k представлен на
рис. 3.22.
W
ijk
ijk машина k
T
k
S
ijk
i, j – 1, l машина l
Рис. 3.22 Выбор операции для машины с номером k
2 Диспетчеризация по минимуму времени выполнения операций.

Страницы