Детерминированные задачи упорядочивания.

Номер цикла

1) Постановка задачи:

Имеется несколько изделий, каждое из которых надо обработать на двух машинах последовательно (сначала на первой, потом на второй). Известны времена обработки каждого изделия на каждой машине.

N _изд
t_{1 j}
t _{2 j}

t₁_j – время обработки j-го изделия на первой машине.

t ₂_j – время обработки j-го изделия на второй машине.

2) Формализованное описание задачи:

1) Время перехода детали от первой машины к другой незначительно и его можно не учитывать.

2) Каждое изделие должно быть обработано в определенном порядке: сначала на первой машине, потом – на второй.

3) Каждое обслуживание должно быть завершено прежде, чем начнется следующее, прерываться нельзя.

Изобразим процесс обработки изделия на двух машинах графически

3) Построение математической модели.

Пусть t _nj – время простоя второй машины. Тогда суммарное время обработки изделий составит

n n

y = ∑ t 2 j + ∑ t n j = 29 + 12 = 41

j=1 j=1

n n

т.к. ∑ t 2 j - известна, то надлежит минимизировать ∑ t n j

j=1 j=1

4) Наследование математической модели.

Известен простой алгоритм для нахождения оптимальной последовательности порядка обслуживания n изделий на двух пунктах обслуживания (алгоритм Джонсона). При этом каждое из изделий должно пройти обслуживание на первом пункте, а затем на втором.

Если использовать метод прямого перебора при наличие n изделий и двух пунктов (машин) существует n! Возможных вариантов. Для нашего примера 720 вариантов.

Алгоритм Джонсона включает следующие этапы:

а) поиск наименьшего элемента. Ищем в таблице наименьший элемент (равен 2 относится ко второй машине), отмечаем его точкой.

б) перестановка изделий. Если этот элемент относится к первой машине, то столбец поставить на первое место, если ко второй, то на последнее место. При наличие равных минимальных элементов в обеих строках, то на первое (последнее) место в таблице ставится изделие, которому соответствует меньший элемент второй (первой) строки.

в) Вычеркивание из таблицы столбца, отмеченного точкой и возвращение к n(а). И так далее, пока не будет исчерпаны все детали.

В результате получим следующую таблицу:

N _изд N _j
t_{1 j}
t _{2 j}

После определения оптимального порядка обработки деталей графически определяем время простоя работы второй машины.

y _min= 29 + 4 + 1 = 34

Алгоритм Джонсона работает только для двух машин, есть частные случаи и для твех машин. В этом случае обработка используется:

а) min {t₁_j} ≥ max {t ₂_j} минимальное время на первой машине не меньше максимума t ₂_j , тогда следует сложение: t₁_j + t ₂_j и рассмотреть их как для I-ой машины, а III машина в качестве II-ой машины.

б) min {t ₃_j} ≥ max {t ₂_j}, то складываем (t ₂_j+ t₃_j) и считают это для II машины.

Этот алгоритм можно использовать при разработке задач календарного планирования, причем рассматривать большое количество машин, при этом объединять время произвольно.

Тема VIII: Игровые задачи.