J2pij1Lmax

$J2\mid p_{ij} = 1\mid L_{max}-$

Задача:

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

Описание решения

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

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

$C_i = \max\{t + 1 \mid A(t)\}$ или $B(t)$ — операция $i$-той работы.

Задача заключается в том, что для данного каждой работе $i$ дедлайна $d_i \geqslant 0$ нужно найти достижимое расписание с наименьшим максимальным временем опоздания:

$\max\{C_i - d_i \mid i = 1, \ldots, n\}$

Следующий алгоритм решает эту задачу:

• введём для каждой операции $O_{ij}$ величину $l(O_{ij}) = d_i - n_i + j$,
• создадим список всех операций $L$, упорядоченный в порядке неубывания значений $l(O_{ij})$,
• найдем соответствующее списку $L$ расписание.

Этот алгоритм может быть реализован с асимптотикой $O(r \log r)$.

Мы предполагаем, что $d_i \geqslant 0$ для $i = 1,\ldots,n$ и хотя бы для одной работы $i$ $d_i = 0$. Иначе, вычтем из всех $d_i$ минимальное значение по $d_i$.

Так как $C_i \geqslant 1$ для всех $i = 1,\ldots,n$ и $d_i = 0$ справедливо $L_i = C_i - d_i \geqslant 1$ как минимум для одной работы $i$. К тому же, можно предположить, что $C_i \leqslant r$. Таким образом, работы с $d_i \gt r - 1$, то есть c $L_i = C_i - d_i \lt 1$, можно смело игнорировать. Они не влияют на значение улучшаемой функции $\max(L_i)$, так как для некого $i$ $L_i \geqslant 1$ можно выполнять эти работы в любом порядке после всех остальных. Для оставшихся операций $O_{ij}$ мы имеем:

$-r + 1 \leqslant l(O_{ij}) = d_i - n_i + j \leqslant r - 1$

Каждую операцию мы кладём в соответствующий список (на самом деле это должна быть куча (англ. heap) для хорошей асимптотики) $L(k)$, где $k = l(O_{ij}) = d_i - n_i + j$ $(-r + 1 \leqslant k \leqslant r - 1)$. На втором шаге мы планируем операции соответственно возрастающему по номеру списка $k$ порядку, где операции из одного списка могут выполнятся в произвольном порядке.

Алгоритм

Рассмотрим алгоритм. Пусть:

• $\mathtt{T1}$ и $\mathtt{T2}$ — первый период времени $t \geqslant 0$, когда соответствующие машины $A$ и $B$ бездействуют;
• $\mathtt{LAST(i)}$ — время окончания последней запланированной операции $i$-той работы;
• $\mathtt{Z}$ — множество работ, где $d_i \geqslant r$.

function main():
  for k = -r + 1 to r - 1
    $L(k)$ = $\emptyset$
    Z = $\emptyset$
  for i = 1 to n
    if $d_i$ < r
      for j = 1 to $n_i$
        добавить $O_{ij}$ в $L(d_i - n_i + j)$
    else
      добавить работу i в Z
  for i = 1 to n
    LAST(i) = 0
  T1 = 0
  T2 = 0
  for k = -r + 1 to r - 1
    while $L(k) \ne \emptyset$
      Выбрать задание $O_{ij}$ из $L(k)$
      $L(k)$ = $L(k)\setminus\{O_{ij}\}$
      schedule($O_{ij}$) 
  while $z \ne \emptyset$
    Выбрать работу i из Z
    Z = $Z \setminus\{i\}$;
    for j = 1 to $n_i$
      schedule($O_{ij}$) 	

function schedule($O_{ij}$):
  if $\mu_{ij}$ == A
    if T1 < LAST(i) 
      t = LAST(i)
      A(t) = $O_{ij}$ (*)
    else
      t = T1
      A(t) = $O_{ij}$
      while $A(T_1)$ $\ne \emptyset$
        T1 = T1 + 1
  else
    if T2 < LAST(i)
      t = LAST(i)
      B(t) = $O_{ij}$ (**)
    else
      t = T2
      A(t) = $O_{ij}$
      while $B(T_2) \ne \emptyset$
        T2 = T2 + 1
  LAST(i) = t + 1

Очевидно, что количество шагов алгоритма ограничено $O(r)$.

Доказательство

Для доказательства того, что алгоритм решения задачи корректен, необходимо показать то, что он строит достижимое расписание. Это справедливо тогда и только тогда, когда до исполнения строчек (*) и (**) пусты A(t) и B(t) соответственно. Иначе две разные операции будут выполняться в один момент времени на одной машине. Для того, чтобы показать достижимость докажем лемму.

Лемма:

Пусть $Y = (A(t), B(t))$ — расписание, где $B(t) = \emptyset$ $(A(t) = \emptyset)$. Тогда для каждого $s \gt t$, где $B(s) = O_{ij}$ $(A(s) = O_{ij})$ выполняется $A(s -1) = O_{i, j - 1}$ $(B(s - 1) = O_{i, j -1}))$

Доказательство:

$\triangleright$

Докажем по индукции по $s$, что если $B(s) = O_{ij}$ и $s \gt t$, то $A(s -1) = O_{i, j - 1}$. Это, очевидно, верно при $s = t+1$ так как если $B(t+1) = O_{ij}$ и $A(t)$ не соответствует работе $i$, то $B(t) = \emptyset$ означает что операция $O_{ij}$ должна быть запланирована в расписании ранее. Предположим теперь что лемма верна для всех $v$ при $t \lt v \lt s$ и $B(s) = O_{ij}$ . Выберем максимальное $l$, такое что $t \lt l \lt s$ и $B(l) = \emptyset$. По предположению индукции, $A(v- −1)$ и $B(v)$ соответствуют одной и той же работе для $v = l + 1,\ldots,s —- 1$. Пусть $A(s - 1$) не соответствует работе $i$. Тогда для каждого $v \in\{l, l + 1,\ldots , s - 1\}$ операция $A(v)$ не соответствует работе $i$. Таким образом, $O_{ij}$ может быть обработан в момент $l$, что противоречит тому, что $Y$ является расписанием.

$\triangleleft$

Теорема:

Пусть $O_{ij}$ — операция, которую планируют строчкой (*) или (**) и $t = LAST(i) \gt T1(T2)$. Тогда $A(t) = \emptyset$ $(B(t) = \emptyset)$

Доказательство:

$\triangleright$

Предположим что $A(t) \neq \emptyset$ $(B(t) \neq \emptyset)$. Поскольку $A(T1) = \emptyset$ $(B(T2) = \emptyset )$, из предыдущей леммы следует, что $A(t)$ и $B(t-1)$ $(B(t)$ и $A(t-1))$ являются операциями одной и той же задачи $k$. Так как $LAST (i)= t$, то должно быть значение $k \neq i$. Это невозможно, т.к. при $LAST (i) = t$ и $\mu_{ij} = A(\mu_{ij} = B)$ , $B(t - 1) = O_{i,j-1}$ $(A(t - 1) = O_{i,j-1})$.

$\triangleleft$

Лемма:

Если существует расписание без опозданий, то данный алгоритм построит расписание без опозданий.

Доказательство:

$\triangleright$

Покажем, что если в расписании, построенном данным алгоритмом есть опоздание, то опоздание есть в каждом расписании. Если есть опоздание в $Y = (A(t), B(t))$, то существует операция $A(t)$ или $B(t)$ с $l(A(t)) \lt t + 1$ или $l(B(t)) \lt t + 1$. Например, это неравенство верно для последней операции в конце работы. Выберем минимальное $t$ с этим свойством и предположим, что $l(A(t)) \lt t + 1$. Тогда мы докажем, что $l(A(v)) \leqslant l(A(t))$ $for$ $v = 1, . . . , t - 1$ и $l(A(0)) \leqslant l(A(t))$ $if$ $A(0) \neq \emptyset$. (***) Таким образом, в каждом расписании должно существовать, по крайней мере, одно опоздание, т.к. если $A(0)\neq \emptyset$ то $l(A(v)) \lt t + 1$ при $v = 0, . . . , t$ и мы должны запланировать $t + 1$ операций во временном интервале $[0, t]$, что невозможно. Если же $A(0) = \emptyset$, то все задачи начинаются на машине $B$ и $t$ операций должны обрабатываться в интервале времени $[1, t]$, что тоже не возможно. Для доказательства (***) заметим, что (***) верно, если $A(t)$ является первой операцией для работы, так как если $l(A(t)) \lt l(A(v))$ при некоторых $v = 0. . . , t - 1$, то алгоритм должен запланировать $A(t)$ перед $A(v)$. Теперь положим $A(t) = O_{ij}$ для какого-нибудь $i$ и $j \gt 1$. Получим $O_{ij-1} = B(s)$ при $s \lt t - 1$, так как из $s = t - 1$ следует $l(B(s)) = l(A(t)) - 1 \lt t = s + 1$, а это противоречит минимальности $t$. Из этого следует, что $l(A(v)) \lt l(A(t))$ при $v = s + 1,\ldots,t - 1$ так как в противном случае $A(t)$ должно быть запланировано ранее. Также $l(A(s)) \lt l(A(s + 1))$ поскольку в противном случае $A (s + 1)$ должно быть запланировано на время $s$, так как $A (s + 1)$ и $B(s)$ являются операциями различных задач. Для $s = 0$ мы доказали (***). Иначе пусть $A(s) = O_{i’,j’,}$. Если $A (s)$ — первая операция задачи, мы закончили. В противном случае, если $O_{i’,’j-1} = B(r)$ при $r \lt s - 1$, мы снова имеем $l(A(v)) \leqslant l(A(s)), v = r, . . . , s - 1$. Если $O_{i',j'-1} = B(s - 1)$, тогда возьмем минимальное $r \leqslant s - 1$ такое, что $B(v)$ и $A(v+1)$ являются последовательными операциями одной и той же задачи при $v = r, \ldots,s - 1$. $A(s + 1)$ не соответствует задаче $i$, и мы снова имеем $l(A(v)) \lt l(A(s + 1)), v = r,\ldots,s$.Если $r = 0$, мы закончили. Если $r \gt 0$, продолжаем таким же образом.

$\triangleleft$

Теорема:

Расписание, построенное данным алгоритмом, оптимально.

Доказательство:

$\triangleright$

Пусть $l$ — максимальное опоздание оптимального расписания. Тогда $\max\limits_{i=1..n}L(i) = \max\limits_{i=1..n}(C_i - d_i) \leqslant l$ эквивалентно $\max\limits_{i=1..n}(C_i - (d_i+l)) \leqslant 0$. По первой лемме, данный алгоритм применительно к задаче с дедлайнами $d_i + l$ дает оптимальное расписание для исходной задаче. Кроме того, это расписание совпадает с расписанием, которое мы получим, применив данный алгоритм к исходной задаче.

$\triangleleft$

См. также.

• Классификация задач
• $J2 \mid n_{i} \leqslant 2 \mid C_{max}$

Источники информации

• Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 180 — 186 стр. — ISBN 978-3-540-69515-8