J2pij1Lmax — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание решения)
м (rollbackEdits.php mass rollback)
 
(не показаны 52 промежуточные версии 3 участников)
Строка 1: Строка 1:
<tex dpi = "200">J2\mid p_{ij} = 1\mid L_{max}-</tex>
+
<tex dpi = "200">J2\mid p_{ij} = 1\mid L_{max}</tex>
 
{{Задача
 
{{Задача
 
|definition=
 
|definition=
Дано <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> операция была совершена на машине<br>
+
Дано <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>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 = \sum_{i=1}^n N_i</tex> {{---}} общее количество операций.
+
==Описание задачи==
 +
Из условия следует, что <tex>i</tex>-тая работа может характеризоваться двумя значениями: числом операций <tex>n_i</tex> и машиной, на которой была совершена первая операция. Пусть <tex>r = \overset{n}{\underset{i=1}{\sum}}n_i</tex> {{---}} общее количество операций.
  
Допустим, самым ранним моментом, когда операция может начать выполняться, будет момент времени 0, а верхнюю границу момента начала выполнения последней операции обозначим за <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>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>C_i</tex> {{---}} время окончания работы <tex>i</tex> в достижимом расписании <tex>y = (A(t), B(t))</tex> можно рассчитать как:
 
<tex>C_i</tex> {{---}} время окончания работы <tex>i</tex> в достижимом расписании <tex>y = (A(t), B(t))</tex> можно рассчитать как:
  
 
<tex>C_i = \max\{t + 1 \mid A(t)\}</tex> или <tex>B(t)</tex> {{---}} операция <tex>i</tex>-той работы.
 
<tex>C_i = \max\{t + 1 \mid A(t)\}</tex> или <tex>B(t)</tex> {{---}} операция <tex>i</tex>-той работы.
  
Задача заключается в том, что для данного каждой работе <tex>i</tex> дедлайна <tex>d_i \geqslant 0</tex> мы хотим найти достижимое расписание с наименьшим максимальным временем опоздания:
+
Задача заключается в том, что для данного каждой работе <tex>i</tex> дедлайна <tex>d_i \geqslant 0</tex> нужно найти достижимое расписание с наименьшим максимальным временем опоздания:
  
<tex>\max\{C_i - d_i \mid i = 1, \ldots, n\}</tex>  
+
<tex>L_{\max} = \max\limits_{i=1..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>l(O_{ij}) = d_i - n_i + j</tex> {{---}} максимальное время завершения <tex>O_{ij}</tex>, при котором работа будет завершена не позднее дедлайна, при условии, что остальные операции выполняются без задержек вслед за ней,
 
* создадим список всех операций <tex>L</tex>, упорядоченный в порядке неубывания значений <tex>l(O_{ij})</tex>,  
 
* создадим список всех операций <tex>L</tex>, упорядоченный в порядке неубывания значений <tex>l(O_{ij})</tex>,  
 
* найдем соответствующее списку <tex>L</tex> расписание.
 
* найдем соответствующее списку <tex>L</tex> расписание.
  
Этот алгоритм может быть реализован с асимптотикой <tex>O(r \log r)</tex>.
+
Этот алгоритм может быть реализован с асимптотикой <tex>O(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>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>C_i \geqslant 1</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>\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>-r + 1 \leqslant l(O_{ij}) = d_i - n_i + j \leqslant r - 1</tex>
 
<tex>-r + 1 \leqslant l(O_{ij}) = d_i - n_i + j \leqslant r - 1</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>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> порядку, где операции из одного списка могут выполнятся в произвольном порядке.
  
 
==Алгоритм==
 
==Алгоритм==
Рассмотрим алгоритм. <tex>T1</tex> и <tex>T2</tex> обозначают первый период времени <tex>t \geqslant 0</tex>, когда соответствующие машины <tex>A</tex> и <tex>B</tex> бездействуют. <tex>LAST(i)</tex> обозначает время окончания последней запланированной операции <tex>i</tex>-той работы. <tex>Z</tex> {{---}} множество работ, где <tex>d_i \geqslant r</tex>.  
+
Рассмотрим алгоритм. Пусть:
 +
*<tex>\mathtt{T1}</tex> и <tex>\mathtt{T2}</tex> {{---}} первый период времени <tex>t \geqslant 0</tex>, когда соответствующие машины <tex>A</tex> и <tex>B</tex> бездействуют;
 +
*<tex>\mathtt{LAST[i]}</tex> {{---}} время окончания последней запланированной операции <tex>i</tex>-той работы;
 +
*<tex>\mathtt{Z}</tex> {{---}} множество работ, где <tex>d_i \geqslant r</tex>.  
  
  '''function''' main():
+
  '''function''' solve():
 +
  <font color=darkgreen>// Шаг 1</font>
 +
  <font color=darkgreen>// Инициализируем L и Z</font>
 
   '''for''' k = -r + 1 '''to''' r - 1
 
   '''for''' k = -r + 1 '''to''' r - 1
 
     <tex>L(k)</tex> = <tex>\emptyset</tex>
 
     <tex>L(k)</tex> = <tex>\emptyset</tex>
    Z = <tex>\emptyset</tex>
+
  Z = <tex>\emptyset</tex>
 
   '''for''' i = 1 '''to''' n
 
   '''for''' i = 1 '''to''' n
 
     '''if''' <tex>d_i</tex> < r
 
     '''if''' <tex>d_i</tex> < r
Строка 49: Строка 56:
 
       добавить работу i в Z
 
       добавить работу i в Z
 
   '''for''' i = 1 '''to''' n
 
   '''for''' i = 1 '''to''' n
     LAST(i) = 0
+
     LAST[i] = 0
 
   T1 = 0
 
   T1 = 0
 
   T2 = 0
 
   T2 = 0
 +
  <font color=darkgreen>// Шаг 2</font>
 +
  <font color=darkgreen>// Планируем операции соответственно возрастающему по номеру списка порядку</font>
 
   '''for''' k = -r + 1 '''to''' r - 1
 
   '''for''' k = -r + 1 '''to''' r - 1
 
     '''while''' <tex>L(k) \ne \emptyset</tex>
 
     '''while''' <tex>L(k) \ne \emptyset</tex>
Строка 57: Строка 66:
 
       <tex>L(k)</tex> = <tex>L(k)\setminus\{O_{ij}\}</tex>
 
       <tex>L(k)</tex> = <tex>L(k)\setminus\{O_{ij}\}</tex>
 
       schedule(<tex>O_{ij}</tex>)  
 
       schedule(<tex>O_{ij}</tex>)  
 +
  <font color=darkgreen>// Планируем операции, соответствующие работам с <tex color>d_i \geqslant r</tex></font>
 
   '''while''' <tex>z \ne \emptyset</tex>
 
   '''while''' <tex>z \ne \emptyset</tex>
 
     Выбрать работу i из Z
 
     Выбрать работу i из Z
Строка 64: Строка 74:
  
 
  '''function''' schedule(<tex>O_{ij}</tex>):
 
  '''function''' schedule(<tex>O_{ij}</tex>):
 +
  t = 0
 
   '''if''' <tex>\mu_{ij}</tex> == A
 
   '''if''' <tex>\mu_{ij}</tex> == A
     '''if''' T1 < LAST(i)
+
     '''if''' T1 < LAST[i]
       t = LAST(i)
+
       t = LAST[i]
       A(t) = <tex>O_{ij}</tex> (*)
+
       A(t) = <tex>O_{ij}</tex> <font color=darkgreen>// </font><tex>(*)</tex>
 
     '''else'''
 
     '''else'''
 
       t = T1
 
       t = T1
Строка 74: Строка 85:
 
         T1 = T1 + 1
 
         T1 = T1 + 1
 
   '''else'''
 
   '''else'''
     '''if''' T2 < LAST(i)
+
     '''if''' T2 < LAST[i]
       t = LAST(i)
+
       t = LAST[i]
       B(t) = <tex>O_{ij}</tex> (**)
+
       B(t) = <tex>O_{ij}</tex> <font color=darkgreen>//</font> <tex>(**)</tex>
 
     '''else'''
 
     '''else'''
 
       t = T2
 
       t = T2
Строка 82: Строка 93:
 
       '''while''' <tex>B(T_2) \ne \emptyset</tex>
 
       '''while''' <tex>B(T_2) \ne \emptyset</tex>
 
         T2 = T2 + 1
 
         T2 = T2 + 1
   LAST(i) = t + 1
+
   LAST[i] = t + 1
  
Очевидно, что количество шагов алгоритма ограничено <tex>O(r)</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>.
  
 
==Доказательство==
 
==Доказательство==
  
Для доказательства того, что алгоритм решения задачи корректен, необходимо показать то, что он строит достижимое расписание. Это справедливо тогда и только тогда, когда до исполнения строчек (*) и (**) пусты A(t) и B(t) соответственно. Иначе две разные операции будут выполняться в один момент времени на одной машине. Для того, чтобы показать достижимость докажем лемму.  
+
Для доказательства того, что алгоритм решения задачи корректен, необходимо показать то, что он строит достижимое расписание. Это справедливо тогда и только тогда, когда до исполнения строчек <tex>(*)</tex> и <tex>(**)</tex> пусты <tex>A(t)</tex> и <tex>B(t)</tex> соответственно. Иначе две разные операции будут выполняться в один момент времени на одной машине. Для того, чтобы показать достижимость докажем лемму.  
  
 
{{Лемма
 
{{Лемма
Строка 113: Строка 125:
 
<tex> l(A(v)) \leqslant l(A(t)) </tex> <tex> for</tex> <tex> v = 1, . . . , t - 1</tex> и  
 
<tex> l(A(v)) \leqslant l(A(t)) </tex> <tex> for</tex> <tex> v = 1, . . . , t - 1</tex> и  
 
<tex> l(A(0)) \leqslant l(A(t)) </tex> <tex> if </tex> <tex> A(0) \neq \emptyset</tex>.
 
<tex> l(A(0)) \leqslant l(A(t)) </tex> <tex> if </tex> <tex> A(0) \neq \emptyset</tex>.
(***)
+
<tex>(***)</tex>
 
Таким образом, в каждом расписании должно существовать, по крайней мере, одно опоздание, т.к. если <tex> A(0)\neq \emptyset</tex> то <tex> l(A(v)) < t + 1</tex> при <tex> v = 0, . . . , t</tex> и мы должны запланировать <tex> t + 1 </tex> операций во временном интервале <tex> [0, t] </tex>, что невозможно. Если же <tex> A(0) = \emptyset </tex>, то все задачи  начинаются на машине <tex> B </tex> и <tex> t</tex> операций должны обрабатываться в интервале времени <tex> [1, t] </tex>, что тоже не возможно.
 
Таким образом, в каждом расписании должно существовать, по крайней мере, одно опоздание, т.к. если <tex> A(0)\neq \emptyset</tex> то <tex> l(A(v)) < t + 1</tex> при <tex> v = 0, . . . , t</tex> и мы должны запланировать <tex> t + 1 </tex> операций во временном интервале <tex> [0, t] </tex>, что невозможно. Если же <tex> A(0) = \emptyset </tex>, то все задачи  начинаются на машине <tex> B </tex> и <tex> t</tex> операций должны обрабатываться в интервале времени <tex> [1, t] </tex>, что тоже не возможно.
Для доказательства (***) заметим, что (***) верно, если <tex> A(t) </tex> является первой операцией для работы, так как если <tex> l(A(t)) < l(A(v)) </tex> при некоторых <tex>v = 0. . . , t - 1</tex>,
+
Для доказательства <tex>(***)</tex> заметим, что (***) верно, если <tex> A(t) </tex> является первой операцией для работы, так как если <tex> l(A(t)) < l(A(v)) </tex> при некоторых <tex>v = 0. . . , t - 1</tex>,
 
то алгоритм должен запланировать <tex> A(t) </tex> перед <tex> A(v) </tex>.
 
то алгоритм должен запланировать <tex> A(t) </tex> перед <tex> A(v) </tex>.
 
Теперь положим <tex> A(t) = O_{ij}</tex> для какого-нибудь <tex>  i</tex> и <tex> j > 1</tex>.
 
Теперь положим <tex> A(t) = O_{ij}</tex> для какого-нибудь <tex>  i</tex> и <tex> j > 1</tex>.
Строка 133: Строка 145:
 
|statement=Расписание, построенное данным алгоритмом, оптимально.
 
|statement=Расписание, построенное данным алгоритмом, оптимально.
 
|proof=Пусть <tex> l</tex> —  максимальное опоздание оптимального расписания. Тогда  
 
|proof=Пусть <tex> l</tex> —  максимальное опоздание оптимального расписания. Тогда  
<tex>max_{i=1}^{n}L(i) = max_{i=1}^{n}(C_i - d_i) \leqslant l</tex> эквивалентно
+
<tex>\max\limits_{i=1..n}L(i) = \max\limits_{i=1..n}(C_i - d_i) \leqslant l</tex> эквивалентно
<tex>max_{i=1}^{n}(C_i - (d_i+l))  \leqslant 0</tex>.
+
<tex>\max\limits_{i=1..n}(C_i - (d_i+l))  \leqslant 0</tex>.
  
 
По первой лемме, данный алгоритм применительно к задаче с дедлайнами <tex> d_i + l</tex> дает оптимальное расписание для исходной задаче. Кроме того, это расписание совпадает с расписанием, которое мы получим, применив данный алгоритм к исходной задаче.
 
По первой лемме, данный алгоритм применительно к задаче с дедлайнами <tex> d_i + l</tex> дает оптимальное расписание для исходной задаче. Кроме того, это расписание совпадает с расписанием, которое мы получим, применив данный алгоритм к исходной задаче.
Строка 144: Строка 156:
  
 
==Источники информации==
 
==Источники информации==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 180 стр. {{---}} ISBN 978-3-540-69515-8
+
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 180 {{---}} 186 стр. {{---}} ISBN 978-3-540-69515-8
  
[[Категория: Дискретная математика и алгоритмы]]
+
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Текущая версия на 19:05, 4 сентября 2022

[math]J2\mid p_{ij} = 1\mid L_{max}[/math]

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

Необходимо отметить, что рассматриваемая задача более узкая, чем следует из ее названия по нотации Грэхема: машины в последовательности операций должны чередоваться.

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

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

Допустим, самым ранним моментом, когда операция может начать выполняться, будет момент времени [math]0[/math], а верхнюю границу момента начала выполнения последней операции обозначим за [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]A(t) (B(t)) = O_{ij} , 1 \lt j \leqslant n_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]L[/math] расписанием.

[math]C_i[/math] — время окончания работы [math]i[/math] в достижимом расписании [math]y = (A(t), B(t))[/math] можно рассчитать как:

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

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

[math]L_{\max} = \max\limits_{i=1..n}\{C_i - d_i\}[/math]

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

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

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

Этот алгоритм может быть реализован с асимптотикой [math]O(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]\forall[/math] [math]i = 1,\ldots,n[/math]: [math]C_i \geqslant 1[/math] и [math]\exists[/math] [math]i = 1,\ldots,n[/math]: [math]d_i = 0[/math]. Поэтому [math]L_i = C_i - d_i \geqslant 1[/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] мы имеем:

[math]-r + 1 \leqslant l(O_{ij}) = d_i - n_i + j \leqslant r - 1[/math]

Для того, чтобы найти расписание, соответствующее списку всех операций [math]L[/math], выполним следующие шаги:

  • на первом шаге каждую операцию кладём в соответствующий список [math]L(k)[/math], где [math]k = l(O_{ij}) = d_i - n_i + j[/math] [math](-r + 1 \leqslant k \leqslant r - 1)[/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():
  // Шаг 1
  // Инициализируем 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
  // Шаг 2
  // Планируем операции соответственно возрастающему по номеру списка порядку
  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] // [math](*)[/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] // [math](**)[/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]r[/math]. Первый шаг алгоритма занимает [math]O(r)[/math], так как каждая операция добавляется либо в [math]L[/math], либо в [math]Z[/math]. На втором шаге каждая операция назначается единожды, то есть на втором шаге также выполняется [math]O(r)[/math] действий. И, наконец, суммарное время всех вызовов функции [math]\mathrm{schedule}[/math] также равно [math]O(r)[/math], так как суммарное количество итераций циклов внутри этой функции не превышает [math]O(r)[/math]. Итого, время работы алгоритма [math]O(r)[/math].

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

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

Лемма:
Пусть [math]Y = (A(t), B(t))[/math] — расписание, где [math]B(t) = \emptyset[/math] [math](A(t) = \emptyset)[/math]. Тогда для каждого [math]s \gt t[/math], где [math]B(s) = O_{ij}[/math] [math](A(s) = O_{ij})[/math] выполняется [math]A(s -1) = O_{i, j - 1}[/math] [math](B(s - 1) = O_{i, j -1}))[/math]
Доказательство:
[math]\triangleright[/math]

Докажем по индукции по [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]v[/math] при [math]t \lt v \lt s[/math] и [math]B(s) = O_{ij}[/math] . Выберем максимальное [math]l[/math], такое что [math]t \lt l \lt s[/math] и [math]B(l) = \emptyset[/math]. По предположению индукции, [math]A(v- −1)[/math] и [math]B(v)[/math] соответствуют одной и той же работе для [math]v = l + 1,\ldots,s —- 1[/math]. Пусть [math]A(s - 1[/math]) не соответствует работе [math]i[/math]. Тогда для каждого [math] v \in\{l, l + 1,\ldots , s - 1\}[/math] операция [math]A(v)[/math] не соответствует работе [math]i[/math]. Таким образом, [math]O_{ij}[/math] может быть обработан в момент [math]l[/math], что противоречит тому, что [math]Y[/math] является расписанием.
[math]\triangleleft[/math]
Теорема:
Пусть [math]O_{ij}[/math] — операция, которую планируют строчкой (*) или (**) и [math]t = LAST(i) \gt T1(T2)[/math]. Тогда [math]A(t) = \emptyset[/math] [math](B(t) = \emptyset)[/math]
Доказательство:
[math]\triangleright[/math]
Предположим что [math] A(t) \neq \emptyset[/math] [math] (B(t) \neq \emptyset)[/math]. Поскольку [math] A(T1) = \emptyset[/math] [math] (B(T2) = \emptyset )[/math], из предыдущей леммы следует, что [math] A(t) [/math] и [math] B(t-1) [/math] [math] (B(t) [/math] и [math] A(t-1)) [/math] являются операциями одной и той же задачи [math] k[/math]. Так как [math] LAST (i)= t[/math], то должно быть значение [math] k \neq i[/math]. Это невозможно, т.к. при [math] LAST (i) = t[/math] и [math] \mu_{ij} = A(\mu_{ij} = B) [/math] , [math] B(t - 1) = O_{i,j-1}[/math] [math](A(t - 1) = O_{i,j-1})[/math].
[math]\triangleleft[/math]
Лемма:
Если существует расписание без опозданий, то данный алгоритм построит расписание без опозданий.
Доказательство:
[math]\triangleright[/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] l(A(v)) \leqslant l(A(t)) [/math] [math] for[/math] [math] v = 1, . . . , t - 1[/math] и [math] l(A(0)) \leqslant l(A(t)) [/math] [math] if [/math] [math] A(0) \neq \emptyset[/math]. [math](***)[/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](***)[/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] l(B(s)) = l(A(t)) - 1 \lt t = s + 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(A(v)) \leqslant l(A(s)), v = r, . . . , s - 1[/math].

Если [math] O_{i',j'-1} = B(s - 1) [/math], тогда возьмем минимальное [math] r \leqslant s - 1[/math] такое, что [math] B(v) [/math] и [math]A(v+1) [/math] являются последовательными операциями одной и той же задачи при [math] v = r, \ldots,s - 1[/math]. [math] A(s + 1) [/math] не соответствует задаче [math] i[/math], и мы снова имеем [math] l(A(v)) \lt l(A(s + 1)), v = r,\ldots,s[/math].Если [math] r = 0[/math], мы закончили. Если [math] r \gt 0[/math], продолжаем таким же образом.
[math]\triangleleft[/math]
Теорема:
Расписание, построенное данным алгоритмом, оптимально.
Доказательство:
[math]\triangleright[/math]

Пусть [math] l[/math] — максимальное опоздание оптимального расписания. Тогда [math]\max\limits_{i=1..n}L(i) = \max\limits_{i=1..n}(C_i - d_i) \leqslant l[/math] эквивалентно [math]\max\limits_{i=1..n}(C_i - (d_i+l)) \leqslant 0[/math].

По первой лемме, данный алгоритм применительно к задаче с дедлайнами [math] d_i + l[/math] дает оптимальное расписание для исходной задаче. Кроме того, это расписание совпадает с расписанием, которое мы получим, применив данный алгоритм к исходной задаче.
[math]\triangleleft[/math]

См. также.

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

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