Рассмотрим задачу последовательной обработки на двух машинах N различных деталей, если известно время A i и B i обработки i -й детали на соответствующих машинах. Очевидно, что первая машина будет загружена полностью, но вторая может периодически оказываться в состоянии простоя. Попытаемся найти порядок обработки, минимизирующий время простоя второй машины и тем самым сокращающий общее время обработки деталей.
Если обозначить через X i - время простоя в ожидании i -й детали, то:
A 1
X 1 + X 2 = max(A 1 + A 2 - B 1 , A 1)
X 1 + X 2 + X 3 = max(A 1 + A 2 +A 3 - B 1 - B 2 , A 1 + A 2 - B 1 , A 1)
∑X i = max(∑A i - ∑B i)
Если обозначить через F(t, A k , B k /k=1..N) - суммарное время обработки N деталей при условии, что вторая машина включается с задержкой t и используется оптимальный порядок обработки, то c учетом принципа оптимальности (независимо от выбора начальной детали порядок выбора последующих должен быть оптимальным) имеем:
F(t, A k , B k /k = 1..N) = min(A i + F(B i + max(t-A i ,0),A k ,B k =1..N,k≠i))
Если после i -й детали при оптимальном порядке обрабатывается j -я, то:
F(t, A k , B k /k=1..N) = A i + A j + F(t ij , A k , B k /k=1..N; k≠i,j)
где
t ij = B i + max = B i + B j - A i - A j + max
Если max(A i + A j - B i ,A i) < max(A j + A i - B j , A j), то сначала разумнее обрабатывать j -ю деталь.
Можно показать, что указанное условие необходимости перестановки эквивалентно условию:
min(A j , B i) < min(A i , B j)
Соответственно ищем среди всех значений A i и B i наименьшее. Если найденное значение совпадает с некоторым A i , то i -ю деталь ставим на обработку первой; если оно совпадает с некоторым Bi , то последней. Эту процедуру повторяем для всех остальных деталей.

Пример 1. Пусть информация о времени обработки задана таблицей:

Шаг № 2.
Минимальное из значений равно 3 и соответствует B 2: 2-ая деталь обрабатывается последней.

Шаг № 4.
Минимальное из значений равно 5 и соответствует B 4: 4-ая деталь обрабатывается последней.

Шаг № 6.
Минимальное из значений равно 7 и соответствует B 6: 6-ая деталь обрабатывается последней.

В итоге упорядоченная информация принимает вид:

Время простоя второй машины при первичном порядке равно:
max(2 , 2 + 8 - 3 , 2 + 8 + 4 - 3 - 3 , 2 + 8 + 4 + 9 - 3 - 3 - 6 , 2 + 8 + 4 + 9 + 6 - 3 - 3 - 6 - 5 , 2 + 8 + 4 + 9 + 6 + 9 - 3 - 3 - 6 - 5 - 8) = max(2, 7, 8, 11, 12, 13) = 13
Время простоя при оптимальной перестановке равно:
max(2 , 2 + 4 - 3 , 2 + 4 + 6 - 3 - 6 , 2 + 4 + 6 + 9 - 3 - 6 - 8 , 2 + 4 + 6 + 9 + 9 - 3 - 6 - 8 - 7 , 2 + 4 + 6 + 9 + 9 + 8 - 3 - 6 - 8 - 7 - 5) = max(2, 3, 3, 4, 6, 9) = 9

Пример 2. Пусть информация о времени обработки задана таблицей:

Шаг № 2.
Минимальное из значений равно 3 и соответствует B 1: 1-ая деталь обрабатывается последней.

Шаг № 4.
Минимальное из значений равно 4 и соответствует B 6: 6-ая деталь обрабатывается последней.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Отняв от обеих частей этого неравенства, получим:

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

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

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

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

Реализация

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

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

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

1. Рассматриваются интервалы времени и , определяется величина .

2. Если эта величина находится в столбце , то -ю деталь помещаем на первый станок в первую очередь. Если эта величина находится в столбце , то -я деталь занимает последнее место на первом станке.

3. Вычеркиваем выбранную деталь, и продолжаем процедуру поиска, повторяя шаги 1 и 2. В случае одинаковых значений выбираем любую деталь. Полученная последовательность обработки деталей будет оптимальной.

Пример. Пусть время обработки пяти деталей на двух машинах задана в таблице:

Рисунок 6.2 – Начальное расписание

По графику видно, что начальный порядок обработки деталей допускает простои второго станка (суммарное время простоев 8 единиц), длина производственного цикла равна 30 единицам времени.

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

Продолжаем процедуру поиска. Среди не вычеркнутых элементов ищем . После выбора второй детали минимальное время равно 3, и оно соответствует и . Мы можем выбрать любую деталь, поэтому произвольно выбираем , т. е. помещаем на первое место деталь 1. Теперь минимальное время соответствует . Следовательно, деталь 4 ставится на предпоследнее место.

Следующая минимальная величина равна 4 ( и ). Можем назначить 2-е место на первом станке для детали 3 и 3-е место для детали 5.

i	a i	b i	i¢
1
2
3
4
5

Полученная последовательность обработки деталей на двух станка =(1, 3, 5, 4, 2) будет оптимальной.

Эта последовательность представлена диаграммой Ганта на рис.6.3.

Рисунок 6.3 – Оптимальное расписание

Из рис. 6. 3 видно, что время обработки всех деталей равно 28 единиц и суммарное время простоев - 6 единиц.

Замечание. Алгоритм Джонсона применим для последовательности деталей, проходящих последовательную обработку на 3-х станках, в двух нижеследующих случаях:

или .

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

Пример. Пусть операции над деталями задаются сроками выполнения :

i	a i	b i	c i

Условие , например, выполняется. Таким образом, мы имеем:

i	a i	b i	c i	a i + b i	b i + c i

и алгоритм Джонсона позволяет выбрать =(4, 2, 3, 1, 5).

Задания для самостоятельной работы

Найти решение задачи Джонсона для двух последовательных приборов. Длительности обслуживания приборами А и В приведены в таблице.

вариант	Требование время
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B

ЗАДАЧА О НАЗНАЧЕНИЯХ

Доверенности