F2Cmax

Постановка задачи

Рассмотрим задачу:

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

Требуется минимизировать время окончания всех работ.

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

Пусть [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]. Утверждается, что этот лист является оптимальной перестановкой работ как на первом, так и на втором станке. Далее расставляем подряд работы на первом станке согласно перестановке, после чего ставим в том же порядке работы на втором стане, при этом избегая одновременного выполнения одной и той же работы.

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

TODO Доказательство равенства перестановок на первом и втором станках

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

Лемма (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}) \leq 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}) \leq \min(p_{i1}, p_{j2}) [/math], то можем поменять местами эти работы без ухудшение целевой функций.

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

[math]\triangleright[/math]

TODO

[math]\triangleleft[/math]

Псевдокод

  [math]L \leftarrow \varnothing [/math]
  [math]R \leftarrow \varnothing [/math]
  [math]X \leftarrow \{1, \dots, n\}[/math]
  while [math] X \neq \varnothing[/math]
     Найти [math] i [/math] и [math] j [/math], где [math]p_{ij} = \min \{ p_{ij}  \mid i \in X; j = 1, 2\}[/math]
     if j = 1
        [math]L \leftarrow L \circ i [/math]
     else 
        [math]R \leftarrow i \circ R [/math]
     [math]X \leftarrow X \setminus \{i\} [/math]
  [math]T \leftarrow L \circ R[/math]

  Расставляем работы на первом станке согласно перестановке [math] T [/math]
  
  Расставляем работы на втором станке согласно перестановке [math] T [/math]
  и времени начала соответсвующей работы на первом станке.

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

Заметим, что на каждом шаге алгоритма мы выбираем минимум из оставшихся элементов за [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