F2Cmax

Задача:

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

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

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

1. Будем в ходе нашего алгоритма строить два списка [math] L [/math] и [math] R [/math]. Изначально оба списка пусты. И будем поддерживать множество еще не распределенных по спискам [math] L [/math] и [math] R [/math] работ [math]X = \{i \mid i = 1, \dots, n\}[/math]
2. Пока множество [math] X [/math] непусто будем распределять работы по спискам следующим образом:
   • Находим такие индексы [math] i [/math] и [math] j [/math], что [math]p_{ij} = \min \{ p_{ij} \mid i \in X; j = 1, 2\}[/math]
   • Если минимум достигается на первом станке (иными словами [math] j = 1 [/math]), то поставим работу [math] i [/math] в конец списка [math] L [/math], иначе ставим в начало списка [math] R [/math]
   • Удаляем работу [math] i [/math] из множества [math] X [/math]
3. Рассмотрим список [math] T = L \circ R[/math]. Утверждается, что этот список является оптимальной перестановкой работ как на первом, так и на втором станке. Далее расставляем подряд работы на первом станке согласно перестановке, после чего ставим в том же порядке работы на втором станке, при этом избегая одновременного выполнения одной и той же работы.

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

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

Лемма (1):

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Лемма (2):

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Теорема:

Построенная перестановка [math] T [/math] является оптимальной.

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Псевдокод

  function F2Cmax(n: int, p: int[][2]):
     Q = deque()
     X = set()
     while X.size != n:
        Найти [math] i [/math] и [math] j [/math], такие что [math]p_{ij} = \min \{ p_{ij}  \mid i \notin X; j = 1, 2\}[/math]
        if j == 1:
           Q.addLast(i)
        else:
           Q.addFirst(i)
        X.add(i)
     return Q

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

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

Источники

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