1632
правки
Изменения
м
==Задача 1==<tex dpi = "200"> 1 \mid p_i = 1\mid \sum C_i</tex> '''Описание алгоритма''' Входные данные для этой задачи: число работ <tex>n</tex> Этот случай простейший. Для верного выполнения просто выставим работы по порядку, тогда ответом Ответом будет <tex>n</tex>, так как мы <tex>n</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_limits_{i k = 1}^n(w_i)k</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы (которое в нашем случае единица) домноженное на вес этой работы. ==Задача 3==<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex>{{Задача|definition=Дано Воспользовавшись формулой суммы первых <tex>n</tex> работ и один станок. Для каждой работы известно её время появления членов арифметической прогрессии алгоритм <tex>r_S_n=\dfrac{ia_1+a_n}2 \cdot n</tex>. Время выполнения всех работ <tex>p_i</tex> равно будет работает за <tex>O(1)</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum f_{i}</tex> было минимальнымно если нужно вывести и само расписание, где <tex>f_{i}</tex> {{---}} монотонная функция времени окончания время работы будет <tex>C_{i}</tex> для работ <tex>i = 1, 2, ..., O(n)</tex>.}} '''Описание алгоритма'''
Нам нужно распределить ===Вариант 2===<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\mid p_i = 1\mid \sum w_i C_i</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы нумеруются так:
'''Псевдокод'''Так как [[Сортировка|сортировка]] весов занимает <tex>O(n \log n)</tex> время, то асимптотика времени работы алгорита равна <tex>O(n + n \log n)</tex>.
<tex>t_1 \leftarrow r_1 </tex> '''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do''' <tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex> ==Задача 4==<tex dpi Основная задача= "200"> 1 \mid r_j,p_j = p \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 = p \mid \sum w_i C_i </tex> '''Описание алгоритма''' Пусть перед началом алгоритма работы пронумерованы в соответствии с свойствами для функций <tex>f_1, f_2, \ldots, f_n</tex> Пояснение для псевдокода: <tex>T</tex> это множество {<tex>r_j + lp \mid j = 1, 2, \ldots, n; l = 0, 1, \ldots, n-1 </tex>} <tex>F_k'(s,e)</tex> это <tex>min(F_{k-1}(s,t_k)+F_{k-1}(t_k + p, e)+f_k(t_k + p) \mid t_k \in T, max(s, r_k) \leqslant t_k \leqslant e-p)</tex> '''Псевдокод''' '''for''' <tex> \forall s, e \in T \ with \ s \leqslant e</tex> '''do''' <tex>F_0(s,e) \leftarrow 0</tex> '''for''' <tex>k \leftarrow 1</tex> '''to''' <tex>n</tex> '''do''' '''for''' <tex> \forall s, e \in T \ with \ s \leqslant e</tex> '''do''' <tex> F_k(s,e) \leftarrow \begin{cases} F_{k-1}(s,e) \ if\ r_k \notin [s - p,e);\\ F_k'(s,e) \ overwise; \end{cases} </tex> '''Вычислить''' <tex>F_n($$ \min_{i=1}^n (r_i) $$, max_{t \in T}(t+p) )</tex>==Описание алгоритма==
==Сложность алгоритма==Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max \limits_{i = 1 \ldots n} r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max \limits_{i = 1 \ldots n} r_{i})\log n)</tex> ====Реализация 2====* <tex>\mathtt{Q}</tex> {{---}} обычная [[Очередь | очередь]], в которой работы изначально располагаются в отсортированном по <tex>r_i</tex> порядке,* <tex>\mathtt{P}</tex> {{---}} [[Приоритетные очереди | приоритетная очередь]] по максимуму. <tex> \mathtt{time} \leftarrow 1</tex> <tex> \mathtt{answer} \leftarrow 0</tex> '''while''' <tex>\mathtt{Q} \neq \varnothing </tex> '''and''' <tex>\mathtt{P} \neq \varnothing </tex> '''if''' <tex>\mathtt{Q} \neq \varnothing </tex> <tex> j \leftarrow \mathtt{Q.head()}</tex> '''if''' <tex>\mathtt{time} < r_j</tex> <tex>\mathtt{time} \leftarrow r_j</tex> '''while''' <tex> \mathtt{time} \geqslant r_j</tex> <tex>\mathtt{P.insert}(w_j)</tex> <tex>\mathtt{Q.pop()}</tex> '''if''' <tex>\mathtt{Q} = \varnothing </tex> '''break''' '''else''' <tex> j \leftarrow \mathtt{Q.head()}</tex> <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot \mathtt{P.extractMax()} </tex> <tex> \mathtt{time}\texttt{++}</tex> Данная реализация имеет идею, аналогичную предыдущей: сначала обрабатывать работу с максимальным весом среди всех доступных.В начале работы сортируются по <tex>r_i</tex>, из очереди <tex>\mathtt{Q}</tex> достаётся каждая работа, причём ровно один раз, аналогично для очереди <tex>\mathtt{P}</tex>, поэтому итоговая асимптотика времени работы алгоритма составляет <tex>O(n \log n)</tex>.
rollbackEdits.php mass rollback
Дано <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> 1 \mid p_i = 1\mid \sum C_i</tex>
Для верного выполнения просто выставим работы по порядку невозрастания весов, тогда ответом будет <tex> r_1 \leqslant r_2 sum\leqslant \ldots \leqslant r_nlimits_{i = 1}^nw_i C_i</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы (которое в нашем случае <tex>C_{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=
}}
===Псевдокод=== ====Реализация 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* PЛазарев А. BruckerА. Scheduling Algorithms (2006), 5th editionМусатова Е.Г., стрКварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний. 101 - 102
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
