Изменения

Найти <tex>x</tex>, где <tex>a_{x} = \max \limits_{i \in I} \{a_{i}\}</tex>

Найти <tex>y</tex>, где <tex>b_{y} = \max \limits_{i \in J} \{b_{i}\}</tex>

Поменять местами первый и второй станок

Пересчитать <tex>I, J, x</tex>

sched1[i] <tex>\leftarrow time1</tex>

<tex>time1 \leftarrow time1 + a_{i}</tex>

sched2[i] <tex>\leftarrow time2</tex>

<tex>time2 \leftarrow time2 + b_{i}</tex>

sched1[i] <tex>\leftarrow time1</tex>

<tex>time1 \leftarrow time1 + a_{i}</tex>

sched2[i] <tex>\leftarrow time2</tex>

<tex>time2 \leftarrow time2 + b_{i}</tex>

sched1[x] <tex>\leftarrow time1</tex>

<tex>time1 \leftarrow time1 + a_{x}</tex>

if станки меняли местами

поменять их обратно

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

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