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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 44: Строка 44:
 
==Сложность алгоритма==
 
==Сложность алгоритма==
 
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex>
 
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex>
 +
 +
 +
== Источники информации ==
 +
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84 - 85
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Версия 14:47, 29 мая 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]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] time \leftarrow 0[/math]
  [math] answer \leftarrow 0[/math]
  while [math] S \neq \varnothing [/math]
     [math] j \leftarrow i : (\max \limits_{i \in S, r_{i} \leq time} w_{i})[/math]
     if [math]j \neq null [/math]
        [math] S \leftarrow S \setminus j[/math]
        [math] Answer \leftarrow Answer + time \cdot w_{j}[/math]
     [math] 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, стр. 84 - 85