[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]0[/math] и [math]k + m - 1[/math] на каждой машине есть [math]m[/math] различных простоев, то есть моментов, когда на ней ничего не обрабатывается. Значит, мы всегда сможем поставить на эти простои итерации обработки работы [math]k[/math], даже если эти простои пересекаются. Таким образом, [math]C_k \leqslant m + k - 1[/math]. |
| [math]\triangleleft[/math] |
Псевдокод
Асимптотика
Доказательство корректности
См. также
Источники информации
- Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 171-174 ISBN 978-3-540-69515-8
