8. Задача о назначениях.

Постановка задачи. Заданы: множество работ ; множество приборов или исполнителей ; матрица затрат времени , где – время выполнения i-й работы j-м исполнителем, . При этом каждый исполнитель может выполнять произвольное количество работ, а каждая работа назначается для выполнения только одному исполнителю. Тогда необходимо распределить работы по исполнителям таким образом, чтобы все они были выполнены в наиболее ранние сроки. Предположим, что – множество вариантов распределения работ по исполнителям, где s₀ – общее количество вариантов распределения работ по исполнителям; N_j(s)– множество работ, назначенных j-му исполнителю в s-м варианте. Тогда время занятости j-го исполнителя в s-м варианте распределения работ

.

Очевидно, что время окончания выполнения всех работ для s—го варианта будет определяться максимальной занятостью приборов . Тогда из множества вариантов S необходимо выбрать такой вариант , для которого . К рассматриваемой задаче на концептуальном уровне сводится задача оптимизации топологии типа «Звезда» локальной вычислительной сети. Элементами сети с топологией типа «Звезда» выступают концентраторы либо коммутаторы, к которым подключаются рабочие станции, а сами коммутирующие элементы также связаны между собой (рис. 2.9).

32. Упрощенное представление локальной вычислительной сети с топологией типа «Звезда»

На рис. 2.10 указаны возможные места размещения концентраторов и показан один из вариантов распределения рабочих станций по трем концентраторам, общее количество возможных мест размещения концентратов равно шести.

Необходимо определить такой вариант распределения рабочих станций по концентраторам, при котором затраты на коммуникационные соединения будут минимальными.

9. Основные понятия и определения теории расписаний

Введение в теорию расписаний

Рассматриваются два множества:

M = {M1, M2,…, Mm} — машины (станки, процессоры, бригады, …)

J = {J1, J2,…, Jn} — работы (задания, пакеты задач, …)

Расписание — указание, на каких машинах и в какое время должны выполняться работы.

В каждый момент времени каждая машина выполняет не более одной работы, и каждая работа выполняется на одной машине или не выполняется вовсе.

Характеристики работ

Работы состоят из операций:

Операция требует pij времени и может выполняться на одной из машин множества ij  {M1,…, Mm}.

Если | ij | = 1,  i j, то получаем модель с предписаниями.

Если | ij | = m,  i j, то получаем модель с параллельными машинами.

Для работы Ji известны:

ri  0 — время появления первой операции

di  0 — директивное время окончания последней операции

wi  0 — важность (вес, ценность) работы Ji

Классификация задач теории расписаний

Краткая запись задачи  |  | 

 — характеристики машин;  — характеристики работ;

 — целевая функция задачи;

Варианты для  :

1 = pmtn (preemption) разрешаются прерывания;

2 = prec (precedence relations) условия предшествования на множестве работ (цепи, деревья, сети);

3 = ri — время поступления на обслуживание

4  {pij =1; pij {0,1}; pij = pij(t), …} — уточнения для времени выполнения операций.

5 = di — директивные сроки окончания работ;

6 = p-batching (s-batching) — работы разбиваются на группы, и в каждой группе берется максимум (сумма) времён выполнения работ;

Характеристики машин

Поле  состоит из двух частей  = 1 2 :

1 — характеристики машин,

2 — число машин.

Если 1{, P, Q, R}, то ni = 1  Ji, то есть каждая работа состоит ровно из одной операции.

1 =  — для каждой работы задана машина для ее выполнения,

1 = P — машины параллельны и одинаковы pij = pi,

1 = Q — машины параллельны, но различаются скоростями pij = pi / sj ,

1 = R — машины параллельны, длительности выполнения работ произвольны, но pij = pi / sij .

Если 1{G, X, J, F, O}, то ni  1, то есть у каждой работы может быть несколько операций.

1 = J (job shop, рабочий цех) — у каждой операции своя машина | ij | = 1 и линейный порядок выполнения операций .

1 = F (flow shop, потоковая линия) — машины упорядочены M1, M2,…, Mm и каждая работа проходит все машины в этом порядке, ni = m и ij = Mj, i.

1 = O (open shop, открытая линия) — каждая работа состоит из m операций (ni = m), но ij = { M1,…, Mm } и на множестве операций нет условий предшествования,

1 = X (mixed shop, смешанный цикл) — смесь J и O,

1 = G (general case) — произвольный порядок предшествования на операциях (как в календарном планировании).

Целевые функции

Обозначим через ci — время окончания работы Ji. Рассматриваются два типа минимизируемых целевых функций: