Редактирование: J2pij1Lmax

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
<tex dpi = "200">J2\mid p_{ij} = 1\mid L_{max}</tex>
+
{{в разработке}}
{{Задача
+
==Условие задачи==
|definition=
+
В нотации Грэхема задача носит название <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>
Дано <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>n</tex> работ <tex>i = 1,\ldots,n</tex> и две машины, обозначенные как <tex>A</tex> и <tex>B</tex>.  
Необходимо отметить, что рассматриваемая задача более узкая, чем следует из ее названия по нотации Грэхема: машины в последовательности операций должны чередоваться.
 
==Описание задачи==
 
Из условия следует, что <tex>i</tex>-тая работа может характеризоваться двумя значениями: числом операций <tex>n_i</tex> и машиной, на которой была совершена первая операция. Пусть <tex>r = \overset{n}{\underset{i=1}{\sum}}n_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>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>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>i</tex>-той работе дедлайна <tex>d_i \ge 0</tex> необходимо найти достижимое расписание с наименьшими максимальным временем опоздания:
  
Задача заключается в том, что для данного каждой работе <tex>i</tex> дедлайна <tex>d_i \geqslant 0</tex> нужно найти достижимое расписание с наименьшим максимальным временем опоздания:
+
<tex>max\{C_i - d_i | i = 1, \ldots, n\}</tex>
  
<tex>L_{\max} = \max\limits_{i=1..n}\{C_i - d_i\}</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,\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> \emptyset</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 \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>O_{ij}</tex> величину <tex>l(O_{ij}) = d_i - n_i + j</tex> {{---}} максимальное время завершения <tex>O_{ij}</tex>, при котором работа будет завершена не позднее дедлайна, при условии, что остальные операции выполняются без задержек вслед за ней,
+
<tex>C_i = max\{t + 1 | A(t)\}</tex> или <tex>B(t)</tex> {{---}} операция <tex>i</tex>-той работы}
* создадим список всех операций <tex>L</tex>, упорядоченный в порядке неубывания значений <tex>l(O_{ij})</tex>,
 
* найдем соответствующее списку <tex>L</tex> расписание.
 
  
Этот алгоритм может быть реализован с асимптотикой <tex>O(r)</tex>.
+
Задача заключается в том, что для данного каждой работе <tex>i</tex> дедлайна <tex>d_i \ge 0</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>max\{C_i - d_i | i = 1, \ldots, n\}</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>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>L</tex>, выполним следующие шаги:
+
Этот алгоритм может быть реализованным с асимптотикой <tex>O(r \log r)</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>d_i \ge 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 \ge 1</tex> для всех <tex>i = 1,\ldots,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>
 +
 
 +
Каждую операцию мы кладём в соответствующий список (на самом деле это должен быть heap для хорошей асимптотики) <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>  
*<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''' solve():
+
  '''main()'''
  <font color=darkgreen>// Шаг 1</font>
+
   '''for''' k: -r + 1 '''to''' r - 1
  <font color=darkgreen>// Инициализируем L и Z</font>
+
     <tex>L(k)</tex> = <tex>\emptyset</tex>;
   '''for''' k = -r + 1 '''to''' r - 1
+
    Z = <tex>\emptyset</tex>;
     <tex>L(k)</tex> = <tex>\emptyset</tex>
+
   '''for''' i: 1 '''to''' n
  Z = <tex>\emptyset</tex>
 
   '''for''' i = 1 '''to''' n
 
 
     '''if''' <tex>d_i</tex> < r
 
     '''if''' <tex>d_i</tex> < r
       '''for''' j = 1 '''to''' <tex>n_i</tex>
+
       '''for''' j: 1 '''to''' n_i
 
         добавить <tex>O_{ij}</tex> в <tex>L(d_i - n_i + j)</tex>
 
         добавить <tex>O_{ij}</tex> в <tex>L(d_i - n_i + j)</tex>
 
     '''else'''
 
     '''else'''
 
       добавить работу 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>
+
   '''for''' k: -r + 1 '''to''' r - 1
  <font color=darkgreen>// Планируем операции соответственно возрастающему по номеру списка порядку</font>
 
   '''for''' k = -r + 1 '''to''' r - 1
 
 
     '''while''' <tex>L(k) \ne \emptyset</tex>
 
     '''while''' <tex>L(k) \ne \emptyset</tex>
 
       Выбрать задание <tex>O_{ij}</tex> из <tex>L(k)</tex>
 
       Выбрать задание <tex>O_{ij}</tex> из <tex>L(k)</tex>
       <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
 
     Z = <tex>Z \setminus\{i\}</tex>;
 
     Z = <tex>Z \setminus\{i\}</tex>;
     '''for''' j = 1 '''to''' <tex>n_i</tex>
+
     '''for''' j: 1 '''to''' <tex>n_i</tex>
 
       schedule(<tex>O_{ij}</tex>)
 
       schedule(<tex>O_{ij}</tex>)
  
  '''function''' schedule(<tex>O_{ij}</tex>):
+
  '''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> <font color=darkgreen>// </font><tex>(*)</tex>
+
       A(t) = <tex>O_{ij}</tex>
 
     '''else'''
 
     '''else'''
       t = T1
+
       t = T1;
       A(t) = <tex>O_{ij}</tex>
+
       A(t) = <tex>O_{ij}</tex>;
 
       '''while''' <tex>A(T_1)</tex> <tex>\ne \emptyset</tex>
 
       '''while''' <tex>A(T_1)</tex> <tex>\ne \emptyset</tex>
         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> <font color=darkgreen>//</font> <tex>(**)</tex>
+
       B(t) = <tex>O_{ij}</tex>
 
     '''else'''
 
     '''else'''
       t = T2
+
       t = T2;
       A(t) = <tex>O_{ij}</tex>
+
       A(t) = <tex>O_{ij}</tex>;
 
       '''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>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> соответственно. Иначе две разные операции будут выполняться в один момент времени на одной машине. Для того, чтобы показать достижимость докажем лемму.
 
 
 
{{Лемма
 
|id=lemma6.12
 
|statement=Пусть <tex>Y = (A(t), B(t))</tex> — расписание, где <tex>B(t) = \emptyset</tex> <tex>(A(t) = \emptyset)</tex>. Тогда для каждого <tex>s > t</tex>, где <tex>B(s) = O_{ij}</tex> <tex>(A(s) = O_{ij})</tex> выполняется <tex>A(s -1) = O_{i, j - 1}</tex> <tex>(B(s - 1) = O_{i, j -1}))</tex>
 
|proof= Докажем по индукции  по  <tex>s</tex>, что если <tex>B(s) = O_{ij}</tex> и <tex>s > t</tex>, то <tex>A(s -1) = O_{i, j - 1}</tex>. Это, очевидно, верно при <tex>s = t+1</tex> так как если <tex>B(t+1) = O_{ij}</tex> и <tex>A(t)</tex> не соответствует работе <tex>i</tex>, то <tex>B(t) = \emptyset</tex> означает что операция <tex>O_{ij}</tex>  должна быть запланирована в расписании ранее.
 
 
 
Предположим теперь что лемма верна для всех <tex>v</tex> при <tex>t < v < s</tex> и <tex>B(s) = O_{ij}</tex> . Выберем максимальное <tex>l</tex>, такое что <tex>t < l < s</tex> и <tex>B(l) = \emptyset</tex>. По предположению индукции, <tex>A(v- −1)</tex> и <tex>B(v)</tex> соответствуют одной и той же работе для <tex>v = l + 1,\ldots,s —- 1</tex>. Пусть <tex>A(s - 1</tex>) не соответствует работе <tex>i</tex>. Тогда для каждого <tex> v \in\{l, l + 1,\ldots , s - 1\}</tex> операция <tex>A(v)</tex> не соответствует работе <tex>i</tex>. Таким образом, <tex>O_{ij}</tex> может быть обработан в момент <tex>l</tex>, что противоречит тому, что <tex>Y</tex> является расписанием.
 
 
 
}}
 
 
 
{{Теорема
 
|id=theorem6.13.
 
|statement=Пусть <tex>O_{ij}</tex> — операция, которую планируют строчкой (*) или (**) и <tex>t = LAST(i) > T1(T2)</tex>. Тогда <tex>A(t) = \emptyset</tex> <tex>(B(t) = \emptyset)</tex>
 
|proof=Предположим что <tex> A(t) \neq \emptyset</tex>  <tex> (B(t) \neq \emptyset)</tex>. Поскольку <tex> A(T1) = \emptyset</tex>  <tex> (B(T2) = \emptyset )</tex>, из предыдущей леммы следует, что <tex> A(t) </tex> и <tex> B(t-1) </tex>  <tex> (B(t) </tex> и <tex>  A(t-1)) </tex> являются операциями одной и той же задачи <tex> k</tex>. Так как <tex> LAST (i)= t</tex>, то должно быть значение <tex> k \neq i</tex>. Это невозможно, т.к. при <tex> LAST (i) = t</tex> и <tex> \mu_{ij} = A(\mu_{ij} = B) </tex> , <tex> B(t - 1) = O_{i,j-1}</tex> <tex>(A(t - 1) = O_{i,j-1})</tex>.
 
}}
 
 
 
{{Лемма
 
|id=lemma6.14
 
|statement=Если существует расписание без опозданий, то данный алгоритм построит расписание без опозданий.
 
|proof=Покажем, что если в расписании, построенном данным алгоритмом есть опоздание, то опоздание есть в каждом расписании.
 
Если есть опоздание в <tex> Y = (A(t), B(t)) </tex>, то существует операция <tex> A(t) </tex> или <tex> B(t) </tex> с <tex> l(A(t)) < t + 1</tex> или <tex> l(B(t)) < t + 1</tex>. Например, это неравенство верно для последней операции в конце работы. Выберем минимальное <tex> t</tex> с этим свойством и предположим, что <tex> l(A(t)) < 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>(***)</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>(***)</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) = O_{ij}</tex> для какого-нибудь <tex>  i</tex> и <tex> j > 1</tex>.
 
Получим <tex> O_{ij-1} = B(s) </tex> при <tex> s < t - 1</tex>,
 
так как  из <tex> s = t - 1</tex> следует <tex> l(B(s)) = l(A(t)) - 1 < t = s + 1</tex>, а это противоречит минимальности <tex> t</tex>. Из этого следует, что <tex> l(A(v)) < l(A(t)) </tex> при <tex> v = s + 1,\ldots,t - 1</tex>
 
так как в противном случае <tex> A(t) </tex> должно быть запланировано ранее. Также <tex> l(A(s)) < l(A(s + 1)) </tex> поскольку в противном случае <tex> A (s + 1) </tex> должно быть запланировано на время <tex> s</tex>, так как <tex> A (s + 1) </tex> и <tex> B(s) </tex> являются операциями различных задач. Для <tex> s = 0</tex>  мы доказали (***). Иначе пусть <tex> A(s) = O_{i’,j’,} </tex>. Если <tex> A (s) </tex> — первая операция задачи, мы закончили. В противном случае, если
 
<tex> O_{i’,’j-1} = B(r) </tex> при <tex> r < s - 1</tex>,
 
мы снова имеем
 
 
 
<tex> l(A(v)) \leqslant l(A(s)), v = r, . . . , s - 1</tex>.
 
 
 
Если <tex>  O_{i',j'-1} = B(s - 1) </tex>, тогда возьмем минимальное <tex> r \leqslant s - 1</tex> такое, что <tex> B(v) </tex> и <tex>A(v+1) </tex> являются последовательными операциями одной и той же задачи при <tex> v = r, \ldots,s - 1</tex>.  <tex> A(s + 1) </tex> не соответствует задаче <tex> i</tex>, и мы снова имеем <tex> l(A(v)) < l(A(s + 1)), v = r,\ldots,s</tex>.Если <tex> r = 0</tex>, мы закончили. Если <tex> r > 0</tex>, продолжаем таким же образом.
 
}}
 
 
 
{{Теорема
 
|id=theorem6.15.
 
|statement=Расписание, построенное данным алгоритмом, оптимально.
 
|proof=Пусть <tex> l</tex> —  максимальное опоздание оптимального расписания. Тогда
 
<tex>\max\limits_{i=1..n}L(i) = \max\limits_{i=1..n}(C_i - d_i) \leqslant l</tex> эквивалентно
 
<tex>\max\limits_{i=1..n}(C_i - (d_i+l))  \leqslant 0</tex>.
 
  
По первой лемме, данный алгоритм применительно к задаче с дедлайнами <tex> d_i + l</tex> дает оптимальное расписание для исходной задаче. Кроме того, это расписание совпадает с расписанием, которое мы получим, применив данный алгоритм к исходной задаче.
+
Очевидно, что количество шагов алгоритма ограничено <tex>O(r)</tex>
}}
 
  
==См. также.==
 
* [[Классификация задач]]
 
* [[J2ni2Cmax|<tex>J2 \mid n_{i} \leqslant 2 \mid C_{max}</tex>]]
 
  
==Источники информации==
+
==Источники==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 180 {{---}} 186 стр. {{---}} ISBN 978-3-540-69515-8
+
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 180 стр. {{---}} ISBN 978-3-540-69515-8
  
[[Категория: Алгоритмы и структуры данных]]
+
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)