Изменения
Нет описания правки
<tex>A (B)</tex>, то операция <tex>O_{i,j-1}</tex> должна быть совершена на машине <tex>B (A)</tex>. Задача заключается в том, что для данного каждой <tex>i</tex>-той работе дедлайна <tex>d_i \geqslant 0</tex> необходимо найти достижимое расписание с наименьшими максимальным временем опоздания:
<tex>\max\{C_i - d_i | \mid i = 1, \ldots, n\}</tex>
}}
==Описание решения==
<tex>C_i</tex> {{---}} время окончания работы <tex>i</tex> в достижимом расписании <tex>y = (A(t), B(t))</tex> можно рассчитать как:
<tex>C_i = \max\{t + 1 | \mid A(t)\}</tex> или <tex>B(t)</tex> {{---}} операция <tex>i</tex>-той работы.
Задача заключается в том, что для данного каждой работе <tex>i</tex> дедлайна <tex>d_i \geqslant 0</tex> мы хотим найти достижимое расписание с наименьшим максимальным временем опоздания:
<tex>\max\{C_i - d_i | \mid i = 1, \ldots, n\}</tex>
Следующий алгоритм решает эту задачу:
