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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{в разработке}}
 
{{в разработке}}
Дано <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_{ij}</tex>, если операция <tex>O_ij</tex> должна выполниться на машине <tex>A</tex> в момент времени <tex>t</tex> и <tex>A(t) =</tex><tex> \emptyset</tex>, если машина <tex>A</tex> простаивает в этот момент. Будем называть <tex>\emptyset</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>n</tex> работ <tex>i = 1,\ldots,n</tex> и две машины, обозначенные как A и B. <tex>i</tex>-тая работа состоит из <tex>n_i</tex> операций <tex>O_{ij} (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>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>\emptyset</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>С_i</tex> {{---}} время окончания работы <tex>i</tex> в достижимом расписании <tex>y = (A(t), B(t))</tex> можно рассчитать как:
  
Строка 9: Строка 12:
 
Задача заключается в том, что для данного каждой работе <tex>i</tex> дедлайна <tex>d_i \ge 0</tex> мы хотим найти достижимое расписание с наименьшими максимальным временем опоздания:
 
Задача заключается в том, что для данного каждой работе <tex>i</tex> дедлайна <tex>d_i \ge 0</tex> мы хотим найти достижимое расписание с наименьшими максимальным временем опоздания:
  
<tex>max{C_i - d_i | i = 1, ..., n}</tex>  
+
<tex>max\{C_i - d_i | i = 1, \ldots, n\}</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>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 \log r)</tex>.
 
Однако, мы будем использовать эвристику с хешами и улучшим асимптотику алгоритма до <tex>O(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>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,...,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>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>
 
<tex>-r + 1 \le l(O_{ij}) = d_i - n_i + j \le r - 1</tex>
Строка 28: Строка 31:
 
Каждую операцию мы кладём в соответствующую корзину <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>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>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()
+
  '''main()'''
 
   '''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>;
Строка 47: Строка 51:
 
     '''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)\\\{O_{ij}\}</tex>;
+
       <tex>L(k)</tex> = <tex>L(k)\setminus\{O_{ij}\}</tex>;
 
       schedule(<tex>O_{ij}</tex>)  
 
       schedule(<tex>O_{ij}</tex>)  
 
   '''while''' <tex>z \ne \emptyset</tex>
 
   '''while''' <tex>z \ne \emptyset</tex>
 
     Выбрать работу i из Z
 
     Выбрать работу i из Z
     Z = <tex>Z\\\{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>)
  
 
+
  '''schedule(<tex>O_{ij}</tex>)'''
  schedule(O_{ij})
+
   '''if''' <tex>\mu_{ij}</tex> == A
   if \mu_{ij} = A then do
+
     '''if''' T1 < LAST(i)  
     if T1 < LAST(i) then do
+
       t = LAST(i)
       t := LAST(i)
+
       A(t) = <tex>O_{ij}</tex>
       A(t) := O_{ij}
+
     '''else'''
     else
+
       t = T1;
       t := T1;
+
       A(t) = <tex>O_{ij}</tex>;
       A(t) := O_{ij};
+
       '''while''' <tex>A(T_1)</tex> <tex>\ne \emptyset</tex>
       while A(T_1) \ne \emptyset do
+
         T1 = T1 + 1;
         T1 := T1 + 1;
+
   '''else'''
   else
+
     '''if''' T2 < LAST(i)
     if T2 < LAST(i) then do
+
       t = LAST(i)
       t := LAST(i)
+
       B(t) = <tex>O_{ij}</tex>
       B(t) := O_{ij}
+
     '''else'''
     else
+
       t = T2;
       t := T2;
+
       A(t) = <tex>O_{ij}</tex>;
       A(t) := O_{ij};
+
       '''while''' <tex>B(T_2) \ne \emptyset</tex>
       while B(T_2) \ne \emptyset do
+
         T2 = T2 + 1;
         T2 := T2 + 1;
+
   LAST(i) = t + 1
   LAST(i) := t + 1
 
  
 
Очевидно, что количество шагов алгоритма ограничено <tex>O(r)</tex>
 
Очевидно, что количество шагов алгоритма ограничено <tex>O(r)</tex>

Версия 21:39, 21 июня 2012

Эта статья находится в разработке!

Условие задачи

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

Дано [math]n[/math] работ [math]i = 1,\ldots,n[/math] и две машины, обозначенные как A и B. [math]i[/math]-тая работа состоит из [math]n_i[/math] операций [math]O_{ij} (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]n_i[/math] и машина, на которой была совершена первая операция. Пусть [math]r = \sum_{i=1}^n N_i[/math] — общее количество операций.

Допустим, самым ранним моментом, когда операция может начать выполняться, будет момент времени 0, а верхняя граница момента начала выполнения последней операции обозначим за [math]t_{max}[/math]. К примеру, мы можем выбрать [math]t_{max} = r[/math]. Тогда расписание можно представить как два массива [math]A(t)[/math] и [math]B(t) (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] \emptyset[/math], если машина [math]A[/math] простаивает в этот момент. Будем называть [math]\emptyset[/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 \le 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]С_i[/math] — время окончания работы [math]i[/math] в достижимом расписании [math]y = (A(t), B(t))[/math] можно рассчитать как:

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

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

[math]max\{C_i - d_i | i = 1, \ldots, n\}[/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]O(r)[/math].

Мы предполагаем, что [math]d_i \ge 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 \ge 1[/math] для всех [math]i = 1,\ldots,n[/math] и [math]d_i = 0[/math] справедливо [math]L_i = C_i - d_i \ge 1[/math] как минимум для одной работы [math]i[/math]. К тому же, можно предположить, что [math]C_i \le 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 L_i \ge 1[/math] Можно выполнять эти работы в любом порядке после всех остальных. Для оставшихся операций [math]O_{ij}[/math] мы имеем:

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

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

Алгоритм

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

main()
  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 n_i
        добавить [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]) 
  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]) 	
schedule([math]O_{ij}[/math])
  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]