3622
правки
Изменения
м
Так как Заметим, что <tex>C_i \geqslant 1forall</tex> для всех <tex>i = 1,\ldots,n</tex>: <tex>C_i \geqslant 1</tex> и <tex>d_i \exists</tex> <tex>i = 01,\ldots,n</tex> хотя бы для одной работы : <tex>id_i = 0</tex>, справедливо . Поэтому <tex>L_i = C_i - d_i \geqslant 1</tex> как минимум для одной работы <tex>i</tex>. К тому же, можно предположить, что <tex>C_i \leqslant r</tex>. Таким образом, работы с <tex>d_i > r - 1</tex>, то есть c <tex>L_i = C_i - d_i < 1</tex>, можно смело игнорировать. Они не влияют на значение улучшаемой функции <tex>\max(L_i)</tex>, так как для некого <tex>i</tex> : <tex>L_i \geqslant 1</tex> можно выполнять эти работы в любом порядке после всех остальных. Для оставшихся операций <tex>O_{ij}</tex> мы имеем:
Количество шагов Суммарное количество операций равно <tex>r</tex>. Первый шаг алгоритма ограничено занимает <tex>O(r)</tex>, так как каждая операция планируется добавляется либо в <tex>L</tex>, либо в <tex>Z</tex>. На втором шаге каждая операция назначается единожды, а всего их то есть на втором шаге также выполняется <tex>O(r)</tex> действий. И, наконец, суммарное время всех вызовов функции <tex>\mathrm{schedule}</tex> также равно <tex>O(r)</tex>, так как суммарное количество итераций циклов внутри этой функции не превышает <tex>O(r)</tex>. Итого, время работы алгоритма <tex>O(r)</tex>.
→Асимптотика
Задача заключается в том, что для данного каждой работе <tex>i</tex> дедлайна <tex>d_i \geqslant 0</tex> нужно найти достижимое расписание с наименьшим максимальным временем опоздания:
<tex>L_{\max} = \max\limits_{C_i - d_i \mid i = 1, ..n}\ldots, n{C_i - d_i\}</tex>
==Описание алгоритма==
Для решения задачи применим следующий алгоритм:
* введём для каждой операции <tex>O_{ij}</tex> величину <tex>l(O_{ij}) = d_i - n_i + j</tex> {{---}} максимальное время завершения <tex>l(O_{ij})</tex>, при котором работа будет завершена не оттягивается время завершения всей работыпозднее дедлайна, при условии, что остальные операции выполняются без задержек вслед за ней,
* создадим список всех операций <tex>L</tex>, упорядоченный в порядке неубывания значений <tex>l(O_{ij})</tex>,
* найдем соответствующее списку <tex>L</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>
Для того, чтобы найти расписание, соответствующее списку всех операций <tex>L</tex>, выполним следующие шаги:*На на первом шаге каждую операцию кладём в соответствующий [[список]] <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> порядку, где операции из одного списка могут выполнятся в произвольном порядке.
==Алгоритм==
'''function''' solve():
<font color=darkgreen>// Шаг 1</font>
<font color=darkgreen>// Инициализируем L и Z</font>
'''for''' k = -r + 1 '''to''' r - 1
T1 = 0
T2 = 0
<font color=darkgreen>// Шаг 2</font>
<font color=darkgreen>// Планируем операции соответственно возрастающему по номеру списка порядку</font>
'''for''' k = -r + 1 '''to''' r - 1
==Асимптотика==
==Доказательство==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 180 {{---}} 186 стр. {{---}} ISBN 978-3-540-69515-8
[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]
[[Категория: Теория расписаний]]
