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].

  for [math]t = 1[/math] to [math]m + n - 1[/math]
     [math]h(t) = 0[/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]i[/math] на время [math][t_j - 1, t_j][/math]
        [math]h(t_j) = h(t_j) + 1[/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