Изменения
Нет описания правки
<tex>A (B)</tex>, то операция <tex>O_{i,j-1}</tex> должна быть совершена на машине <tex>B (A)</tex>.
Задача заключается в том, что для данного каждой <tex>i</tex>-той работе дедлайна <tex>d_i \ge geqslant 0</tex> необходимо найти достижимое расписание с наименьшими максимальным временем опоздания:
<tex>\max\{C_i - d_i | 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 | 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 | i = 1, \ldots, n\}</tex>
Следующий алгоритм решает эту задачу:
* Введём введём для каждой операции <tex>O_{ij}</tex> величину <tex>l(O_{ij}) = d_i - n_i + j</tex>,* Создадим создадим список всех операций <tex>L</tex>, упорядоченный в порядке неубывания значений <tex>l(O_{ij})</tex> , * Найдем найдем соответствующее списку <tex>L</tex> расписание.
Этот алгоритм может быть реализованным реализован с асимптотикой <tex>O(r \log r)</tex>.
Мы предполагаем, что <tex>d_i \geqslant 0</tex> для <tex>i = 1,\ldots,n</tex> и хотя бы для одной работы <tex>i</tex> <tex>d_i = 0</tex>. Иначе, вычтем из всех <tex>d_i</tex> минимальное значение по <tex>d_i</tex>.
<tex>-r + 1 \leqslant l(O_{ij}) = d_i - n_i + j \leqslant r - 1</tex>
Каждую операцию мы кладём в соответствующий список (на самом деле это должен быть куча (англ. ''heap '') для хорошей асимптотики) <tex>L(k)</tex>, где <tex>k = l(O_{ij}) = d_i - n_i + j</tex> <tex>(-r + 1 \leqslant k \leqslant r - 1)</tex>. На втором шаге мы планируем операции соответственно возрастающему по номеру списка <tex>k</tex> порядку, где операции из одного списка могут выполнятся в произвольном порядке.
==Алгоритм==
