E142. 문제 Джонсона с двумя станками

Источник: e-maxx.ru/algo, страница PDF 471.

Имеется

деталей и два станка. Каждая деталь должна сначала пройти обработку на первом станке, затем — на

втором. При этом

-ая деталь обрабатывается на первом станке за

времени, а на втором — за

времени. Каждый станок в каждый момент времени может работать только с одной деталью. it is required составить такой порядок подачи деталей на станки, чтобы итоговое время обработки всех деталей было бы минимальным. Эта 문제 называется иногда задачей двухпроцессорного обслуживания задач, или задачей Джонсона (по имени S. M. Johnson, который в 1954 г. предложил 알고리즘 для её решения). Стоит отметить, что когда number станков больше двух, эта 문제 становится NP-полной (как доказал Гэри (Garey) в 1976 г.).

Построение 알고리즘а

Заметим вначале, что можно считать, что порядок обработки деталей на первом и втором станках должен совпадать. В самом деле, т.к. детали для второго станка становятся доступными только после обработки на первом, а при наличии нескольких доступных для второго станка деталей время их

обработки будет равно сумме их

независимо от их порядка — то выгоднее всего отправлять на второй станок ту из деталей, которая раньше других прошла обработку на первом станке. Рассмотрим порядок подачи деталей на станки, совпадающий с их 입력ным порядком: .

Обозначим через

время простоя второго станка непосредственно перед обработкой

-ой детали

(после обработки

-ой детали). Наша цель — минимизировать суммарный простой: Для первой детали мы имеем: Для второй — т.к. она становится готовой к отправке на второй станок в момент времени

, а второй

станок освобождается в момент времени

, то имеем:

Третья деталь становится доступной для второго станка в момент

, а станок освобождается

в

, поэтому:

Таким образом, общий вид для

выглядит так:

Посчитаем теперь суммарный простой

. Утверждается, что он имеет вид:

где

(В это можно убедиться по индукции, либо последовательно находя выражения для суммы первых двух, трёх, и т.д.

.)

Воспользуемся теперь перестановочным приёмом: попробуем обменять какие-либо два соседних elementа

и

и посмотрим, как при этом изменится суммарный простой.

По виду функции выражений для

понятно, что изменятся только

и

; обозначим их новые значения через

и

.

Таким образом, чтобы деталь

шла до детали

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

, получив

тем самым достаточное, но не необходимое 문제 설명 того, что старое

меньше либо равно нового значения)

Отняв

от обеих частей этого неравенства, получим: или, избавляясь от отрицательных чисел, получаем: Тем самым, мы получили компаратор: отсортировав детали по нему, мы, согласно приведённым выше выкладкам, придём к оптимальному порядку деталей, в котором нельзя переставить местами никакие две детали, улучшив итоговое время. Впрочем, можно ещё больше упростить сортировку, если посмотреть на этот компаратор с другой стороны. Фактически он говорит нам о том, что если минимум из четырёх чисел

достигается

на elementе из 배열а

, то соответствующая деталь должна идти раньше, а если на elementе из 배열а

— то

позже. Тем самым мы получаем другую форму 알고리즘а: отсортировать детали по минимуму из

, и если

у текущей детали минимум равен

, то эту деталь надо обработать первой из оставшихся, иначе — последней из оставшихся. Так или иначе, получается, что 문제 Джонсона с двумя станками сводится к сортировке деталей с определённой функцией сравнения elementов. Таким образом, Asymptotic complexity решения составляет .

구현

Реализуем второй вариант описанного выше 알고리즘а, когда детали сортируются по минимуму из

, и

затем отправляются в начало либо в конец текущего списка.

struct item {

int a, b, id;

bool operator< (item p) const {

return min(a,b) < min(p.a,p.b);

} };

sort (v.begin(), v.end());

vector<item> a, b;

for (int i=0; i<n; ++i)

(v[i].a<=v[i].b ? a : b) .push_back (v[i]);

a.insert (a.end(), b.rbegin(), b.rend());

int t1=0, t2=0;

for (int i=0; i<n; ++i) {

t1 += a[i].a;

t2 = max(t2,t1) + a[i].b;

}

Здесь все детали хранятся в виде структур

, каждая из которых содержит значения

и

и исходный номер детали.

Детали сортируются, затем распределяются по спискам

(это те детали, которые были отправлены в начало очереди) и

(те, что были отправлены в конец). После этого два списка объединяются (причём второй список берётся в обратном порядке), и затем по найденному порядку вычисляется искомое минимальное время: поддерживаются

две переменные

и

— время освобождения первого и второго станка соответственно.

References

● S.M. Johnson. Optimal two- and three-stage production schedules with setup

times included [1954]

● M.R. Garey. The Complexity of Flowshop and Jobshop Scheduling [1976]