Opij1SumTi

[math] O \mid p_{i,j} = 1 \mid \sum T_{i} [/math]

Задача:

Дано [math]m[/math] одинаковых станков, которые работают параллельно, и [math]n[/math] работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания [math]d_i[/math] — время, до которого она должна быть выполнена. Необходимо минимизировать суммарную медлительность.

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

Идея

Будем полагать, что работы заданы в порядке неубывания их дедлайнов, то есть [math]d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n[/math].

Лемма:

Пусть есть работы [math]1 \ldots n[/math] с дедлайнами [math]d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n[/math]. Тогда существует оптимальное расписание, в котором времена завершения работ идут в том же порядке, то есть [math]C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n[/math].

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

[math]\triangleright[/math]

Рассмотрим две работы [math]i[/math] и [math]j[/math] из какого-либо оптимального расписания такие, что [math]C_i \gt C_j[/math] и [math]d_i \lt d_j[/math]. Поменяем эти работы в расписании местами, то есть [math]C'_i = C_j[/math] и [math]C'_j = C_i[/math]. Если они обе успевали выполниться вовремя, то это свойство сохранится, так как [math]d_i \lt d_j[/math], значит по-прежнему [math]T_i = 0[/math] и [math]T_j = 0[/math], то есть значение целевой функции мы не ухудшили и расписание осталось оптимальным. Если обе работы не успевали выполниться вовремя, то когда мы поменяем их местами ничего не изменится, то есть значение целевой функции останется прежним, так как мы не меняли значения времен окончаний, а только поменяли их местами. Если работа [math]j[/math] успевала выполниться, а [math]i[/math] — нет, то мы снова не ухудшим значение целевой функции. Покажем это. До того, как мы поменяли работы местами, было [math]T_i + T_j = C_i - d_i[/math], так как [math]T_j = 0[/math]. После того, как мы поменяли работы местами, [math]T_i + T_j = C'_i - d_i + C'_j - d_j = C_j - d_i + C_i - d_j = C_i - d_i + (C_j - d_j)[/math]. Но так как работа [math]j[/math] успевает выполниться до дедлайна, то [math]C_j - d_j \leqslant 0[/math].

[math]\triangleleft[/math]

Далее будем рассматривать только оптимальное расписание со свойством [math]C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n[/math].

Теорема:

Всегда существует оптимально расписание такое, что в нем [math]C_i \leqslant m + i - 1[/math] для любого [math]i = 1 \ldots n[/math], где [math]m[/math] — количество станков.

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

[math]\triangleright[/math]

Рассмотрим оптимальное расписание [math]S^*[/math], в котором для любого [math]i = 1 \ldots k - 1[/math] выполняется [math]C_i \leqslant m + i - 1[/math], но [math]C_k \gt m + k - 1[/math], где [math]k[/math] максимально среди всех возможных. Для начала покажем, что [math]k[/math] не меньше [math]2[/math]. Пусть есть оптимальное расписание, у которого [math]C_1 \gt m[/math]. Это значит, что есть период времени [math]t[/math] такой, что первая работа выполняется в момент [math]t[/math] и не выполняется в [math]t - 1[/math]. Поменяем эти периоды времени местами. То есть все работы, которые выполнялись в момент [math]t - 1[/math], будут выполняться на тех же станках, но в момент [math]t[/math], и наоборот. Значение [math]C_i[/math] для каждой работы [math]i[/math] не увеличится, так как [math]C_1[/math] было минимальным из них, а значит ни одна работа не могла быть закончена раньше периода времени [math]t[/math]. Будем продолжать этот процесс, пока не будет выполнено равенство [math]C_1 = m[/math]. Теперь пусть [math]C_k = m + k + t[/math], где [math]t \geqslant 0[/math]. Будем называть итерацией обработки работы обработку на одной машине. Разобьем все работы на три множества: множество [math]A[/math] будет содержать все итерации обработки работ [math]i = 1 \ldots k - 1[/math] множество [math]B[/math] — все итерации, запланированные в расписании [math]S^*[/math] строго после момента времени [math]k + m + t[/math] множество [math]C[/math] — итерации обработки работ [math]i = k + 1 \ldots n[/math], которые в [math]S^*[/math] запланированы на время [math]k + m + t[/math] и раньше Таким образом, мы имеем три непересекающихся множества, которые вместе с работой [math]k[/math] покрывают все итерации всех работ. Построим новое расписание [math]S^*[/math]. Для начала расставим все работы из множества [math]A \cup B[/math] так же, как они были запланированы в расписании [math]S^*[/math]. Так как [math]C_i \leqslant m + i - 1[/math] для [math]i = 1 \ldots k - 1[/math], ни одна итерация обработки в множестве [math]B[/math] не поставлена раньше момента времени [math]k + m + t[/math] и к моменту времени [math]C_k = m + k + t[/math] выполнено [math]k[/math] работ, то это значит, что между моментами времени [math]1[/math] и [math]k + m - 1[/math] на каждой машине есть [math]m[/math] различных простоев, то есть моментов, когда на ней ничего не обрабатывается. Значит, мы всегда сможем поставить на эти простои итерации обработки работы [math]k[/math], даже если эти простои пересекаются. Таким образом, [math]C_k \leqslant m + k - 1[/math]. Теперь назначим машины для операций из множества [math]C[/math]. До момента времени [math]k + m + t[/math] сейчас распланировано ровно [math]k[/math] работ, так как по определению работы из множества [math]B[/math] запланированы на время строго большее [math]k + m + t[/math]. Значит, между моментами времени [math]1[/math] и [math]k + m + t[/math] есть [math]k + m + t - k = m + t[/math] различных простоев на каждой машине. Исходя из определения множества [math]C[/math] и того, что к моменту [math]k + m + t[/math] распланировано [math]km[/math] итераций обработок, приходим к неравенству [math]|C| \leqslant (k + m + t)m - km = (m + t)m[/math]. Значит, мы можем распланировать итерации из множества [math]C[/math] не позднее момента [math]k + m + t[/math]. Таим образом, мы снова построили расписание для задачи open shop, которое так же является оптимальным, так как для множеств [math]A[/math] и [math]B[/math] все осталось как в оптимальном расписании [math]S^*[/math], работу [math]k[/math] мы научились выполнять быстрее, а для множества [math]C[/math] ответ был не ухудшен. Любая работа [math]j[/math], итерации обработки которой принадлежат множеству [math]C[/math], имела время окончания [math]C_j \geqslant m + k + t[/math]. Однако это противоречит тому, что мы выбрали максимальное [math]k[/math].

[math]\triangleleft[/math]

Отсортируем работы в порядке неуменьшения дедлайнов. Для текущей работы [math]i[/math] вычислим лимит [math]T_i[/math] — время, до которого закончится обработка данной работы, то есть [math]1 \leqslant t_1 \lt t_2 \lt \ldots \lt t_m \leqslant T_i [/math], где [math]t_j[/math], [math]j = 1 \ldots m[/math] — периоды обработки работы [math]i[/math]. Будем выбирать эти периоды среди моментов времени, в которые выполняется наименьшее число работ.

Псевдокод

Определим вектор частот [math]h[t][/math] — количество работ во временном интервале [math]t[/math]. Работы отсортированы в порядке [math]d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n[/math].

  function scheduler():
     int [math]h[m + n - 1][/math]
     vector<int> [math]s[n][/math]
     fill([math]h,\ 0[/math])
     fill([math]s,\ \varnothing[/math])  
     for [math]i = 1[/math] to [math]n[/math]
        if [math]d_i \lt  m + i - 1[/math]
           вычислим [math]z[/math] — количество временных интервалов [math]t = 1 \ldots d_i[/math], таких, что [math]h[t] \lt  m[/math]
           if [math]z \geqslant m[/math]
              [math]T_i = d_i[/math]
           else 
              [math]T_i = d_i + m - z[/math]
        else
           [math]T_i = m + i - 1[/math]
        вычислим [math]m[/math] периодов [math]1 \leqslant t_1 \lt  t_2 \lt  \ldots \lt  t_m \leqslant T_i [/math] с минимальными значениями [math]h[t_j][/math]
        for [math]j = 1[/math] to [math]m[/math]
           [math]s[i] =  s[i] \cup \{t_j - 1\}[/math]         // ставим работу [math]i[/math] на время [math][t_j - 1, t_j][/math]
           [math]h[t_j] = h[t_j] + 1[/math]
     return [math]s[/math]

Асимптотика

Алгоритм может работать за [math]O(nm)[/math]. Чтобы получить алгоритм с такой сложностью, мы распределяем работы так, чтобы после каждого шага [math]i[/math] сохранялся инвариант [math]l_1 \geqslant l_2 \geqslant \ldots \geqslant l_m [/math] при [math]l_1 \geqslant T_i[/math], где [math]l_j[/math] такое, что на станке [math]M_j[/math] все временные промежутки [math]1 \ldots l_j[/math] заняты. На первом шаге алгоритма [math] l_1 = l_2 = \ldots = l_m = 0 [/math]. Предположим, что инвариант сохранился после шага [math] i - 1 [/math]. Тогда [math] T_{i-1} \leqslant T_i [/math] и, для сохранения инварианта, распределим работу в следующем порядке:

[math]l_1 + 1 \ldots T_i[/math] на станке [math] M_1 [/math],

[math]l_2 + 1 \ldots l_1[/math] на станке [math] M_2 [/math],
[math] \vdots [/math]
[math]l_m + 1 \ldots l_{m-1}[/math] на станке [math] M_1 [/math].

Таким образом, мы получаем распределение одной работы по [math]m[/math] станкам для [math]n[/math] работ. Итоговая асимптотика — [math]O(nm)[/math].

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

Теорема:

Алгоритм строит оптимальное расписание для задачи [math] O \mid p_{i,j} = 1 \mid \sum T_{i} [/math]

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

[math]\triangleright[/math]

Воспользуемся для доказательства леммой и теоремой из предыдущего пункта. Из них мы знаем, что существует оптимальное расписание, для которого выполняются свойства [math]C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n[/math] и [math]C_i \leqslant m + i - 1[/math] для любого [math]i = 1 \ldots n[/math], где [math]m[/math] — число станков. Пусть [math]B[/math] — оптимальное расписание, которое удовлетворяет свойству, по которому работы [math]1 \ldots k - 1 [/math] поставлены в те же временные промежутки, в которых они оказались следуя нашему расписанию [math]A[/math]. Более того, предположим, что [math]B[/math] было выбрано так, что [math]k[/math] максимально. Пусть [math]C_k \gt T_k[/math]. С того момента, как работа [math]k[/math] поставлена в расписании [math]A[/math] перед [math]T_k[/math], определим временной промежуток [math]t \leqslant T_k [/math] в месте, где работа [math]k[/math] не выполняется в [math]B[/math]. Тогда в самом расписании [math]B[/math] этот промежуток либо так же пустой, либо он занят работой [math]r \gt k[/math]. Если он пустой, мы перемещаем операцию [math]k[/math], которая была распределена в промежуток [math]C_k[/math], в этот промежуток. Если работа [math]r[/math] стоит во время [math]t[/math], но не во время [math]C_k[/math], то мы меняем между собой операции работ [math]k[/math] и [math]r[/math]. Если работа [math]r[/math] поставлена во время [math]t[/math] и [math]C_k[/math], то либо тут есть пустое место в [math]C_r + 1[/math], либо там должна быть работа, назовем ее [math]v[/math], которая поставлена на время [math]C_r + 1[/math], но не поставлена в [math]C_k[/math]. Работа [math]v[/math] точно там есть, потому что [math]r[/math] и [math]k[/math] поставлены на время [math]C_k[/math], но не поставлены на время [math]C_r + 1[/math]. Если свободный промежуток есть, тогда переставим работу [math]r[/math] со времени [math]t[/math] на время [math]C_r + 1[/math] и работу [math]k[/math] со времени [math]C_k[/math] на [math]t[/math]. Иначе мы можем переместить работу [math]r[/math] с времени [math]t[/math] на время [math]C_r + 1[/math], [math]k[/math] c [math]C_k[/math] на [math]t[/math], и [math]v[/math] с [math]C_r + 1[/math] на [math]C_k[/math]. Тогда [math]C_k[/math] должно уменьшиться как минимум на один, а [math]C_r[/math] увеличится не больше, чем на один. Если мы продолжим так действовать, мы получим оптимальное расписание [math]B'[/math] с [math]C_k \leqslant T_k[/math], в котором работы [math]1 \ldots k-1[/math] расположены так же, как в расписании [math]A[/math]. Пусть [math]h[/math] — вектор частот для части расписания из работ от [math]1[/math] до [math]k - 1[/math]. Предположим, что [math]h(t') \lt h(t)[/math] и работа [math]k[/math] выполняется во временной промежуток [math]t[/math], но не выполняется в [math]t'[/math] в расписании [math]B'[/math]. Если в [math]B'[/math] станок простаивает во время [math]t'[/math], мы можем переместить работу [math]k[/math] из [math]t[/math] в [math]t'[/math]. Иначе работа [math]r \gt k[/math] находится в расписании в промежутке [math]t'[/math], но ее нет в [math]t[/math]. Мы можем передвинуть [math]r[/math] в [math]t[/math] и [math]k[/math] в [math]t'[/math] без увеличения целевой функции, потому что [math]C_k \leqslant C_r[/math]. Продолжая действовать таким образом, мы достигнем оптимального расписания, в котором работы [math]1 \ldots k[/math] расположены таким же образом, как и в [math]A[/math]. Мы получили противоречие, так как выбранный [math]k[/math] оказался не максимальным.

[math]\triangleleft[/math]

См. также

• [math]O2 \mid \mid C_{max}[/math]
• [math]O \mid p_{ij} = 1 \mid \sum U_i[/math]
• [math] O \mid p_{i, j} = 1, d_i \mid - [/math]
• [math] O \mid p_{i, j} = 1 \mid - \sum w_{i} U_{i}[/math]

Источники информации

• Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 171-174 ISBN 978-3-540-69515-8