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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 32: Строка 32:
  
 
=== Динамика ===
 
=== Динамика ===
Для любых <tex>t_u, t_v \in \Theta, u \leqslant v</tex> и для любого <tex>k \in [1, n]</tex> положим <tex>U_k(t_u, t_v) = \{J_i \mid i < k \wedge t_u <= r_i < t_v\}</tex> <tex>-</tex> множество работ, индекс которых меньше <tex>k</tex> и чьи <tex>r_i</tex> лежать в интервале <tex>[t_u, t_v).</tex> Также определим <tex>W_k(t_u, t_v, m)</tex> как максимальный вес множества работ <tex>Z \subset U_k(t_u, t_v), |Z| = m</tex> такой, что <tex>m \in (1, \dots ,n)</tex> и расписание от <tex>Z</tex> разрешимо и заканчивается до <tex>t_v</tex>. Если такое <tex>Z</tex> существует, будем говорить, что <tex>Z</tex> реализует <tex>W_k(t_u, t_v, m)</tex>. Если же такого <tex>Z</tex> нет, то <tex>W_k(t_u, t_v, m) = - \infty.</tex>
+
{{Определение
 
+
|id = def1
Будем основывать динамику на следующей лемме.
+
|definition = <tex>t_u, t_v \in \Theta, u \leqslant v, k \in [1, n]:</tex>
 +
#<tex>U_k(t_u, t_v) = \{J_i \mid i < k \wedge t_u <= r_i < t_v\}</tex> <tex>-</tex> это множество работ, индекс которых меньше <tex>k</tex> и чьи <tex>r_i</tex> лежать в интервале <tex>[t_u, t_v);</tex>
 +
#<tex>W_k(t_u, t_v, m)</tex> <tex>-</tex> максимальный вес <tex>Z \subset U_k(t_u, t_v), |Z| = m</tex> такой, что <tex>m \in (1, \dots ,n)</tex> и расписание от <tex>Z</tex> разрешимо и заканчивается до <tex>t_v</tex>. Если такое <tex>Z</tex> существует, будем говорить, что <tex>Z</tex> реализует <tex>W_k(t_u, t_v, m)</tex>. Если же такого <tex>Z</tex> нет, то <tex>W_k(t_u, t_v, m) = - \infty.</tex>}}
  
 
{{Лемма
 
{{Лемма
Строка 44: Строка 46:
  
 
|proof=
 
|proof=
Если <tex>r_k \notin [t_u, t_v)</tex>, то работа <tex>J_k</tex> не может быть поставлена ни в какой <tex>Z</tex> такой, что расписание от <tex>Z</tex> разрешимо и <tex>Z \subset U_k(t_u, t_v)</tex>. Тогда, очевидно, что <tex>W_k(t_u, t_v, m) = W_{k-1}(t_u, t_v, m).</tex>
+
Если <tex>r_k \notin [t_u, t_v)</tex>, то работа <tex>J_k</tex> не может быть поставлена ни в какой <tex>Z</tex> такой, что расписание от <tex>Z</tex> разрешимо и <tex>Z \subset U_k(t_u, t_v)</tex>. Тогда, очевидно, что <tex>W_k(t_u, t_v, m) = W_{k-1}(t_u, t_v, m);</tex>
  
  
Строка 53: Строка 55:
 
* <tex> W_{k-1}(t_u, t_v, m) < W'_k</tex>
 
* <tex> W_{k-1}(t_u, t_v, m) < W'_k</tex>
 
*:Пусть существуют такие <tex>t_x, t_y \in \Theta</tex> и три числа <tex>m_1,m_2,m_3</tex>, такие что
 
*:Пусть существуют такие <tex>t_x, t_y \in \Theta</tex> и три числа <tex>m_1,m_2,m_3</tex>, такие что
*:# <tex> \max(r_k, t_u) \leqslant t_x < t_y \leqslant \min(d_k, t_v)</tex>
+
*:# <tex> \max(r_k, t_u) \leqslant t_x < t_y \leqslant \min(d_k, t_v)</tex>,
*:# <tex> m_1 + m_2 + m_3 = m - 1</tex>
+
*:# <tex> m_1 + m_2 + m_3 = m - 1</tex>,
*:# <tex> p \cdot (m_2 + 1) = t_y - t_x</tex>
+
*:# <tex> p \cdot (m_2 + 1) = t_y - t_x.</tex>
 
*: Очевидно, что <tex>U_{k-1}(t_u, t_x), U_{k-1}(t_x, t_y)</tex> и <tex>U_{k-1}(t_y, t_v)</tex> не пересекаются. Следовательно, расписания подмножеств, которые реализуют <tex>W_{k-1}(t_u, t_x, m_1), W_{k-1}(t_x, t_y, m_2)</tex> и <tex>W_{k-1}(t_y, t_v, m_3)</tex>, поставленные друг за другом дадут правильное расписание для <tex>m-1</tex> работ взятых из <tex>U_{k-1}(t_u, t_v)</tex>. Более того, у нас достаточно места чтобы вставить работу <tex>J_k</tex> в промежуток между <tex>t_x</tex> и <tex>t_y</tex>. Это возможно, так как <tex>p \cdot (m_2 + 1) = t_y - t_x</tex> и ровно <tex>m_2</tex> работ распределено для <tex>U_{k-1}(t_x, t_y)</tex>. Таким образом <tex>W'_k \leqslant W_k(t_u, t_v, m)</tex>.
 
*: Очевидно, что <tex>U_{k-1}(t_u, t_x), U_{k-1}(t_x, t_y)</tex> и <tex>U_{k-1}(t_y, t_v)</tex> не пересекаются. Следовательно, расписания подмножеств, которые реализуют <tex>W_{k-1}(t_u, t_x, m_1), W_{k-1}(t_x, t_y, m_2)</tex> и <tex>W_{k-1}(t_y, t_v, m_3)</tex>, поставленные друг за другом дадут правильное расписание для <tex>m-1</tex> работ взятых из <tex>U_{k-1}(t_u, t_v)</tex>. Более того, у нас достаточно места чтобы вставить работу <tex>J_k</tex> в промежуток между <tex>t_x</tex> и <tex>t_y</tex>. Это возможно, так как <tex>p \cdot (m_2 + 1) = t_y - t_x</tex> и ровно <tex>m_2</tex> работ распределено для <tex>U_{k-1}(t_x, t_y)</tex>. Таким образом <tex>W'_k \leqslant W_k(t_u, t_v, m)</tex>.
  
Строка 63: Строка 65:
 
*:Тогда <tex>W_k(t_u, t_v, m) = W_{k-1}(t_u, t_v, m) \leqslant \max(W_{k-1}(t_u, t_v, m), W'_k)</tex>.
 
*:Тогда <tex>W_k(t_u, t_v, m) = W_{k-1}(t_u, t_v, m) \leqslant \max(W_{k-1}(t_u, t_v, m), W'_k)</tex>.
 
* <tex>J_k \in Z</tex>.  
 
* <tex>J_k \in Z</tex>.  
*:Положим <tex>t_x</tex> и <tex>t_y</tex> временем начала выполнения и завершения работы <tex>J_k</tex> в расписании от <tex>Z</tex>. Благодаря предыдущей лемме, мы знаем, что <tex>t_x, t_y \in \Theta</tex>. Также выполняется условие <tex> \max(r_k, t_u) \leqslant t_x < t_y \leqslant \min(d_k, t_v).</tex> Пусть <tex>Z_1, Z_2, Z_3</tex> будут подмножествами <tex>Z/J_k</tex> такими, что все работы в <tex>Z_1, Z_2</tex> и <tex>Z_3</tex> имеют время появления <tex>r_i</tex> в границах <tex>[t_u,t_x)</tex>, <tex>[t_x, t_y)</tex> и <tex>[t_y,t_v)</tex> соответственно. По структуре расписания(работа <tex>J_k</tex> имеет максимальный дедлайн <tex>d_k</tex>) все работы в <tex>Z_1</tex> завершаться до <tex>t_x</tex>. Более того, все работы в <tex>Z_2</tex> начнут выполняться после <tex>t_x</tex> и завершаться до <tex>t_y</tex>, аналогично для <tex>Z_3</tex>. Также <tex>p \cdot (|Z_2| + 1) = t_y - t_x,</tex> так как <tex>J_k</tex> выполнялась в промежутке <tex>[t_x, t_y).</tex> При этом, <tex>|Z_1| + |Z_2| + |Z_3| = m - 1.</tex> Можно заметить, что вес <tex>Z_1</tex> не превосходит <tex>W_{k-1}(t_u, t_x, |Z_1|)</tex>, вес <tex>Z_2</tex> не превосходит <tex> W_{k-2}(t_x, t_y, |Z_2|)</tex> и вес <tex>Z_3</tex> не превосходит <tex> W_{k-1}(t_y, t_v, |Z_3|).</tex> Следовательно, <tex>W_k(t_u, t_v, m) = w_k + \sum\limits_{i = 1}^3weight(Z_i) \leqslant W'_k \leqslant \max(W_{k-1}(t_u, t_v, m), W'_k)</tex>, где <tex>weight(Z)</tex> <tex>-</tex> суммарный вес всех работ множества <tex>Z.</tex>
+
*:Положим <tex>t_x</tex> и <tex>t_y</tex> временем начала выполнения и завершения работы <tex>J_k</tex> в расписании от <tex>Z</tex>. Благодаря предыдущей лемме, мы знаем, что <tex>t_x, t_y \in \Theta</tex>. Также выполняется условие <tex> \max(r_k, t_u) \leqslant t_x < t_y \leqslant \min(d_k, t_v).</tex> Пусть <tex>Z_1, Z_2, Z_3</tex> будут подмножествами <tex>Z/J_k</tex> такими, что все работы в <tex>Z_1, Z_2</tex> и <tex>Z_3</tex> имеют время появления <tex>r_i</tex> в границах <tex>[t_u,t_x)</tex>, <tex>[t_x, t_y)</tex> и <tex>[t_y,t_v)</tex> соответственно. По структуре расписания(работа <tex>J_k</tex> имеет максимальный дедлайн <tex>d_k</tex>) все работы в <tex>Z_1</tex> завершаться до <tex>t_x</tex>. Более того, все работы в <tex>Z_2</tex> начнут выполняться после <tex>t_x</tex> и завершаться до <tex>t_y</tex>, аналогично для <tex>Z_3</tex>. Также <tex>p \cdot (|Z_2| + 1) = t_y - t_x,</tex> так как <tex>J_k</tex> выполнялась в промежутке <tex>[t_x, t_y).</tex> При этом, <tex>|Z_1| + |Z_2| + |Z_3| = m - 1.</tex> Можно заметить, что <tex>weight(Z_1) \leqslant W_{k-1}(t_u, t_x, |Z_1|), weight(Z_2) \leqslant W_{k-2}(t_x, t_y, |Z_2|)</tex> и <tex>weight(Z_3) \leqslant W_{k-1}(t_y, t_v, |Z_3|).</tex> Следовательно, <tex>W_k(t_u, t_v, m) = w_k + \sum\limits_{i = 1}^3weight(Z_i) \leqslant W'_k \leqslant \max(W_{k-1}(t_u, t_v, m), W'_k).</tex>
  
Исходя из двух неравенств доказанных выше, можно получить требуемое равенство <tex>W_k(t_u, t_v, m) = \max(W_{k-1}(t_u, t_v, m), W'_k).</tex>
+
Исходя из двух неравенств доказанных выше, можно получить требуемое равенство <tex>W_k(t_u, t_v, m) = \max(W_{k-1}(t_u, t_v, m), W'_k).</tex> Лемма доказана.
 
}}
 
}}
  
 
=== Псевдокод ===
 
=== Псевдокод ===
     '''int''' solve('''int['''n''']''' d, '''int['''n''']''' r, '''int['''n''']''' w):
+
 
      Отсортировать работы по <tex>d_i</tex>
+
     Отсортировать работы по <tex>d_i</tex>
      <tex>fill(W, -\infty)</tex>
+
    <tex>fill(W, -\infty)</tex>
   
+
   
      '''foreach''' <tex>t_u, t_v \in \Theta \mid t_u \leqslant t_v</tex>
+
    '''foreach''' <tex>t_u, t_v \in \Theta \mid t_u \leqslant t_v</tex>
            '''if''' <tex>p \leqslant (\min(d_1,t_v)-\max(r_1,t_u))</tex>
+
        '''if''' <tex>p \leqslant (\min(d_1,t_v)-\max(r_1,t_u))</tex>
                <tex>W_1(t_u, t_v, 1) = w_1</tex>
+
            <tex>W_1(t_u, t_v, 1) = w_1</tex>
 
      
 
      
      '''for''' <tex>k = 2</tex> '''to''' <tex>n</tex>
+
    '''for''' <tex>k = 2</tex> '''to''' <tex>n</tex>
            '''for''' <tex>m = 1</tex> '''to''' <tex>n</tex>
+
        '''for''' <tex>m = 1</tex> '''to''' <tex>n</tex>
                '''foreach''' <tex>t_u, t_v \in \Theta \mid t_u \leqslant t_v</tex>
+
            '''foreach''' <tex>t_u, t_v \in \Theta \mid t_u \leqslant t_v</tex>
                  '''if''' <tex>r_k \not\in [t_u, t_v)</tex>
+
                '''if''' <tex>r_k \not\in [t_u, t_v)</tex>
                      <tex>W_k (t_u, t_v, m) = W_{k - 1} (t_u, t_v, m)</tex>
+
                  <tex>W_k (t_u, t_v, m) \leftarrow W_{k - 1} (t_u, t_v, m)</tex>
                  '''else'''
+
                '''else'''
                      <tex>W'_k = </tex> Подсчитать <tex>W'_k</tex> по формуле из леммы
+
                  <tex>W'_k \leftarrow </tex> Подсчитать <tex>W'_k</tex> по формуле из леммы
                      <tex>W_k (t_u, t_v, m) = \max(W_{k - 1} (t_u, t_v, m), W'_k)</tex>
+
                  <tex>W_k (t_u, t_v, m) \leftarrow \max(W_{k - 1} (t_u, t_v, m), W'_k\})</tex>
 
      
 
      
      '''return''' <tex>\max\limits_{i \in [1, \dots, n]}(W_n(\min\limits_{t \in \Theta} (t - p), \max\limits_{t \in \Theta} (t), i))</tex>
+
    '''return''' <tex>\max\limits_{i \in [1, \dots, n]}(W_n(\min\limits_{t \in \Theta} (t - p), \max\limits_{t \in \Theta} (t), i))</tex>
  
=== Асимптотика  ===
+
=== Оценка алгоритма ===
 
Заметим, что множество <tex>\Theta</tex> содержит не более <tex>n^2</tex> элементов. Следовательно, цикл по <tex>t_u, t_v</tex> итерируется <tex>O(n^4)</tex> раз. Внутри этого цикла мы тратим <tex>O(n^4)</tex> времени на подсчет <tex>W'_k</tex>, так как зная <tex>t_x, m_1</tex> и <tex>m_2</tex> мы можем посчитать <tex>t_y</tex> и <tex>m_3</tex>. Также алгоритм использует шестимерный массив для хранения <tex>W_k (t_u, t_v, m)</tex>. Таким образом, учитывая итерации алгоритма по <tex>k</tex> и <tex>m</tex>, нам потребуется <tex>O(n^{10})</tex> времени и <tex>O(n^6)</tex> памяти для работы алгоритма.
 
Заметим, что множество <tex>\Theta</tex> содержит не более <tex>n^2</tex> элементов. Следовательно, цикл по <tex>t_u, t_v</tex> итерируется <tex>O(n^4)</tex> раз. Внутри этого цикла мы тратим <tex>O(n^4)</tex> времени на подсчет <tex>W'_k</tex>, так как зная <tex>t_x, m_1</tex> и <tex>m_2</tex> мы можем посчитать <tex>t_y</tex> и <tex>m_3</tex>. Также алгоритм использует шестимерный массив для хранения <tex>W_k (t_u, t_v, m)</tex>. Таким образом, учитывая итерации алгоритма по <tex>k</tex> и <tex>m</tex>, нам потребуется <tex>O(n^{10})</tex> времени и <tex>O(n^6)</tex> памяти для работы алгоритма.
  
 
== См. также ==
 
== См. также ==
* [[1pi1sumwu | <tex> 1 \mid r_i,p_i = 1 \mid \sum w_i U_i</tex>]]
+
 
* [[1ripipsumwu | <tex> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>]]
+
* [[P1sumu]]
 +
* [[1pi1sumwu]]
 +
* [[1ripipsumwu]]
  
 
== Источники информации ==
 
== Источники информации ==
  
*[http://www.lix.polytechnique.fr/~baptiste/jsched98.pdf Philippe Baptiste <tex>-</tex> Polynomial Time Algorithms for Minimizing the Weighted Number of Late Jobs on a Single Machine with Equal Processing Times]
+
Philippe Baptiste - Polynomial Time Algorithms for Minimizing the Weighted Number of Late Jobs on a Single Machine with Equal Processing Times
  
[[Категория: Алгоритмы и структуры данных]]
+
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

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

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

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

Шаблоны, используемые на этой странице: