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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 9: Строка 9:
 
Перед решением основной задачи рассмотрим более простые.
 
Перед решением основной задачи рассмотрим более простые.
  
==Задача 1==
+
==Задача <tex>1 \mid r_i,p_i = 1 \mid \sum f_i</tex>==
 
<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex>
 
<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex>
 
{{Задача
 
{{Задача
Строка 16: Строка 16:
 
}}
 
}}
  
==Описание алгоритма простой задачи 1==
+
==Описание алгоритма задачи <tex>1 \mid r_i,p_i = 1 \mid \sum f_i</tex>==
 
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Так как нужно рассмотреть <tex>n</tex> временных промежутков, задача может быть решена за <tex>O(n^3)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы нумеруются так:
 
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Так как нужно рассмотреть <tex>n</tex> временных промежутков, задача может быть решена за <tex>O(n^3)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы нумеруются так:
  
 
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex>  
 
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex>  
==Псевдокод простой задачи 1==
+
==Псевдокод задачи <tex>1 \mid r_i,p_i = 1 \mid \sum f_i</tex>==
 
   <tex>t_1 \leftarrow r_1 </tex>
 
   <tex>t_1 \leftarrow r_1 </tex>
 
   '''for'''  <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''
 
   '''for'''  <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''
Строка 27: Строка 27:
 
==Задача 2==
 
==Задача 2==
 
<tex dpi = "200"> 1 \mid \mid \sum w_i C_i</tex>
 
<tex dpi = "200"> 1 \mid \mid \sum w_i C_i</tex>
==Описание алгоритма простой задачи 2==
+
==Описание алгоритма задачи <tex>1 \mid \mid \sum w_i C_i</tex>==
 
Входные данные для этой задачи: число работ <tex>n</tex> и два вектора <tex>p_i</tex>, <tex>w_i</tex> размера <tex>n</tex>.
 
Входные данные для этой задачи: число работ <tex>n</tex> и два вектора <tex>p_i</tex>, <tex>w_i</tex> размера <tex>n</tex>.
 
Пусть в алгоритме задания перечислены так:
 
Пусть в алгоритме задания перечислены так:
  
 
<tex>w_1/p_1 \geqslant w_2/p_2 \geqslant \ldots w_n/p_n</tex>  
 
<tex>w_1/p_1 \geqslant w_2/p_2 \geqslant \ldots w_n/p_n</tex>  
==Псевдокод простой задачи 2==
+
==Псевдокод задачи <tex>1 \mid \mid \sum w_i C_i</tex>==
 +
  <tex> C_0 \leftarrow 0</tex>
 +
  '''for'''  <tex> i \leftarrow 1</tex> '''to''' <tex>n</tex> '''do'''
 +
      <tex>C_i \leftarrow C_{i-1} + p_i</tex>
 +
 
 +
==Задача 3==
 +
<tex dpi = "200"> 1 \mid r_j,p_j = 1 \mid \sum f_j</tex>
 +
 
 +
Вес всех работ <tex>w_i \geqslant 0</tex>
 +
Для всех функций <tex>f_1, f_2, \ldots, f_n</tex> выполняются следующие свойства:
 +
<tex>f_j</tex> неубывающая функция для  <tex>j = 1, 2, \ldots, n</tex>
 +
<tex>f_i - f_j</tex> неубывающая функция для  <tex>i, j = 1, 2, \ldots, n</tex> при <tex>i < j </tex>
 +
 
 +
<tex>\sum w_i C_i</tex> являются функцией <tex>f_j(C_j)</tex>, так что по факту решаем задачу <tex>1 \mid r_j,p_j = 1 \mid \sum w_i C_i </tex>
 +
==Описание алгоритма задачи <tex>1 \mid r_j,p_j = 1 \mid \sum f_j</tex>==
 +
Входные данные для этой задачи: число работ <tex>n</tex> и два вектора <tex>p_i</tex>, <tex>w_i</tex> размера <tex>n</tex>.
 +
Пусть в алгоритме задания перечислены так:
 +
 
 +
<tex>w_1/p_1 \geqslant w_2/p_2 \geqslant \ldots w_n/p_n</tex>
 +
==Псевдокод задачи <tex>1 \mid r_j,p_j = 1 \mid \sum f_j</tex>==
 
   <tex> C_0 \leftarrow 0</tex>
 
   <tex> C_0 \leftarrow 0</tex>
 
   '''for'''  <tex> i \leftarrow 1</tex> '''to''' <tex>n</tex> '''do'''
 
   '''for'''  <tex> i \leftarrow 1</tex> '''to''' <tex>n</tex> '''do'''

Версия 20:25, 2 июня 2015

[math] 1 \mid r_i,p_i = 1 \mid \sum w_i C_i[/math]


Задача:
Дано [math]n[/math] работ и один станок. Для каждой работы известно её время появления [math]r_{i}[/math] и вес [math]w_{i}[/math]. Время выполнения всех работ [math]p_i[/math] равно [math]1[/math]. Требуется выполнить все работы, чтобы значение [math]\sum w_{i} C_{i}[/math] было минимальным, где [math]C_{i}[/math] — время окончания работы.


Простая задача

Перед решением основной задачи рассмотрим более простые.

Задача [math]1 \mid r_i,p_i = 1 \mid \sum f_i[/math]

[math] 1 \mid r_i,p_i = 1 \mid \sum f_i[/math]

Задача:
Дано [math]n[/math] работ и один станок. Для каждой работы известно её время появления [math]r_{i}[/math]. Время выполнения всех работ [math]p_i[/math] равно [math]1[/math]. Требуется выполнить все работы, чтобы значение [math]\sum f_{i}[/math] было минимальным, где [math]f_{i}[/math] — монотонная функция времени окончания работы [math]C_{i}[/math] для работ [math]i = 1, 2, ..., n[/math].


Описание алгоритма задачи [math]1 \mid r_i,p_i = 1 \mid \sum f_i[/math]

Нам нужно распределить [math]n[/math] работ в разное время. Если мы назначим время [math]t[/math] для работы [math]i[/math] то цена будет [math]f_i(t + 1)[/math]. Так как нужно рассмотреть [math]n[/math] временных промежутков, задача может быть решена за [math]O(n^3)[/math]. Функция [math]f_i[/math] монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. [math]n[/math] временных интервалов [math]t_i[/math] для [math]n[/math] работ могут быть получены с помощью следующего алгоритма, где предполагается что работы нумеруются так:

[math] r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n[/math]

Псевдокод задачи [math]1 \mid r_i,p_i = 1 \mid \sum f_i[/math]

  [math]t_1 \leftarrow r_1 [/math]
  for  [math] i \leftarrow 2[/math] to [math]n[/math] do
     [math] t_i \leftarrow [/math] max[math](r_i, \ t_{i-1} - 1)[/math]

Задача 2

[math] 1 \mid \mid \sum w_i C_i[/math]

Описание алгоритма задачи [math]1 \mid \mid \sum w_i C_i[/math]

Входные данные для этой задачи: число работ [math]n[/math] и два вектора [math]p_i[/math], [math]w_i[/math] размера [math]n[/math]. Пусть в алгоритме задания перечислены так:

[math]w_1/p_1 \geqslant w_2/p_2 \geqslant \ldots w_n/p_n[/math]

Псевдокод задачи [math]1 \mid \mid \sum w_i C_i[/math]

  [math] C_0 \leftarrow 0[/math]
  for  [math] i \leftarrow 1[/math] to [math]n[/math] do
     [math]C_i \leftarrow C_{i-1} + p_i[/math]

Задача 3

[math] 1 \mid r_j,p_j = 1 \mid \sum f_j[/math]

Вес всех работ [math]w_i \geqslant 0[/math] Для всех функций [math]f_1, f_2, \ldots, f_n[/math] выполняются следующие свойства: [math]f_j[/math] неубывающая функция для [math]j = 1, 2, \ldots, n[/math] [math]f_i - f_j[/math] неубывающая функция для [math]i, j = 1, 2, \ldots, n[/math] при [math]i \lt j [/math]

[math]\sum w_i C_i[/math] являются функцией [math]f_j(C_j)[/math], так что по факту решаем задачу [math]1 \mid r_j,p_j = 1 \mid \sum w_i C_i [/math]

Описание алгоритма задачи [math]1 \mid r_j,p_j = 1 \mid \sum f_j[/math]

Входные данные для этой задачи: число работ [math]n[/math] и два вектора [math]p_i[/math], [math]w_i[/math] размера [math]n[/math]. Пусть в алгоритме задания перечислены так:

[math]w_1/p_1 \geqslant w_2/p_2 \geqslant \ldots w_n/p_n[/math]

Псевдокод задачи [math]1 \mid r_j,p_j = 1 \mid \sum f_j[/math]

  [math] C_0 \leftarrow 0[/math]
  for  [math] i \leftarrow 1[/math] to [math]n[/math] do
     [math]C_i \leftarrow C_{i-1} + p_i[/math]

Основная задача

Описание алгоритма основной задачи

Пусть [math]time[/math] — текущий момент времени.
Для каждого очередного значения [math]time[/math], которое изменяется от [math]0[/math] до времени окончания последней работы, будем:

  1. Выбирать работу [math]j[/math] из множества невыполненных работ, у которой [math]r_{i} \le time[/math], а значение [math]w_{i}[/math] максимально.
  2. Если мы смогли найти работу [math]j[/math], то выполняем её в момент времени [math]time[/math] и удаляем из множества невыполненных работ.
  3. Увеличиваем [math]time[/math] на один.

Доказательство корректности алгоритма основной задачи

Теорема:
Расписание, построенное данным алгоритмом, является корректным и оптимальным.
Доказательство:
[math]\triangleright[/math]

Доказательство будем вести от противного.
Рассмотрим расписание [math]S_{1}[/math], полученное после выполнения нашего алгоритма, и оптимальное расписание [math]S_{2}[/math].
Возьмём первый момент времени [math]t_{1}[/math], когда расписания различаются. Пусть в этот момент времени в [math]S_{1}[/math], будет выполняться работа с весом [math]w_{1}[/math], а в [math]S_{2}[/math] — работа с весом [math]w_{2}[/math].
Это первый момент, в котором расписания отличаются, значит в [math]S_{2}[/math] работа с весом [math]w_{1}[/math] выполнится в момент времени [math]t_{2} \gt t_{1}[/math].
Поменяем местами работы с весами [math]w_{1}[/math] и [math]w_{2}[/math] в [math]S_{2}[/math] и полуим расписание [math]S_{3}[/math]. Это возможно, потому что время появления этих работ не меньше [math]t_{1}[/math].
При такой перестановке ответы на задачу для [math]S_{2}[/math] и [math]S_{3}[/math] будут отличаться на

    [math]t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})[/math]

Первая скобка отрицательная: [math]t_{1} \lt t_{2}[/math]. Вторая скобка тоже отрицательная из того, что в [math]S_{1}[/math] работа с весом [math]w_1[/math] выполняется раньше, значит её вес должен быть больше [math]w_2[/math].

Итого имеем, что ответ для [math]S_{2}[/math] больше, чем ответ для [math]S_{3}[/math]. Следовательно расписание [math]S_2[/math] неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание [math]S_{1}[/math] отличается от оптимального. Следовательно мы доказали, что оно оптимальное.
[math]\triangleleft[/math]

Псевдокод основной задачи

  [math] S \leftarrow \{1 \dots n\}[/math]
  [math] \mathtt{time} \leftarrow 0[/math]
  [math] \mathtt{answer} \leftarrow 0[/math]
  while [math] S \neq \varnothing [/math]
     [math] j \leftarrow null [/math]
     if [math] i \in S[/math] and [math] r_{i} \leq \mathtt{time}[/math] and [math]\max w_{i} [/math]
        [math] j \leftarrow i [/math]
     if [math]j \neq null [/math]
        [math] S \leftarrow S \setminus j[/math]
        [math] \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}[/math]
     [math] \mathtt{time++}[/math]

Сложность алгоритма

Множество [math]S[/math] станет пустым не позже, чем через [math]n + \max r_{i}[/math] шагов цикла. Определить максимум в множестве можно за время [math]O(\log n)[/math], используя , например, очередь с приоритетами. Значит общее время работы алгоритма [math]O((n + \max r_{i})\log n)[/math]


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

  • P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20
  • P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84 - 85