O2Cmax

$O2 \mid \mid C_{max}$

Задача:

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

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

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

1. Разобьём все работы на два множества: $I = \{i \mid a_{i} \leqslant b_{i}; i = 1, \dots, n\}$ и $J = \{i \mid a_{i} \gt b_{i}; i = 1, \dots, n\}$.
2. Найдем такие $x$ и $y$, что $a_{x} = \max \limits_{i \in I} \{a_{i}\}$ и $b_{y} = \max \limits_{i \in J} \{b_{i}\}$.
3. Построим оптимальное значение целевой функции: $C_{max} = \max \{\sum \limits_{i = 1}^{n} a_i, \ \sum \limits_{i = 1}^{n} b_i,\ \max \limits_{i = 1}^{n}\{a_i + b_{i}\}\}$.
4. Рассмотрим два случая:
   1. $a_{x} \gt b_{y}$. Будем строить расписание с двух концов:
      • Строим расписание слева: выполняем на первом станке все работы из $I \setminus \{x\}$, а на втором выполняем первой работу $x$, затем $I \setminus \{x\}$ в том же порядке, что и на первом станке.
      • Теперь, упираясь в правую границу, равную $C_{max}$, можно построить расписание справа: выполняем на первом станке все работы из $J$, затем $x$, а для второго выполняем работы из $J$.
        
   2. $a_{x} \leqslant b_{y}$. Сводится к первому, если поменять местами станки и соответствующие списки времён выполнения, при этом надо заново выполнить пункты 1,2 и 3. При выдаче ответа меняем станки обратно местами.

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

Теорема:

Расписание, построенное данным алгоритмом, является корректным и оптимальным.

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

$\triangleright$

Чтобы доказать корректность, надо доказать, что на каждом станке в любой момент времени выполняется не более одной работы, и что каждая работа в каждый момент времени выполняется не более, чем на одном станке. Первое утверждение вытекает из того, что мы строили расписание, опираясь на $C_{max}$. Из построения $C_{max} \geqslant \sum \limits_{i = 1}^{n}a_{i}, \sum \limits_{i = 1}^{n}b_{i}$, следовательно на каждом станке в любой момент времени выполняется не более одной работы. Докажем теперь второе утверждение. У нас имеется три блока работ: $I \setminus \{x\}, \{x\}, J$. Для блока $\{x\}$ это следует из того, что $C_{max} \geqslant a_{x}+b_{x}$, а работа $x$ выполняется с разных концов станков. Получили, что отрезки выполнения работы $x$ на разных станках не пересекаются. Покажем, что любая работа из $I \setminus \{x\}$ начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму: $\sum \limits_{i = 1}^k a_{i} \leqslant \sum \limits_{i = 1}^k b_{i} = \sum \limits_{i = 1}^{k - 1} b_{i} + b_{x}$, где $1 \dots k$ — это работы, выполняемые на первом станке во время данного блока. Это неравенство следует из выбора $I$ и из того, что $b_{x} \geqslant a_{x} \geqslant a_{i}, \forall i \in I$. Получили, что каждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом. Покажем, что любая работа из $J$ начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму: $\sum \limits_{i = 1}^k b_{i} \leqslant \sum \limits_{i = 1}^k a_{i} \leqslant \sum \limits_{i = 1}^{k - 1} a_{i} + a_{x}$, где $1 \dots k$ — это работы, выполняемые на втором станке во время данного блока. Это неравенство следует из выбора $J$ и из того, что $a_{x} \geqslant a_{i}, \forall i \in I$. Получили, что каждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом. Итого мы доказали корректность. Оптимальность вытекает из того, что $C_{max}$ не может быть меньше $\sum \limits_{i = 1}^{n} a_i,\ \sum \limits_{i = 1}^{n} b_i, \ \max \limits_{i = 1}^{n}\{a_i + b_{i}\}$, а из построения оно равно максимуму из этих значений.

$\triangleleft$

Псевдокод

//Функция принимает список из времён выполнения на первом станке a и времён выполнения на втором станке b.
//Функция возвращает пару из расписания для первого станка и расписания для второго станка.
function scheduling(a: int[n], b: int[n]): pair<int[n], int[n]>
    $I = \varnothing$
    $J = \varnothing$
    $C_{max} = \max \{\sum \limits_{i = 1}^{n} a_i, \  \sum \limits_{i = 1}^{n} b_i, \  \max \limits_{i = 1}^{n}\{a_i + b_{i}\}\}$
    for $i = 1$ to $n$
       if $a_{i} \leqslant b_{i}$
          $I = I \cup \{i\}$
       else
          $J = J \cup \{i\}$
    Найти $x$, где $a_{x} = \max \limits_{i \in I} \{a_{i}\}$
    Найти $y$, где $b_{y} = \max \limits_{i \in J} \{b_{i}\}$
    if $a_{x} \gt  b_{y}$
        Начиная с $0$ на первом станке расставляем расписание для $I \setminus \{x\}$
        Начиная с $0$ на втором станке расставляем расписание для $\{x\}$, затем для $I \setminus \{x\}$

        От правой границы — $C_{max}$ на первом станке расставляем расписание для $\{x\}$, затем для $J$
        От правой границы — $C_{max}$ на втором станке расставляем расписание для $J$

        pair<int[n], int[n]> ans = пара из расписания для первого станка и расписания для второго станка 
        return ans
    else
        pair<int[n], int[n]> ans = scheduling(b, a)
        Меняем местами расписания для станков в ans
        return ans

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

Каждое из множеств в сумме содержит $n$ элементов. Следовательно, чтобы найти максимум в каждом из множеств нам потребуется $O(n)$ операций, чтобы составить расписание для каждой работы из множества нам потребуется так же $O(n)$ операций. Получаем сложность алгоритма $O(n)$.

См. также

• $P2 \mid prec, p_i = 1 \mid L_{\max}$
• $R2 \mid \mid C_{max}$
• $F2 \mid \mid C_{max}$
• $O2 \mid \mid C_{max}$
• $J2 \mid n_{i} \leqslant 2 \mid C_{max}$
• $J2\mid p_{ij} = 1\mid L_{max}$

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

• Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 158—160 ISBN 978-3-540-69515-8