F2Cmax

$F2 \mid\mid C_{max}$

Задача:

Рассмотрим задачу: дано $n$ работ и $2$ станка, для каждой работы известно её время выполнения на каждом станке $p_{ij}$, каждую работу необходимо выполнить сначала на первом станке, а потом на втором. Требуется минимизировать время окончания выполнения всех работ.

Описание алгоритма

Пусть $p_{i1}$ — время выполнения $i$-ой работы на первом станке, а $p_{i2}$ — на втором.

1. Алгоритм строит два списка $L$ и $R$. Изначально они пусты. Также поддерживается множество еще не распределенных по спискам $L$ и $R$ работ $X = \{i \mid i = 1, \dots, n\}$
2. Пока множество $X$ не пусто, распределяем работы по спискам следующим образом:
   • находим такие индексы $i$ и $j$, что $p_{ij} = \min \{ p_{ij} \mid i \in X \land j = 1, 2\}$,
   • если минимум достигается на первом станке (иными словами $j = 1$), то поставим работу $i$ в конец списка $L$, иначе ставим в начало списка $R$,
   • удаляем работу $i$ из множества $X$.
3. Рассмотрим список $T = L ~\texttt{++}~ R$ — конкатенацию $L$ и $R$. Утверждается, что этот список является оптимальной перестановкой работ как на первом, так и на втором станке. Далее расставляем подряд работы на первом станке согласно перестановке, после чего ставим в том же порядке работы на втором станке, при этом избегая одновременного выполнения одной и той же работы.

Доказательство корректности алгоритма

Теорема:

Существует оптимальное расписание, в котором станки выполняют работы в одном и том же порядке.

Доказательство:

$\triangleright$

Рис. 1 Предположим обратное: что не существует оптимального расписания с одинаковыми перестановками работ на станках. Рассмотрим некоторое оптимальное расписание с максимальным по длине общим префиксом на станках. Пусть его длина равна $k$, где $k \lt n$. Пусть на $k$ позиции на первом и втором станках стоит работа $i$, а на втором станке на позиции $k + 1$ стоит работа $j$. Тогда заметим, что если мы поставим работу $j$ на первом станке сразу после работы $i$, то последовательные работы с $h$ по $m$ (см. рис. 1) по-прежнему будут успевать выполниться, так как на втором станке они выполняются в текущем расписании после $j$. Таким образом нам удалось увеличить длину наибольшего общего префикса, а так как по нашему предположению она была максимальна, то предположение неверно и искомое расписание с одинаковым порядком выполнения работ на обоих станках существует.

$\triangleleft$

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

Лемма (1):

Если для каких-то работ $i$ и $j$ из списка $T$ верно неравенство $\min(p_{i1}, p_{j2}) \lt \min(p_{j1}, p_{i2})$, то работа $i$ встречается в списке $T$ раньше, чем $j$.

Доказательство:

$\triangleright$

Пусть $p_{i1} \lt p_{j2}$. Случай $p_{i1} \gt p_{j2}$ рассматривается аналогично. Так как $p_{i1} \lt \min(p_{j1}, p_{i2}) \leqslant p_{i2}$, то работа $i \in L$. Работа $j$ либо стоит в $R$, либо она стоит в $L$ и при этом $p_{i1} \lt p_{j1}$. Заметим, что в обоих случаях она расположена позже (в силу нашего построения), чем работа $i$.

$\triangleleft$

Лемма (2):

Пусть имеем произвольное расписание, в котором работа $j$ идет сразу же после работы $i$. Тогда если $\min(p_{j1}, p_{i2}) \leqslant \min(p_{i1}, p_{j2})$, то можем поменять местами эти работы без ухудшения целевой функции.

Доказательство:

$\triangleright$

Рис. 2 — Расположение последовательных работ Пусть $w_{ij}$ — время, прошедшее с начала выполнения работы $i$ на первом станке до окончания работы $j$ на втором станке. Рассмотрим возможные случаи расположения работ $i$ и $j$ (см. Рис. 2) Работа $i$ начинается на втором станке сразу же после завершения ее на первом Выполнение работы $i$ на втором станке заканчивается позже, чем работы $j$ на первом. Тогда $w_{ij} = p_{i1} + p_{i2} + p_{j2}$. Выполнение работы $i$ на втором станке заканчивается раньше, чем работы $j$ на первом. В этом случае $w_{ij} = p_{i1} + p_{j1} + p_{j2}$. Работа $i$ не может начаться на втором станке сразу же после завершения ее на первом Выполнение работы $i$ на втором станке заканчивается раньше, чем работы $j$ на первом. Здесь снова имеем $w_{ij} = p_{i1} + p_{j1} + p_{j2}$. Выполнение работы $i$ на втором станке заканчивается позже, чем работы $j$ на первом. Пусть $\Delta$ — время прошедшее с начала выполнения работы $i$ на первом станке и до начала ее выполнения на втором станке. Получили, что $w_{ij} = \Delta + p_{i2} + p_{j2}$. Таким образом, $w_{ij} = \max (p_{i1} + p_{j1} + p_{j2}, p_{i1} + p_{i2} + p_{j2}, \Delta + p_{i2} + p_{j2})$. Иначе говоря, $w_{ij} = \max (p_{i1} + \max(p_{j1}, p_{i2}) + p_{j2}, \Delta + p_{i2} + p_{j2})$. Аналогично, $w_{ji} = \max (p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2}, \Delta + p_{i2} + p_{j2})$ Так как $\min(a, b) = - \max(-a, -b)$, то из условия леммы имеем $\max(-p_{i1}, -p_{j2}) \leqslant \max(-p_{j1}, -p_{i2})$. Добавив $p_{i1} + p_{i2} + p_{j1} + p_{j2}$ к обеим частям, получим, что $p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2} \leqslant p_{i1} + \max(p_{j1}, p_{i2}) + p_{j2}$, то есть $w_{ji} \leqslant w_{ij}$ и при смене местами работ $i$ и $j$ ответ не ухудшается.

$\triangleleft$

Теорема:

Построенная перестановка $T$ является оптимальной.

Доказательство:

$\triangleright$

Рассмотрим произвольную перестановку $S$. Пусть перестановки $T$ и $S$ имеют общий префикс длины $l-1$. Пусть $i = T_{l}$ и $j = S_{l}$. Рассмотрим множество работ $M = \{T_{r} \mid r = l, \dots, n\}$. Заметим, что для любой работы $k \in M$ верно, что $\min(p_{k1}, p_{i2}) \geqslant \min(p_{i1}, p_{k2})$, так как если было бы верно обратное, то есть $\min(p_{k1}, p_{i2}) \lt \min(p_{i1}, p_{k2})$, то по лемме 1 было бы верно, что $k$ идет раньше $i$, что неверно. Очевидно, что в перестановке $S$ работа $i$ будет стоять после $j$ (иначе общий префикс был бы длиннее), то заметим, что в этой перестановке для работы $i$ и для предыдущей работы $w$ верно $\min(p_{w1}, p_{i2}) \geqslant \min(p_{i1}, p_{w2})$ (так как $w \in M$), то по лемме 2 можем поменять местами работы $i$ и $w$ без ухудшения ответа. То такими операциями сможем дойти до пары работ $i$ и $j$, которые при смене увеличат общий префикс перестановок $S$ и $T$. Таким образом любая перестановка сводится к нашей без ухудшения ответа такими операциями, что подтверждает оптимальность перестановки $T$

$\triangleleft$

Псевдокод

  function F2Cmax(p: int[n][2]): list<int>
     list<int> L = $\varnothing$
     list<int> R = $\varnothing$
     set<int> X = $\{1, \ldots, n\}$
     while X $\neq \varnothing$
        Найти i и j, такие что $p_{ij} = \min \{ p_{ij} \mid i \in X \land j = 1, 2\}$
        if j == 1
           L.addLast(i)
        else 
           R.addFirst(i)
        X.remove(i)
     list<int> T = L ++ R
     return T

Сложность алгоритма

Заметим, что на каждом шаге алгоритма мы выбираем минимум из оставшихся элементов за $O(\log n)$ (либо предварительной сортировкой, либо с помощью любой структуры данных, поддерживающей нахождение минимума и удаление за $O(\log n)$, например, кучи). А так как мы делаем это $n$ раз, алгоритм работает за $O(n\log n)$.

См. также

• $J2 \mid n_i \leqslant 2 \mid C_{max}$
• $O2\mid\mid C_{max}$
• $R2\mid\mid C_{max}$

Источники информации

• Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 175 стр. — ISBN 978-3-540-69515-8