577
правок
Изменения
→Описание алгоритма
* множество <tex>C</tex> {{---}} итерации обработки работ <tex>i = k + 1 \ldots n</tex>, которые в <tex>S^*</tex> запланированы на время <tex>k + m + t</tex> и раньше
Таким образом, мы имеем три непересекающихся множества, которые вместе с работой <tex>k</tex> покрывают все итерации всех работ.<br>
Построим новое расписание <tex>S^*</tex>. Для начала расставим все работы из множества <tex>A \cup B</tex> так же, как они были запланированы в расписании <tex>S^*</tex>. Так как <tex>C_i \leqslant m + i - 1</tex> для <tex>i = 1 \ldots k - 1</tex>, ни одна итерация обработки в множестве <tex>B</tex> не поставлена раньше момента времени <tex>k + m + t</tex> и к моменту времени <tex>C_k = m + k + t</tex> выполнено <tex>k</tex> работ, то это значит, что между моментами времени <tex>01</tex> и <tex>k + m - 1</tex> на каждой машине есть <tex>m</tex> различных простоев, то есть моментов, когда на ней ничего не обрабатывается. Значит, мы всегда сможем поставить на эти простои итерации обработки работы <tex>k</tex>, даже если эти простои пересекаются. Таким образом, <tex>C_k \leqslant m + k - 1</tex>.<br>Теперь назначим машины для операций из множества <tex>C</tex>. До момента времени <tex>k + m + t</tex> сейчас распланировано ровно <tex>k</tex> работ, так как по определению работы из множества <tex>B</tex> запланированы на время строго большее <tex>k + m + t</tex>. Значит, между моментами времени <tex>01</tex> и <tex>k + m + t</tex> есть <tex>k + m + t - k = m + t</tex> различных простоев на каждой машине. Исходя из определения множества <tex>C</tex> и того, что к моменту <tex>k + m + t</tex> распланировано <tex>km</tex> итераций обработок, приходим к неравенству <tex>|C| \leqslant (k + m + t)m - km = (m + t)m</tex>. Значит, мы можем распланировать итерации из множества <tex>C</tex> не позднее момента <tex>k + m + t</tex>. Таим образом, мы снова построили расписание для задачи open shop, которое так же является оптимальным, так как для множеств <tex>A</tex> и <tex>B</tex> все осталось как в оптимальном расписании <tex>S^*</tex>, работу <tex>k</tex> мы научились выполнять быстрее, а для множества <tex>C</tex> ответ был не ухудшен. Любая работа <tex>j</tex>, итерации обработки которой принадлежат множеству <tex>C</tex>, имела время окончания <tex>C_j \geqslant m + k + t</tex>. Однако это противоречит тому, что мы выбрали максимальное <tex>k</tex>.
}}
Отсортируем работы в порядке неуменьшения дедлайнов. Для текущей работы <tex>i</tex> вычислим ''лимит'' <tex>T_i</tex> {{---}} время, до которого закончится обработка данной работы, то есть <tex>1 \leqslant t_1 < t_2 < \ldots < t_m \leqslant T_i </tex>, где <tex>t_j</tex>, <tex>j = 1 \ldots m</tex> {{---}} периоды обработки работы <tex>i</tex>.
=== Псевдокод ===
Определим ''вектор частот'' <tex>h(t)</tex> {{---}} количество работ во временном интервале <tex>t</tex>. Работы отсортированы в порядке <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>.
'''for''' <tex>t = 1</tex> '''to''' <tex>m + n - 1</tex>
<tex>h(t) = 0</tex>
'''for''' <tex>i = 1</tex> '''to''' <tex>n</tex>
'''if''' <tex>d_i < m + i - 1</tex>
вычислим <tex>z</tex> {{---}} количество временных интервалов <tex>t = 1 \ldots d_i</tex>, таких, что <tex>h(t) < m</tex>
'''if''' <tex>z \geqslant m</tex>
<tex>T_i = d_i</tex>
'''else'''
<tex>T_i = d_i + m - z</tex>
'''else'''
<tex>T_i = m + i - 1</tex>
вычислим <tex>m</tex> периодов <tex>1 \leqslant t_1 < t_2 < \ldots < t_m \leqslant T_i </tex> с минимальными значениями <tex>h(t_j)</tex>
'''for''' <tex>j = 1</tex> '''to''' <tex>m</tex>
ставим работу <tex>i</tex> на время <tex>[t_j - 1, t_j]</tex>
<tex>h(t_j) = h(t_j) + 1</tex>
=== Асимптотика ===
