Изменения

Дано <tex>n</tex> работ <tex>i = 1,\ldots,n</tex> и две машины, обозначенные как <tex>A</tex> и <tex>B</tex>. <tex>i</tex>-тая работа состоит из <tex>n_i</tex> операций <tex>O_{ij}</tex> <tex>(j = 1,\ldots n_i)</tex>, которые должны быть выполнены последовательно и, при этом, если <tex>O_{ij} </tex> операция была совершена на машине <tex>A (B)</tex>, то операция <tex>O_{i,j-1}</tex> должна быть совершена на машине <tex>B (A)</tex>. Задача заключается в том, что для данного каждой <tex>i</tex>-той работе дедлайна <tex>d_i \geqslant 0</tex> необходимо найти достижимое расписание с наименьшими максимальным временем опоздания: <tex>\max\{C_i - d_i \mid i = 1, \ldots, n\}</tex>.

Из условия следует, что <tex>i</tex>-тая работа может характеризоваться двумя значениями: количество числом операций <tex>n_i</tex> и машиной, на которой была совершена первая операция. Пусть <tex>r = \overset{n}{\underset{i=1}{\sum}}N_in_i</tex> {{---}} общее количество операций.

Допустим, самым ранним моментом, когда операция может начать выполняться, будет момент времени <tex>0</tex>, а верхнюю границу момента начала выполнения последней операции обозначим за <tex>t_{max}</tex>. К примеру, мы можем выбрать <tex>t_{max} = r</tex>. Тогда расписание можно представить как два списка <tex>A(t)</tex> и <tex>B(t)</tex> <tex>(t = 0,\ldots,t_{max})</tex>, где <tex>A(t) = O_{ij}</tex>, если операция <tex>O_{ij}</tex> должна выполниться на машине <tex>A</tex> в момент времени <tex>t</tex> и <tex>A(t) =</tex> <tex> \varnothing</tex>, если машина <tex>A</tex> простаивает в этот момент. И для каждой операции <tex>O_{ij}</tex>, выполняющейся на машине <tex>A</tex> существует <tex>t</tex>, для которого <tex>A(t) = O_{ij}</tex>. Аналогично для <tex>B_i</tex>. Расписание достижимо тогда и только тогда, когда из <tex>A(t) (B(t)) = O_{ij} , 1 < j \leqslant n_i</tex> следует <tex>O_{i,j-1} = B(s) (A(s))</tex> для некоторого <tex>s < t</tex>, и первая операция для каждой работы запланирована на нужной машине. Перестановку всех Обозначим некоторую перестановку операций будем называть спискомза <tex>L</tex>. Для данного списка <tex>L</tex> осуществимое расписание может быть создано следующим способом: планируем выполнять операции в порядке, соответствующем <tex>L</tex>, причем каждую операцию стараемся выполнить как можно раньше. Подобное расписание будем называть соответствующим <tex>L</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>O_{ij}</tex>, при котором работа будет завершена не позднее дедлайна, при условии, что остальные операции выполняются без задержек вслед за ней,

Этот алгоритм может быть реализован с асимптотикой <tex>O(r \log r)</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>\forall</tex> <tex>i = 1,\ldots,n</tex>: <tex>C_i \geqslant 1</tex> для всех и <tex>\exists</tex> <tex>i = 1,\ldots,n</tex> и : <tex>d_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>L</tex>, выполним следующие шаги:*на первом шаге каждую операцию кладём в соответствующий [[список]] (на самом деле это должна быть [[Двоичная куча|куча]] (англ. ''heap'') для хорошей асимптотики) <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> порядку, где операции из одного списка могут выполнятся в произвольном порядке.

*<tex>\mathtt{LAST([i)]}</tex> {{---}} время окончания последней запланированной операции <tex>i</tex>-той работы;

<font color=darkgreen>// Шаг 1</font> <font color=darkgreen>//Инициализируем L и Z</font>

LAST([i) ] = 0

<font color=darkgreen>// Шаг 2</font> <font color=darkgreen>//Планируем операции соответственно возрастающему по номеру списка порядку</font>

<font color=darkgreen>//Планируем операции, соответствующие работам с <tex color>d_i \geqslant r</tex></font>

'''if''' T1 < LAST([i) ] t = LAST([i)] A(t) = <tex>O_{ij}</tex> <font color=darkgreen>// </font><tex> (*)</tex>

'''if''' T2 < LAST([i)] t = LAST([i)] B(t) = <tex>O_{ij}</tex> <font color=darkgreen>//</font> <tex> (**)</tex>

LAST([i) ] = t + 1 

Количество шагов Суммарное количество операций равно <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>(*) </tex> и <tex>(**) </tex> пусты <tex>A(t) </tex> и <tex>B(t) </tex> соответственно. Иначе две разные операции будут выполняться в один момент времени на одной машине. Для того, чтобы показать достижимость докажем лемму.

<tex>(***)</tex>

Для доказательства <tex>(***) </tex> заметим, что (***) верно, если <tex> A(t) </tex> является первой операцией для работы, так как если <tex> l(A(t)) < l(A(v)) </tex> при некоторых <tex>v = 0. . . , t - 1</tex>,

[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]