J2pij1Lmax

Задача:

Дано работ и две машины, обозначенные как и . -тая работа состоит из операций , которые должны быть выполнены последовательно и, при этом, если операция была совершена на машине , то операция должна быть совершена на машине . Задача заключается в том, что для данного каждой -той работе дедлайна необходимо найти достижимое расписание с наименьшими максимальным временем опоздания: .

Описание задачи

Судя по условию, [math]i[/math]-тая работа может характеризоваться двумя значениями: количество операций [math]n_i[/math] и машиной, на которой была совершена первая операция. Пусть — общее количество операций.

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

или [math]B(t)[/math] — операция [math]i[/math]-той работы.

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

Описание алгоритма

Для решения задачи применим следующий алгоритм:

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

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

Предположим, что [math]d_i \geqslant 0[/math] для [math]i = 1,\ldots,n[/math] и хотя бы для одной работы [math]i[/math] [math]d_i = 0[/math]. Иначе, вычтем из всех [math]d_i[/math] минимальное значение по [math]d_i[/math].

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

Каждую операцию кладём в соответствующий список (на самом деле это должна быть куча (англ. heap) для хорошей асимптотики) [math]L(k)[/math], где . На втором шаге планируем операции соответственно возрастающему по номеру списка [math]k[/math] порядку, где операции из одного списка могут выполнятся в произвольном порядке.

Алгоритм

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

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

function solve():
  //Инициализируем L и Z
  for k = -r + 1 to r - 1
    [math]L(k)[/math] = [math]\emptyset[/math]
  Z = [math]\emptyset[/math]
  for i = 1 to n
    if [math]d_i[/math] < r
      for j = 1 to [math]n_i[/math]
        добавить [math]O_{ij}[/math] в [math]L(d_i - n_i + j)[/math]
    else
      добавить работу i в Z
  for i = 1 to n
    LAST(i) = 0
  T1 = 0
  T2 = 0
  //Планируем операции соответственно возрастающему по номеру списка порядку
  for k = -r + 1 to r - 1
    while [math]L(k) \ne \emptyset[/math]
      Выбрать задание [math]O_{ij}[/math] из [math]L(k)[/math]
      [math]L(k)[/math] = [math]L(k)\setminus\{O_{ij}\}[/math]
      schedule([math]O_{ij}[/math]) 
  //Планируем операции, соответствующие работам с [math]d_i \geqslant r[/math]
  while [math]z \ne \emptyset[/math]
    Выбрать работу i из Z
    Z = [math]Z \setminus\{i\}[/math];
    for j = 1 to [math]n_i[/math]
      schedule([math]O_{ij}[/math])

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

Асимптотика

Количество шагов алгоритма ограничено [math]O(r)[/math], так как каждая операция планируется единожды, а всего их [math]O(r)[/math].

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

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

Лемма:

Пусть — расписание, где . Тогда для каждого , где выполняется

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

Докажем по индукции по [math]s[/math], что если [math]B(s) = O_{ij}[/math] и [math]s \gt t[/math], то [math]A(s -1) = O_{i, j - 1}[/math]. Это, очевидно, верно при [math]s = t+1[/math] так как если [math]B(t+1) = O_{ij}[/math] и [math]A(t)[/math] не соответствует работе [math]i[/math], то [math]B(t) = \emptyset[/math] означает что операция [math]O_{ij}[/math] должна быть запланирована в расписании ранее.

Предположим теперь что лемма верна для всех при и . Выберем максимальное , такое что и . По предположению индукции, и соответствуют одной и той же работе для . Пусть ) не соответствует работе . Тогда для каждого операция не соответствует работе . Таким образом, может быть обработан в момент , что противоречит тому, что является расписанием.

Теорема:

Пусть — операция, которую планируют строчкой (*) или (**) и . Тогда

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

Предположим что . Поскольку , из предыдущей леммы следует, что и и являются операциями одной и той же задачи . Так как , то должно быть значение . Это невозможно, т.к. при и , .

Лемма:

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

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

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

.

Если , тогда возьмем минимальное такое, что и являются последовательными операциями одной и той же задачи при . не соответствует задаче , и мы снова имеем .Если , мы закончили. Если , продолжаем таким же образом.

Теорема:

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

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

Пусть [math] l[/math] — максимальное опоздание оптимального расписания. Тогда эквивалентно .

По первой лемме, данный алгоритм применительно к задаче с дедлайнами дает оптимальное расписание для исходной задаче. Кроме того, это расписание совпадает с расписанием, которое мы получим, применив данный алгоритм к исходной задаче.

См. также.

Классификация задач

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

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

J2pij1Lmax

Описание задачи

Описание алгоритма

Алгоритм

Асимптотика

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

См. также.

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

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты