MAXimal

добавлено: 11 Jun 2008 11:21
редактировано: 15 Sep 2011 1:36

Задача Джонсона с двумя станками

Имеется $n$ деталей и два станка. Каждая деталь должна сначала пройти обработку на первом станке, затем — на втором. При этом $i$ -ая деталь обрабатывается на первом станке за $a_i$ времени, а на втором — за $b_i$ времени. Каждый станок в каждый момент времени может работать только с одной деталью.

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

Эта задача называется иногда задачей двухпроцессорного обслуживания задач, или задачей Джонсона (по имени S.M. Johnson, который в 1954 г. предложил алгоритм для её решения).

Стоит отметить, что когда число станков больше двух, эта задача становится NP-полной (как доказал Гэри (Garey) в 1976 г.).

Построение алгоритма

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

Рассмотрим порядок подачи деталей на станки, совпадающий с их входным порядком: $1, 2, \ldots, n$ .

Обозначим через $x_i$ время простоя второго станка непосредственно перед обработкой $i$ -ой детали (после обработки $i-1$ -ой детали). Наша цель — минимизировать суммарный простой:

$F(x) = \sum x_i \longrightarrow \min.$

Для первой детали мы имеем:

$x_1 = a_1.$

Для второй — т.к. она становится готовой к отправке на второй станок в момент времени $a_1+a_2$ , а второй станок освобождается в момент времени $x_1 + b_1$ , то имеем:

$x_2 = \max \Big( (a_1+a_2) - (x_1+b_1), 0 \Big).$

Третья деталь становится доступной для второго станка в момент $a_1+a_2+a_3$ , а станок освобождается в $x_1+b_1+x_2+b_2$ , поэтому:

$x_3 = \max \Big( (a_1+a_2+a_3) - (x_1+b_1+x_2+b_2[...]$

Таким образом, общий вид для $x_i$ выглядит так:

$x_k = \max \left( \sum_{i=1}^{k} a_i - \sum_{i=1}[...]$

Посчитаем теперь суммарный простой $F(x)$ . Утверждается, что он имеет вид:

$F(x) = \max_{k=1 \ldots n} K_i,$

где

$K_i = \sum_{i=1}^{k} a_i - \sum_{i=1}^{k-1} b_i.$

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

Воспользуемся теперь перестановочным приёмом: попробуем обменять какие-либо два соседних элемента $j$ и $j+1$ и посмотрим, как при этом изменится суммарный простой.

По виду функции выражений для $K_i$ понятно, что изменятся только $K_j$ и $K_{j+1}$ ; обозначим их новые значения через $K_j^\prime$ и $K_{j+1}^\prime$ .

Таким образом, чтобы деталь $j$ шла до детали $j+1$ , достаточно (хотя и не необходимо), чтобы:

$\max \left( K_j, K_{j+1} \right) \le \max \left( [...]$

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

Отняв $\sum_{i=1}^{j+1} a_i - \sum_{i=1}^{j-1} b_i$ от обеих частей этого неравенства, получим:

$\max (-a_{j+1}, -b_j) \le \max (-b_{j+1}, -a_j),$

или, избавляясь от отрицательных чисел, получаем:

$\min (a_j, b_{j+1}) \le \min (b_j, a_{j+1}).$

Тем самым, мы получили компаратор: отсортировав детали по нему, мы, согласно приведённым выше выкладкам, придём к оптимальному порядку деталей, в котором нельзя переставить местами никакие две детали, улучшив итоговое время.

Впрочем, можно ещё больше упростить сортировку, если посмотреть на этот компаратор с другой стороны. Фактически он говорит нам о том, что если минимум из четырёх чисел $(a_j, a_{j+1}, b_{j}, b_{j+1})$ достигается на элементе из массива $a$ , то соответствующая деталь должна идти раньше, а если на элементе из массива $b$ — то позже. Тем самым мы получаем другую форму алгоритма: отсортировать детали по минимуму из $(a_i, b_i)$ , и если у текущей детали минимум равен $a_i$ , то эту деталь надо обработать первой из оставшихся, иначе — последней из оставшихся.

Так или иначе, получается, что задача Джонсона с двумя станками сводится к сортировке деталей с определённой функцией сравнения элементов. Таким образом, асимптотика решения составляет $O (n \log n)$ .

Реализация

Реализуем второй вариант описанного выше алгоритма, когда детали сортируются по минимуму из $(a_i, b_i)$ , и затем отправляются в начало либо в конец текущего списка.

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;
}

Здесь все детали хранятся в виде структур $\rm item$ , каждая из которых содержит значения $a$ и $b$ и исходный номер детали.

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

Литература

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]