Изменения
Нет описания правки
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.
}}
==Простые задачи==
Перед решением основной задачи рассмотрим более простые.
===Задача 1===
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum C_i</tex>
===Задача 2===
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum w_i C_i</tex>
Входные данные для этой задачи: число работ <tex>n</tex> и вес каждой работы <tex>w_i</tex>
Для верного выполнения просто выставим работы по порядку убывания невозрастанию весов, тогда ответом будет <tex> \sum_{i = 1}^n(w_i C_i)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы (которое в нашем случае единица<tex>C_{i-1}+1</tex>) домноженное на вес этой работы.Если вес работ отсортировали за <tex>O(n \log n)</tex> то алгоритм работает за <tex>O(n + n \log n)</tex>
===Задача 3===
<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex>
'''Описание алгоритма'''
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex>
==Основная задача== ===Описание алгоритма===
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/>
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:
<ol>
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le leqslant time</tex>, а значение <tex>w_{i}</tex> максимально.</li>
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li>
<li> Увеличиваем <tex>time</tex> на один.</li>
</ol>
===Доказательство корректности алгоритма===
{{Теорема
|statement=
}}
===Псевдокод===
<tex> S \leftarrow \{1 \dots n\}</tex>
<tex> \mathtt{time} \leftarrow 0</tex>
<tex> \mathtt{time++}</tex>
===Сложность алгоритма===Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max_{i = 1}^n r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[Wikipedia:ru:Очередь с приоритетом (программирование)Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max_{i = 1}^n r_{i})\log n)</tex>
==См. также==
* [[Классификация задач]]
* [[1ridipi1|<tex>1 \mid outtree \mid \sum w_i C_i</tex>]]
* [[1ridipi1|<tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>]]
== Источники информации ==
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38 - 39* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84 - 85
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
