81
правка
Изменения
Нет описания правки
{{в разработке}}
Дано <tex>n </tex> работ <tex>i = 1,...,n </tex> и две машины, обозначенные как A и B. <tex>i</tex>-тая работа состоит из <tex>n_i </tex> операций <tex>O_{ij} (j = 1,..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>n_i </tex> и машина, на которой была совершена первая операция. Пусть <tex>r = \Sum(i=1..n) N_i </tex> {{---}} общее количество операций.
Допустим, самым ранним моментом, когда операция может начать выполняться, будет момент времени 0, а верхняя граница момента начала выполнения последней операции обозначим за <tex>t_{max}</tex>. К примеру, мы можем выбрать <tex>t_{max} = r</tex>. Тогда расписание можно представить как два массива <tex>A(t) </tex> и <tex>B(t) (t = 0,...,t_{max})</tex>, где <tex>A(t) = O_ijO_{ij}</tex>, если операция <tex>O_ij </tex> должна выполниться на машине <tex>A </tex> в момент времени <tex>t </tex> и <tex>A(t) = </tex><tex> (пусто)</tex>, если машина <tex>A </tex> простаивает в этот момент. Будем называть <tex>(пусто) </tex> пустой операцией. И для каждой операции O_ij<tex>O_{ij}</tex>, выполняющейся на машине <tex>A </tex> существует <tex>t</tex>, для которого <tex>A(t) = O_ijO_{ij}</tex>. Аналогично для <tex>B_i</tex>. Расписание достижимо тогда и только тогда, когда из <tex>A(t) (B(t)) = O_{ij} , 1 < j \le 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>С_i </tex> {{---}} время окончания работы <tex>i </tex> в достижимом расписании <tex>y = (A(t), B(t)) </tex> можно рассчитать как:
<tex>C_i = max{t + 1 | A(t) </tex> или <tex>B(t) </tex> {{---}} операция <tex>i</tex>-той работы}
Задача заключается в том, что для данного каждой работе <tex>i </tex> дедлайна <tex>d_i \ge 0 </tex> мы хотим найти достижимое расписание с наименьшими максимальным временем опоздания:
<tex>max{C_i - d_i | i = 1, ..., n} </tex>
Следующий алгоритм решает эту задачу:
* Введём для каждой операции <tex>O_{ij}</tex> величину <tex>l(O_{ij}) = d_i - n_i + j</tex>
* Создадим список всех операций <tex>L</tex>, упорядоченный в порядке неубывания значений <tex>l(O_{ij}) </tex> * Найдем соответствующее списку <tex>L </tex> расписание.
Этот алгоритм может быть реализованным с асимптотикой <tex>O(r \log r)</tex>.
Однако, мы будем использовать эвристику с хешами и улучшим асимптотику алгоритма до <tex>O(r)</tex>.
Мы предполагаем, что <tex>d_i \ge 0</tex> для <tex>i = 1,...,n</tex> и хотя бы для одной работы <tex>i</tex> <tex>d_i = 0</tex>. Иначе, вычтем из всех <tex>d_i</tex> минимальное значение по <tex>d_i</tex>
Так как <tex>C_i \ge 1</tex> для всех <tex>i = 1,...,n</tex> и <tex>d_i = 0</tex> справедливо <tex>L_i = C_i - d_i \ge 1</tex> как минимум для одной работы <tex>i</tex>. К тому же, можно предположить, что <tex>C_i \le 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 L_i \ge 1</tex> Можно выполнять эти работы в любом порядке после всех остальных. Для оставшихся операций <tex>O_{ij}</tex> мы имеем:
<tex>-r + 1 \le l(O_{ij}) = d_i - n_i + j \le r - 1</tex>
Каждую операцию мы кладём в соответствующую корзину <tex>L(k)</tex>, где <tex>k = l(O_{ij}) = d_i - n_i + j(-r + 1 \le k \le r - 1)</tex>. На втором шаге мы планируем операции соответственно возрастающему по номеру корзины <tex>k</tex> порядку, где операции из одной корзины могут выполнятся в произвольном порядке.
Давайте детально рассмотрим алгоритм. <tex>T1</tex> и <tex>T2</tex> обозначают первый период времени <tex>t \ge 0</tex>, когда соответсвующие машины <tex>A</tex> и <tex>B</tex> бездействуют. <tex>LAST(i)</tex> обозначает время окончания последней запланированной операции <tex>i</tex>-той работы. <tex>Z</tex> {{---}} множество работ, где <tex>d_i \ge r</tex>
main()
for k:= -r + 1 to r - 1 do
L(k) := (empty);
Z := (empty);
for i:= 1 to n do
if d_i < r then
for j := 1 to n_i do
добавить O_{ij} в L(d_i - n_i + j)
else
добавить работу i в Z
for i := 1 to n do
LAST(i) := 0;
T1 := 0;
T2 := 0;
for k := -r + 1 to r - 1 do
while L(k) \ne (empty) do
Выбрать задание O_{ij} из L(k)
L(k) := L(k)\{O_{ij}};
schedule(O_{ij})
while z \ne (empty) do
Выбрать работу i из Z
Z := Z\{i};
for j := 1 to n_i
schedule(O_{ij})
schedule(O_{ij})
if \mu_{ij} = A then do
if T1 < LAST(i) then do
t := LAST(i)
A(t) := O_{ij}
else
t := T1;
A(t) := O_{ij};
while A(T_1) \ne (empty) do
T1 := T1 + 1;
else
if T2 < LAST(i) then do
t := LAST(i)
B(t) := O_{ij}
else
t := T2;
A(t) := O_{ij};
while B(T_2) \ne (empty) do
T2 := T2 + 1;
LAST(i) := t + 1
Очевидно, что количество шагов алгоритма ограничено <tex>O(r)</tex>
