3622
правки
Изменения
→Более простые варианты исходной задачи: выпилено неправильное решение
}}
=Простая задача =Более простые варианты исходной задачи==
Перед решением основной задачи рассмотрим более простые.
==Задача <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>{{Задача|definition=Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum f_{i}</tex> было минимальным, где <tex>f_{i}C_i</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, ..., n</tex>.}}
Так как [[Сортировка|сортировка]] весов занимает <tex>w_1/p_1 O(n \geqslant w_2/p_2 \geqslant \ldots w_n/p_nlog n)</tex> ==Псевдокод задачи время, то асимптотика времени работы алгорита равна <tex>1 \mid \mid \sum w_i C_i</tex>== <tex> C_0 \leftarrow 0</tex> '''for''' <tex> i O(n + n \leftarrow 1</tex> '''to''' <tex>log 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> '''for''' <tex> i \leftarrow 1</tex> '''to''' <tex>n</tex> '''do''' <tex>C_i \leftarrow C_{i-1} + p_i</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=
}}
===Псевдокод основной задачи=== ====Реализация 1==== <tex> S \leftarrow \{1 \dots ldots n\}</tex>
<tex> \mathtt{time} \leftarrow 0</tex>
<tex> \mathtt{answer} \leftarrow 0</tex>
'''while''' <tex> S \neq \varnothing </tex>
<tex> j \leftarrow null </tex>
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leq leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant \max w_\limits_{ij \in S, j = 1 \ldots n} w_j</tex>
<tex> j \leftarrow i </tex>
'''if''' <tex>j \neq null </tex>
<tex> \mathtt{time++}</tex>
==См. также==
* [[Классификация задач]]
* [[1outtreesumwc|<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* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]