Викиконспекты - Вклад участника [ru]

RSumCi

2016-06-10T10:38:45Z

Qradimir: /* Описание алгоритма */

<tex dpi="200">R \mid \mid \sum C_i</tex>
{{Задача
|definition=Дано <tex> n </tex> работ и <tex> m </tex> станков, причем для каждого станка длительность выполнения на нем <tex>i</tex>-й работы составляет <tex> p_{ij} </tex>. Необходимо минимизировать сумму времени выполнения работ.
}}
==Алгоритм==

===Описание алгоритма===
Рассмотрим произвольное допустимое расписание для этой задачи. Рассмотрим какой-то станок <tex> j </tex>, пусть на нем выполняется <tex>n_j</tex> работ. Тогда вклад этого станка в целевую функцию (не теряя общности, пронумеруем работы на этом станке от <tex>1 </tex> до <tex>n_j</tex>) рассчитывается как:

<tex>
\sum\limits_{i=1}^{n_j} \left( p_{ij} + \sum\limits_{q=1}^{i-1} p_{qj} \right) =
n_j \cdot p_{1j} + (n_j - 1) \cdot p_{2j} + \dots + 2 p_{(n_j-1)j} + p_{n_jj}
</tex>

Заметим, что в каждом допустимом расписании перед каждой работой окажется коэффициент <tex> k </tex>, означающий, что соответствующая работа выпллняется <tex> k </tex>-й с конца. Понятно, что в различных расписаниях <tex> k </tex> может принимать значения от <tex>1</tex> до <tex>n</tex>.

Сведем задачу к назначению каждой работы <tex> i </tex> позиции с конца <tex> k </tex> на станке <tex> j </tex> с помощью алгоритма [[Поток минимальной стоимости | поиска максимального потока минимальной стоимости]]. Поместим в левую долю графа работы, в правую долю — пары из станка и коэффициента и проведем соответствующие ребра пропускной способности <tex>1</tex> и стоимости <tex>k \cdot p_{ij}</tex>, соответствующие вкладу работы в целевую функцию, если она окажется в позиции <tex> k </tex> с конца на станке <tex> j </tex>. Проведем из стока в левую долю ребра стоимости <tex>0</tex> и пропускной способности <tex>1</tex>, из правой доли в сток — также ребра стоимости <tex> 0 </tex> и пропускной способности <tex>1</tex>. Максимальный поток минимальной стоймости в построенной сети будет ответом на исходную задачу.
{{Утверждение
|statement=Eсли ребро <tex> i \to (j, k) </tex> насыщено потоком, то работа <tex> i </tex> в оптимальном расписании должна стоять на станке <tex> j </tex> в позиции <tex> k </tex> с конца.
|proof=
# Целевя функция текущей задачи совпадает со стомостью максимального потока в построенной сети, так как у ребер между долями пропускная способность 1, а у дополнительных ребер из истока и в сток нулевая стоимость, и они не могут внести вклад в целевую функцию.
# Расписание, построенное по вышепредставленному способу действительно будет допустимым.
## Благодаря ограничениям на поток, входящий в левую долю, каждая работа будет назначена только один раз.
## Благодаря ограничениям на поток, выходящий из правой доли, на каждую позицию будет назначено не более одной работы.
## Докажем, что не возникает ситуации такой, что существует такая позиция <tex> l </tex>, что в этой позиции с конца стоит какая-то работа, а в позиции <tex> l - 1 </tex> с конца — нет (это противоречит определению <tex>l</tex>-й с конца работы). Такая ситуация означает, что ребро <tex> i \to (j, l) </tex> оказалось насышено потоком, а ребро <tex>i \to (j, l - 1) </tex> — не насыщено. Но стоимость ребра <tex> i \to (j, l - 1) </tex> меньше стоимости ребра <tex> i \to (j, l) </tex>, поэтому можем переместить поток с ребра <tex> i \to (j, l) </tex> на ребро <tex> i \to (j, l - 1) </tex>, не нарушив свойства потока и улучшив целевую функцию, что противоречит оптимальности ответа для mincost-maxflow. Следовательно, такой позиции не возникнет и расписание будет допустимым.
}}

===Время выполнения===
Время выполнения алгоритма поиска максимального потока минимальной стоймости равно <tex> \mathcal{O}(V \cdot E^2) </tex>. Количество вершин в получаемой сети равно <tex> \mathcal{O}(m \cdot n) </tex>. Количество ребер в сети равно <tex> \mathcal{O}(m \cdot n^2) </tex>. Следовательно, ассимптотика алгоритма равна <tex> \mathcal{O}(m^3 \cdot n^5) </tex>.

==См. также==
* [[Поток минимальной стоимости]]
* [[Методы решения задач теории расписаний]]
* [[PSumCi|<tex>P \mid \mid \sum C_i</tex>]]
* [[QSumCi|<tex>Q \mid \mid \sum C_i</tex>]]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

RSumCi

2016-06-10T10:36:14Z

Qradimir: /* Описание алгоритма */

<tex dpi="200">R \mid \mid \sum C_i</tex>
{{Задача
|definition=Дано <tex> n </tex> работ и <tex> m </tex> станков, причем для каждого станка длительность выполнения на нем <tex>i</tex>-й работы составляет <tex> p_{ij} </tex>. Необходимо минимизировать сумму времени выполнения работ.
}}
==Алгоритм==

===Описание алгоритма===
Рассмотрим произвольное допустимое расписание для этой задачи. Рассмотрим какую-то станок <tex> j </tex>, пусть на нем выполняется <tex>n_j</tex> работ. Тогда вклад этого станка в целевую функцию (не теряя общности, пронумеруем работы на этом станке от <tex>1 </tex> до <tex>n_j</tex>) рассчитывается как:

<tex>
\sum\limits_{i=1}^{n_j} \left( p_{ij} + \sum\limits_{q=1}^{i-1} p_{qj} \right) =
n_j \cdot p_{1j} + (n_j - 1) \cdot p_{2j} + \dots + 2 p_{(n_j-1)j} + p_{n_jj}
</tex>

Заметим, что в каждом допустимом расписании перед каждой работой окажется коэффициент <tex> k </tex>, означающий, что соответствующая работа выпллняется <tex> k </tex>-й с конца. Понятно, что в различных расписаниях <tex> k </tex> может принимать значения от <tex>1</tex> до <tex>n</tex>.

Сведем задачу к назначению каждой работы <tex> i </tex> позиции с конца <tex> k </tex> на станке <tex> j </tex> с помощью алгоритма [[Поток минимальной стоимости | поиска максимального потока минимальной стоимости]]. Поместим в левую долю графа работы, в правую долю — пары из станка и коэффициента и проведем соответствующие ребра пропускной способности <tex>1</tex> и стоимости <tex>k \cdot p_{ij}</tex>, соответствующие вкладу работы в целевую функцию, если она окажется в позиции <tex> k </tex> с конца на станке <tex> j </tex>. Проведем из стока в левую долю ребра стоимости <tex>0</tex> и пропускной способности <tex>1</tex>, из правой доли в сток — также ребра стоимости <tex> 0 </tex> и пропускной способности <tex>1</tex>. Максимальный поток минимальной стоймости в построенной сети будет ответом на исходную задачу.
{{Утверждение
|statement=Eсли ребро <tex> i \to (j, k) </tex> насыщено потоком, то работа <tex> i </tex> в оптимальном расписании должна стоять на станке <tex> j </tex> в позиции <tex> k </tex> с конца.
|proof=
# Целевя функция текущей задачи совпадает со стомостью максимального потока в построенной сети, так как у ребер между долями пропускная способность 1, а у дополнительных ребер из истока и в сток нулевая стоимость, и они не могут внести вклад в целевую функцию.
# Расписание, построенное по вышепредставленному способу действительно будет допустимым.
## Благодаря ограничениям на поток, входящий в левую долю, каждая работа будет назначена только один раз.
## Благодаря ограничениям на поток, выходящий из правой доли, на каждую позицию будет назначено не более одной работы.
## Докажем, что не возникает ситуации такой, что существует такая позиция <tex> l </tex>, что в этой позиции с конца стоит какая-то работа, а в позиции <tex> l - 1 </tex> с конца — нет (это противоречит определению <tex>l</tex>-й с конца работы). Такая ситуация означает, что ребро <tex> i \to (j, l) </tex> оказалось насышено потоком, а ребро <tex>i \to (j, l - 1) </tex> — не насыщено. Но стоимость ребра <tex> i \to (j, l - 1) </tex> меньше стоимости ребра <tex> i \to (j, l) </tex>, поэтому можем переместить поток с ребра <tex> i \to (j, l) </tex> на ребро <tex> i \to (j, l - 1) </tex>, не нарушив свойства потока и улучшив целевую функцию, что противоречит оптимальности ответа для mincost-maxflow. Следовательно, такой позиции не возникнет и расписание будет допустимым.
}}

===Время выполнения===
Время выполнения алгоритма поиска максимального потока минимальной стоймости равно <tex> \mathcal{O}(V \cdot E^2) </tex>. Количество вершин в получаемой сети равно <tex> \mathcal{O}(m \cdot n) </tex>. Количество ребер в сети равно <tex> \mathcal{O}(m \cdot n^2) </tex>. Следовательно, ассимптотика алгоритма равна <tex> \mathcal{O}(m^3 \cdot n^5) </tex>.

==См. также==
* [[Поток минимальной стоимости]]
* [[Методы решения задач теории расписаний]]
* [[PSumCi|<tex>P \mid \mid \sum C_i</tex>]]
* [[QSumCi|<tex>Q \mid \mid \sum C_i</tex>]]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

Методы решения задач теории расписаний

2016-06-07T15:04:43Z

Qradimir: /* Жадное построение расписания */

== Сведение к другой задаче ==
При сведении текущей задачи теории расписаний <tex> S </tex> к какой-то другой <tex> S' </tex> (не обязательно задаче теории расписаний) необходимо доказать два пункта:
# Допустимость расписания, построенного с помощью задачи <tex> S' </tex>, или существование способа его трансформации в допустимое без нарушения оптимальности.
# Следствие того, что если мы оптимизируем <tex> S' </tex>, мы также оптимизируем ответ для <tex> S </tex>.
'''Примечание''': если требуется полиномиальное время для решения задачи, сведение к другой задаче и трансформация расписания в допустимое также должны происходить за полиномиальное время.

С помощью этого метода решаются:
* Задачи класса [[Классификация задач|Open Shop]] при условии <tex>p_{ij}=1</tex> можно свести к задачам равной длительности на параллельных станках:
*:[[Opij1Sumwc|<tex> O \mid p_{ij} = 1 \mid \sum w_i C_i </tex>]]
*:<tex> O \mid p_{ij} = 1, r_i \mid C_{max} </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 161</ref>
* Задачи класса [[Классификация задач|Flow Shop]] при условии <tex>p_{ij}=1</tex> можно свести к задаче на одном станке:
*:[[Fpij1sumwu|<tex> F \mid p_{ij} = 1 \mid \sum w_i U_i </tex>]]
* Часто в задачах, в которых допускаются прерывания, оптимальный ответ совпадает с соответствующими задачами без прерываний:
*:<tex> P \mid pmtn \mid \sum w_i C_i </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 121</ref>
*:[[Flow shop|<tex> F2 \mid pmtn \mid C_{max} </tex>]]
* Ряд задач можно свести к задаче поиска максимального потока:
*:<tex> Q \mid pmtn, r_i\mid L_{max} </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 129-133</ref>
*:[[RSumCi|<tex> R \mid \mid \sum C_i </tex>]]
* Некоторые задачи сводятся к другим похожим задачам теории расписаний путем преобразования их расписаний:
*:[[1outtreesumwc|<tex> 1 \mid intree \mid \sum w_i C_i </tex>]]

== Построение расписания по нижней оценке ==
Этот метод обычно применим к задачам, в которых целевая функция — <tex> C_{max}</tex>.
Обычно построение расписания по нижней оценке происходит в два этапа:
# Построение некоторого набора нижних ограничений на произвольное расписание для задачи <tex> S </tex>.
# Построение произвольного допустимого расписания, достигающего максимального ограничения из построенного набора.

С помощью этого метода решаются следующие задачи:
* <tex> P \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 108</ref>
* <tex> R \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 137-139</ref>
* [[Opij1Cmax|<tex> O \mid p_{ij}=1 \mid C_{max}</tex>]]
* [[QpmtnCmax|<tex> Q \mid pmtn \mid C_{max}</tex>]]

Ниже будет рассмотрен частный пример решения задачи подобным образом:
=== P | pmtn | C_max ===
{{Задача
|definition = Имеется <tex>m</tex> однородных машин, работающих параллельно, и <tex>n</tex> работ, которые могут быть прерваны и продолжены позже. Необходимо минимизировать время выполнения всех работ
}}
Найдем набор ограничений на значение <tex> C_{max} </tex> для произвольного допустимого расписания <tex> S </tex> :
# В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому <tex> C_{max} \geqslant p_i </tex>.
# Если все станки работали время <tex> C_{max} </tex>, на них могло выполниться не больше <tex> C_{max} \cdot m </tex> работы, то есть <tex> \sum\limits_{i=1}^n p_i \leqslant C_{max} \cdot m </tex> и <tex> C_{max} \geqslant \dfrac1m \sum\limits_{i=1}^n p_i </tex>.
Из этих ограничений следует, что <tex> C_{max} = \max {\left( \max\limits_{i=1 \hdots n} p_i,~ \dfrac1m \sum\limits_{i=1}^n p_i \right)} </tex>.

Построим расписание, подходящее под эту границу: будем по очереди заполнять машины работами в произвольном порядке, и если очередная работа не помещается на текущей машине полностью, перенесем ее выходящую за <tex> C_{max} </tex> часть на следующую машину. Благодаря первому ограничению никакая работа не будет выполняться одновременно на двух станках, а благодаря второму — не останется работы, которую мы не сможем выполнить.

== Бинарный поиск по ответу ==
Этот способ часто подходит для задач, в которых надо минимизировать <tex>C_{max} </tex> (если мы умеем решать соответствующую задачу существования расписания), реже для <tex> \sum w_i U_i </tex>. Важно помнить, что если требуется полиномиальное по <tex> n </tex> решение, оно не должно зависеть от логарифма ответа, но иногда ответ ограничен полиномом от <tex>n</tex>, и мы можем применить этот метод.

Примером решения задач подобным методом служит следующая задача:
[[QpmtnriLmax|<tex> Q \mid pmtn, r_i \mid L_{max} </tex>]]

== Жадное построение расписания ==
Для решения задач теории расписаний часто применяется [[Определение матроида|теория матроидо]]в, а в частности — [[Теорема Радо-Эдмондса (жадный алгоритм)|жадный алгоритм]]: алгоритм решения задач путем выбора локально оптимальных решений на каждом этапе алгоритма.
Естественно, далеко не все оптимизационные задачи можно решать жадно — для этого сначала необходимо доказать оптимальность жадного выбора.

С помощью этого метода решаются:
* [[Правило Лаулера|<tex> 1 \mid prec \mid f_{max} </tex>]]
* [[1outtreesumwc|<tex> 1 \mid outtree \mid \sum w_i C_i </tex>]]
* [[1pi1sumwu|<tex> 1 \mid p_i = 1 \mid \sum w_i U_i </tex>]]
* [[1sumu|<tex> 1 \mid \mid \sum U_i </tex>]]

Обычно оптимальность жадного выбора доказывают двумя способами:

=== Неправильно ===
Приведем пример часто распространенных '''неправильных''' действий при доказательстве оптимальности жадного алгоритма:

Пусть предложенным нами алгоритмом мы получили какое-то решение <tex> S </tex>. Атомарными изменениями в этом решении <tex> S </tex> будем получать другие допустимые решения <tex> S' </tex> и докажем, что <tex> f(S) \leqslant f(S') </tex>. Тогда решение <tex> S </tex> — оптимально.

Проблема в этих рассуждениях в том, что ими мы доказываем локальную оптимальность алгоритма в решении <tex> S </tex>. Получение же глобального минимума может потребовать нескольких атомарных изменений в расписании, поэтому доказать оптимальность таким образом в общем случае невозможно. Как ближайшую аналогию, можно привести '''неправильное''' утверждение для произвольной функции <tex> f(\bar x) </tex> — «если все частные производные <tex> \dfrac{\partial f}{\partial x_1} \dots \dfrac{\partial f}{\partial x_n} </tex> неотрицательны, то в точке <tex> \bar x </tex> наблюдается глобальный минимум».

=== Правильно ===
При доказательстве оптимательности применима стратегия '''аргумент замены''' (англ. ''exchange argument''). Стратегия заключается в рассмотрении текущего решения <tex> S </tex> и оптимального решения <tex> O </tex>. Далее предлагается способ модификации <tex> O </tex> в <tex> O'</tex> так, что:
# <tex> f(O') \leqslant f(O) </tex>, то есть <tex> O' </tex> также оптимально.
# <tex> O' </tex> «более похоже» на <tex> S </tex>, чем на <tex> O </tex>.

Если такой способ найден, получаем, что какой-то последовательностью модификаций <tex> O \to O_t' \to \dots \to O_1' \to S </tex> получим <tex> f(S) \leqslant f(O_1') \leqslant \dots \leqslant f(O_t') \leqslant f(O) </tex>, из чего следует оптимальность <tex> S </tex>.

Отношение «более похоже» должно быть [[Отношение порядка | отношением частичного строгого порядка]]. Часто в качестве него можно выбрать отношение «длина наибольшего общего префикса решения <tex> A </tex> и <tex> S </tex> меньше наибольшего общего префикса решения <tex> B </tex> и <tex> S </tex>». Тогда если мы сможем увеличить длину наибольшего общего префикса для оптимального решения, не нарушив оптимальности, мы приблизимся к <tex> S </tex>. Можно выбирать и более сложные отношения, например, в доказательстве оптимальности алгоритма <tex> P \mid \mid \sum w_i C_i </tex> для решения задачи <tex> P \mid pmtn \mid \sum w_i C_i </tex> используется отношение «время последнего прерывания больше или количество прерываний меньше».

== См. также. ==
* [[Правило Лаулера]]
* [[Flow shop]]
* [[Opi1sumu|<tex> O \mid p_{ij} = 1 \mid \sum U_i</tex>]]

== Примечания ==
<references/>

== Источники информации ==
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer ISBN 978-3-540-69515-8

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

Методы решения задач теории расписаний

2016-06-07T15:04:10Z

Qradimir: /* Жадное построение расписания */

== Сведение к другой задаче ==
При сведении текущей задачи теории расписаний <tex> S </tex> к какой-то другой <tex> S' </tex> (не обязательно задаче теории расписаний) необходимо доказать два пункта:
# Допустимость расписания, построенного с помощью задачи <tex> S' </tex>, или существование способа его трансформации в допустимое без нарушения оптимальности.
# Следствие того, что если мы оптимизируем <tex> S' </tex>, мы также оптимизируем ответ для <tex> S </tex>.
'''Примечание''': если требуется полиномиальное время для решения задачи, сведение к другой задаче и трансформация расписания в допустимое также должны происходить за полиномиальное время.

С помощью этого метода решаются:
* Задачи класса [[Классификация задач|Open Shop]] при условии <tex>p_{ij}=1</tex> можно свести к задачам равной длительности на параллельных станках:
*:[[Opij1Sumwc|<tex> O \mid p_{ij} = 1 \mid \sum w_i C_i </tex>]]
*:<tex> O \mid p_{ij} = 1, r_i \mid C_{max} </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 161</ref>
* Задачи класса [[Классификация задач|Flow Shop]] при условии <tex>p_{ij}=1</tex> можно свести к задаче на одном станке:
*:[[Fpij1sumwu|<tex> F \mid p_{ij} = 1 \mid \sum w_i U_i </tex>]]
* Часто в задачах, в которых допускаются прерывания, оптимальный ответ совпадает с соответствующими задачами без прерываний:
*:<tex> P \mid pmtn \mid \sum w_i C_i </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 121</ref>
*:[[Flow shop|<tex> F2 \mid pmtn \mid C_{max} </tex>]]
* Ряд задач можно свести к задаче поиска максимального потока:
*:<tex> Q \mid pmtn, r_i\mid L_{max} </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 129-133</ref>
*:[[RSumCi|<tex> R \mid \mid \sum C_i </tex>]]
* Некоторые задачи сводятся к другим похожим задачам теории расписаний путем преобразования их расписаний:
*:[[1outtreesumwc|<tex> 1 \mid intree \mid \sum w_i C_i </tex>]]

== Построение расписания по нижней оценке ==
Этот метод обычно применим к задачам, в которых целевая функция — <tex> C_{max}</tex>.
Обычно построение расписания по нижней оценке происходит в два этапа:
# Построение некоторого набора нижних ограничений на произвольное расписание для задачи <tex> S </tex>.
# Построение произвольного допустимого расписания, достигающего максимального ограничения из построенного набора.

С помощью этого метода решаются следующие задачи:
* <tex> P \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 108</ref>
* <tex> R \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 137-139</ref>
* [[Opij1Cmax|<tex> O \mid p_{ij}=1 \mid C_{max}</tex>]]
* [[QpmtnCmax|<tex> Q \mid pmtn \mid C_{max}</tex>]]

Ниже будет рассмотрен частный пример решения задачи подобным образом:
=== P | pmtn | C_max ===
{{Задача
|definition = Имеется <tex>m</tex> однородных машин, работающих параллельно, и <tex>n</tex> работ, которые могут быть прерваны и продолжены позже. Необходимо минимизировать время выполнения всех работ
}}
Найдем набор ограничений на значение <tex> C_{max} </tex> для произвольного допустимого расписания <tex> S </tex> :
# В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому <tex> C_{max} \geqslant p_i </tex>.
# Если все станки работали время <tex> C_{max} </tex>, на них могло выполниться не больше <tex> C_{max} \cdot m </tex> работы, то есть <tex> \sum\limits_{i=1}^n p_i \leqslant C_{max} \cdot m </tex> и <tex> C_{max} \geqslant \dfrac1m \sum\limits_{i=1}^n p_i </tex>.
Из этих ограничений следует, что <tex> C_{max} = \max {\left( \max\limits_{i=1 \hdots n} p_i,~ \dfrac1m \sum\limits_{i=1}^n p_i \right)} </tex>.

Построим расписание, подходящее под эту границу: будем по очереди заполнять машины работами в произвольном порядке, и если очередная работа не помещается на текущей машине полностью, перенесем ее выходящую за <tex> C_{max} </tex> часть на следующую машину. Благодаря первому ограничению никакая работа не будет выполняться одновременно на двух станках, а благодаря второму — не останется работы, которую мы не сможем выполнить.

== Бинарный поиск по ответу ==
Этот способ часто подходит для задач, в которых надо минимизировать <tex>C_{max} </tex> (если мы умеем решать соответствующую задачу существования расписания), реже для <tex> \sum w_i U_i </tex>. Важно помнить, что если требуется полиномиальное по <tex> n </tex> решение, оно не должно зависеть от логарифма ответа, но иногда ответ ограничен полиномом от <tex>n</tex>, и мы можем применить этот метод.

Примером решения задач подобным методом служит следующая задача:
[[QpmtnriLmax|<tex> Q \mid pmtn, r_i \mid L_{max} </tex>]]

== Жадное построение расписания ==
Для решения задач теории расписаний часто применяется [[Определение матроида|теория матроидо]]в, а в частности — [[Теорема Радо-Эдмондса (жадный алгоритм)|жадный алгоритм]] : алгоритм решения задач путем выбора локально оптимальных решений на каждом этапе алгоритма.
Естественно, далеко не все оптимизационные задачи можно решать жадно — для этого сначала необходимо доказать оптимальность жадного выбора.

С помощью этого метода решаются:
* [[Правило Лаулера|<tex> 1 \mid prec \mid f_{max} </tex>]]
* [[1outtreesumwc|<tex> 1 \mid outtree \mid \sum w_i C_i </tex>]]
* [[1pi1sumwu|<tex> 1 \mid p_i = 1 \mid \sum w_i U_i </tex>]]
* [[1sumu|<tex> 1 \mid \mid \sum U_i </tex>]]

Обычно оптимальность жадного выбора доказывают двумя способами:

=== Неправильно ===
Приведем пример часто распространенных '''неправильных''' действий при доказательстве оптимальности жадного алгоритма:

Пусть предложенным нами алгоритмом мы получили какое-то решение <tex> S </tex>. Атомарными изменениями в этом решении <tex> S </tex> будем получать другие допустимые решения <tex> S' </tex> и докажем, что <tex> f(S) \leqslant f(S') </tex>. Тогда решение <tex> S </tex> — оптимально.

Проблема в этих рассуждениях в том, что ими мы доказываем локальную оптимальность алгоритма в решении <tex> S </tex>. Получение же глобального минимума может потребовать нескольких атомарных изменений в расписании, поэтому доказать оптимальность таким образом в общем случае невозможно. Как ближайшую аналогию, можно привести '''неправильное''' утверждение для произвольной функции <tex> f(\bar x) </tex> — «если все частные производные <tex> \dfrac{\partial f}{\partial x_1} \dots \dfrac{\partial f}{\partial x_n} </tex> неотрицательны, то в точке <tex> \bar x </tex> наблюдается глобальный минимум».

=== Правильно ===
При доказательстве оптимательности применима стратегия '''аргумент замены''' (англ. ''exchange argument''). Стратегия заключается в рассмотрении текущего решения <tex> S </tex> и оптимального решения <tex> O </tex>. Далее предлагается способ модификации <tex> O </tex> в <tex> O'</tex> так, что:
# <tex> f(O') \leqslant f(O) </tex>, то есть <tex> O' </tex> также оптимально.
# <tex> O' </tex> «более похоже» на <tex> S </tex>, чем на <tex> O </tex>.

Если такой способ найден, получаем, что какой-то последовательностью модификаций <tex> O \to O_t' \to \dots \to O_1' \to S </tex> получим <tex> f(S) \leqslant f(O_1') \leqslant \dots \leqslant f(O_t') \leqslant f(O) </tex>, из чего следует оптимальность <tex> S </tex>.

Отношение «более похоже» должно быть [[Отношение порядка | отношением частичного строгого порядка]]. Часто в качестве него можно выбрать отношение «длина наибольшего общего префикса решения <tex> A </tex> и <tex> S </tex> меньше наибольшего общего префикса решения <tex> B </tex> и <tex> S </tex>». Тогда если мы сможем увеличить длину наибольшего общего префикса для оптимального решения, не нарушив оптимальности, мы приблизимся к <tex> S </tex>. Можно выбирать и более сложные отношения, например, в доказательстве оптимальности алгоритма <tex> P \mid \mid \sum w_i C_i </tex> для решения задачи <tex> P \mid pmtn \mid \sum w_i C_i </tex> используется отношение «время последнего прерывания больше или количество прерываний меньше».

== См. также. ==
* [[Правило Лаулера]]
* [[Flow shop]]
* [[Opi1sumu|<tex> O \mid p_{ij} = 1 \mid \sum U_i</tex>]]

== Примечания ==
<references/>

== Источники информации ==
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer ISBN 978-3-540-69515-8

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

Методы решения задач теории расписаний

2016-06-07T15:02:13Z

Qradimir: Фиксы

== Сведение к другой задаче ==
При сведении текущей задачи теории расписаний <tex> S </tex> к какой-то другой <tex> S' </tex> (не обязательно задаче теории расписаний) необходимо доказать два пункта:
# Допустимость расписания, построенного с помощью задачи <tex> S' </tex>, или существование способа его трансформации в допустимое без нарушения оптимальности.
# Следствие того, что если мы оптимизируем <tex> S' </tex>, мы также оптимизируем ответ для <tex> S </tex>.
'''Примечание''': если требуется полиномиальное время для решения задачи, сведение к другой задаче и трансформация расписания в допустимое также должны происходить за полиномиальное время.

С помощью этого метода решаются:
* Задачи класса [[Классификация задач|Open Shop]] при условии <tex>p_{ij}=1</tex> можно свести к задачам равной длительности на параллельных станках:
*:[[Opij1Sumwc|<tex> O \mid p_{ij} = 1 \mid \sum w_i C_i </tex>]]
*:<tex> O \mid p_{ij} = 1, r_i \mid C_{max} </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 161</ref>
* Задачи класса [[Классификация задач|Flow Shop]] при условии <tex>p_{ij}=1</tex> можно свести к задаче на одном станке:
*:[[Fpij1sumwu|<tex> F \mid p_{ij} = 1 \mid \sum w_i U_i </tex>]]
* Часто в задачах, в которых допускаются прерывания, оптимальный ответ совпадает с соответствующими задачами без прерываний:
*:<tex> P \mid pmtn \mid \sum w_i C_i </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 121</ref>
*:[[Flow shop|<tex> F2 \mid pmtn \mid C_{max} </tex>]]
* Ряд задач можно свести к задаче поиска максимального потока:
*:<tex> Q \mid pmtn, r_i\mid L_{max} </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 129-133</ref>
*:[[RSumCi|<tex> R \mid \mid \sum C_i </tex>]]
* Некоторые задачи сводятся к другим похожим задачам теории расписаний путем преобразования их расписаний:
*:[[1outtreesumwc|<tex> 1 \mid intree \mid \sum w_i C_i </tex>]]

== Построение расписания по нижней оценке ==
Этот метод обычно применим к задачам, в которых целевая функция — <tex> C_{max}</tex>.
Обычно построение расписания по нижней оценке происходит в два этапа:
# Построение некоторого набора нижних ограничений на произвольное расписание для задачи <tex> S </tex>.
# Построение произвольного допустимого расписания, достигающего максимального ограничения из построенного набора.

С помощью этого метода решаются следующие задачи:
* <tex> P \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 108</ref>
* <tex> R \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 137-139</ref>
* [[Opij1Cmax|<tex> O \mid p_{ij}=1 \mid C_{max}</tex>]]
* [[QpmtnCmax|<tex> Q \mid pmtn \mid C_{max}</tex>]]

Ниже будет рассмотрен частный пример решения задачи подобным образом:
=== P | pmtn | C_max ===
{{Задача
|definition = Имеется <tex>m</tex> однородных машин, работающих параллельно, и <tex>n</tex> работ, которые могут быть прерваны и продолжены позже. Необходимо минимизировать время выполнения всех работ
}}
Найдем набор ограничений на значение <tex> C_{max} </tex> для произвольного допустимого расписания <tex> S </tex> :
# В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому <tex> C_{max} \geqslant p_i </tex>.
# Если все станки работали время <tex> C_{max} </tex>, на них могло выполниться не больше <tex> C_{max} \cdot m </tex> работы, то есть <tex> \sum\limits_{i=1}^n p_i \leqslant C_{max} \cdot m </tex> и <tex> C_{max} \geqslant \dfrac1m \sum\limits_{i=1}^n p_i </tex>.
Из этих ограничений следует, что <tex> C_{max} = \max {\left( \max\limits_{i=1 \hdots n} p_i,~ \dfrac1m \sum\limits_{i=1}^n p_i \right)} </tex>.

Построим расписание, подходящее под эту границу: будем по очереди заполнять машины работами в произвольном порядке, и если очередная работа не помещается на текущей машине полностью, перенесем ее выходящую за <tex> C_{max} </tex> часть на следующую машину. Благодаря первому ограничению никакая работа не будет выполняться одновременно на двух станках, а благодаря второму — не останется работы, которую мы не сможем выполнить.

== Бинарный поиск по ответу ==
Этот способ часто подходит для задач, в которых надо минимизировать <tex>C_{max} </tex> (если мы умеем решать соответствующую задачу существования расписания), реже для <tex> \sum w_i U_i </tex>. Важно помнить, что если требуется полиномиальное по <tex> n </tex> решение, оно не должно зависеть от логарифма ответа, но иногда ответ ограничен полиномом от <tex>n</tex>, и мы можем применить этот метод.

Примером решения задач подобным методом служит следующая задача:
[[QpmtnriLmax|<tex> Q \mid pmtn, r_i \mid L_{max} </tex>]]

== Жадное построение расписания ==
Для решения задач теории расписаний часто применяется [[Определение матроида|теория матроидо]]в, а в частности — [[Теорема Радо-Эдмондса (жадный алгоритм)|жадный алгоритм]] — алгоритм решения задач путем выбора локально оптимальных решений на каждом этапе алгоритма.
Естественно, далеко не все оптимизационные задачи можно решать жадно — для этого сначала необходимо доказать оптимальность жадного выбора.

С помощью этого метода решаются:
* [[Правило Лаулера|<tex> 1 \mid prec \mid f_{max} </tex>]]
* [[1outtreesumwc|<tex> 1 \mid outtree \mid \sum w_i C_i </tex>]]
* [[1pi1sumwu|<tex> 1 \mid p_i = 1 \mid \sum w_i U_i </tex>]]
* [[1sumu|<tex> 1 \mid \mid \sum U_i </tex>]]

Обычно оптимальность жадного выбора доказывают двумя способами:

=== Неправильно ===
Приведем пример часто распространенных '''неправильных''' действий при доказательстве оптимальности жадного алгоритма:

Пусть предложенным нами алгоритмом мы получили какое-то решение <tex> S </tex>. Атомарными изменениями в этом решении <tex> S </tex> будем получать другие допустимые решения <tex> S' </tex> и докажем, что <tex> f(S) \leqslant f(S') </tex>. Тогда решение <tex> S </tex> — оптимально.

Проблема в этих рассуждениях в том, что ими мы доказываем локальную оптимальность алгоритма в решении <tex> S </tex>. Получение же глобального минимума может потребовать нескольких атомарных изменений в расписании, поэтому доказать оптимальность таким образом в общем случае невозможно. Как ближайшую аналогию, можно привести '''неправильное''' утверждение для произвольной функции <tex> f(\bar x) </tex> — «если все частные производные <tex> \dfrac{\partial f}{\partial x_1} \dots \dfrac{\partial f}{\partial x_n} </tex> неотрицательны, то в точке <tex> \bar x </tex> наблюдается глобальный минимум».

=== Правильно ===
При доказательстве оптимательности применима стратегия '''аргумент замены''' (англ. ''exchange argument''). Стратегия заключается в рассмотрении текущего решения <tex> S </tex> и оптимального решения <tex> O </tex>. Далее предлагается способ модификации <tex> O </tex> в <tex> O'</tex> так, что:
# <tex> f(O') \leqslant f(O) </tex>, то есть <tex> O' </tex> также оптимально.
# <tex> O' </tex> «более похоже» на <tex> S </tex>, чем на <tex> O </tex>.

Если такой способ найден, получаем, что какой-то последовательностью модификаций <tex> O \to O_t' \to \dots \to O_1' \to S </tex> получим <tex> f(S) \leqslant f(O_1') \leqslant \dots \leqslant f(O_t') \leqslant f(O) </tex>, из чего следует оптимальность <tex> S </tex>.

Отношение «более похоже» должно быть [[Отношение порядка | отношением частичного строгого порядка]]. Часто в качестве него можно выбрать отношение «длина наибольшего общего префикса решения <tex> A </tex> и <tex> S </tex> меньше наибольшего общего префикса решения <tex> B </tex> и <tex> S </tex>». Тогда если мы сможем увеличить длину наибольшего общего префикса для оптимального решения, не нарушив оптимальности, мы приблизимся к <tex> S </tex>. Можно выбирать и более сложные отношения, например, в доказательстве оптимальности алгоритма <tex> P \mid \mid \sum w_i C_i </tex> для решения задачи <tex> P \mid pmtn \mid \sum w_i C_i </tex> используется отношение «время последнего прерывания больше или количество прерываний меньше».

== См. также. ==
* [[Правило Лаулера]]
* [[Flow shop]]
* [[Opi1sumu|<tex> O \mid p_{ij} = 1 \mid \sum U_i</tex>]]

== Примечания ==
<references/>

== Источники информации ==
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer ISBN 978-3-540-69515-8

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

Opij1Cmax

2016-06-07T14:24:53Z

Qradimir: Таблица в техе

<tex dpi = "200">O \mid p_{ij} = 1 \mid C_{max}</tex>
{{Задача
|definition = Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex> работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно 1. Необходимо минимизировать время выполнения всех работ.
}}
==Алгоритм==

===Описание алгоритма===
Минимальное значение <tex> C_{max} </tex> упирается в следующие ограничения:
# В допустимом расписании на каждом станке надо обработать каждую работу, поэтому <tex> C_{max} \geqslant n </tex>.
# В допустимом расписании каждую работу нужно обработать на всех станках, причем ее нельзя обрабатывать на двух станках одновременно, поэтому <tex> C_{max} \geqslant m </tex>.
Тогда <tex> C_{max} = \max{(m, n)} </tex>.

В случае <tex> n \geqslant m </tex> оптимальное расписание строится циклическими сдвигами последовательности <tex> 1 \dots n </tex> и выглядит следующим образом:
{| class="wikitable"
|-
!
!| <tex>\textbf1</tex> || <tex>\textbf2</tex> || <tex>\textbf3</tex> ||<tex>\bf{\hdots}</tex>|| <tex>\textbf{n - 1}</tex> || <tex>\textbf{n}</tex>
|- style="text-align:center;"
!<tex>\bf{M_1}</tex>
|| <tex>1</tex> || <tex>2</tex> || <tex>3</tex> ||<tex>\hdots</tex>|| <tex>n - 1</tex> || <tex>n</tex>
|- style="text-align:center;"
!<tex>\bf{M_2}</tex>
|| <tex>n</tex> || <tex>1</tex> || <tex>2</tex> ||<tex>\hdots</tex>|| <tex>n - 2</tex> || <tex>n - 1</tex>
|- style="text-align:center;"
!<tex>\bf{M_3}</tex>
|| <tex>n - 1</tex> || <tex>n</tex> || <tex>1</tex> ||<tex>\hdots</tex>|| <tex>n - 3</tex> || <tex>n - 2</tex>
|- style="text-align:center;"
!<tex>\bf{\vdots}</tex>
||<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\ddots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>
|- style="text-align:center;"
!<tex>\bf{M_m}</tex>
|| <tex>n - m + 2</tex> || <tex>n - m + 3</tex> || <tex>n - m + 4</tex> ||<tex>\hdots</tex>|| <tex>n - m</tex> || <tex>n - m + 1</tex>
|}

Если же <tex> n < m </tex>, добавим <tex> m - n </tex> фиктивных работ с номерами <tex> n + 1 \dots m </tex>, построим расписание способом выше и удалим из полученного расписания фиктивные работы.

===Оценка сложности алгоритма===
Минимальное значение <tex> C_{max} </tex> вычисляется за <tex> \mathcal{O}(1) </tex> времени.
Построение расписания сводится к заполнению матрицы размером <tex> m \times \max{(m, n)} </tex> и выполняется за <tex> \mathcal{O}(m \dot (m + n)) </tex> времени.

==См. также.==
* [[Методы решения задач теории расписаний]]
* [[O2Cmax|<tex> O2 \mid \mid C_{max} </tex>]]
* [[QpmtnCmax|<tex> Q \mid pmtn \mid C_{max} </tex>]]
* [[Opij1Sumwc|<tex> O \mid p_{ij} = 1 \mid \sum w_i C_i </tex>]]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

RSumCi

2016-06-07T02:47:03Z

Qradimir: точки

<tex dpi="200">R \mid \mid \sum C_i</tex>
{{Задача
|definition=Дано <tex> n </tex> работ и <tex> m </tex> станков, причем для каждого станка длительность выполнения на нем <tex>i</tex>-й работы составляет <tex> p_{ij} </tex>. Необходимо минимизировать сумму времени выполнения работ.
}}
==Алгоритм==

===Описание алгоритма===
Рассмотрим произвольное допустимое расписание для этой задачи. Рассмотрим какую-то станок <tex> j </tex>, пусть на нем выполняется <tex>n_j</tex> работ. Тогда вклад этого станка в целевую функцию (не теряя общности, пронумеруем работы на этом станке от <tex>1 </tex> до <tex>n_j</tex>) рассчитывается как:

<tex>
\sum\limits_{i=1}^{n_j} \left( p_ij + \sum\limits_{q=1}^{i-1} p_qj \right) =
n_j \cdot p_{1j} + (n_j - 1) \cdot p_{2j} + \dots + 2 p_{(n_j-1)j} + p_{n_jj}
</tex>

Заметим, что в каждом допустимом расписании перед каждой работой окажется коэффициент <tex> k </tex>, означающий, что соответствующая работа выпллняется <tex> k </tex>-й с конца. Понятно, что в различных расписаниях <tex> k </tex> может принимать значения от <tex>1</tex> до <tex>n</tex>.

Сведем задачу к назначению каждой работы <tex> i </tex> позиции с конца <tex> k </tex> на станке <tex> j </tex> с помощью алгоритма [[Поток минимальной стоимости | поиска максимального потока минимальной стоимости]]. Поместим в левую долю графа работы, в правую долю — пары из станка и коэффициента и проведем соответствующие ребра пропускной способности <tex>1</tex> и стоимости <tex>k \cdot p_{ij}</tex>, соответствующие вкладу работы в целевую функцию, если она окажется в позиции <tex> k </tex> с конца на станке <tex> j </tex>. Проведем из стока в левую долю ребра стоимости <tex>0</tex> и пропускной способности <tex>1</tex>, из правой доли в сток — также ребра стоимости <tex> 0 </tex> и пропускной способности <tex>1</tex>. Максимальный поток минимальной стоймости в построенной сети будет ответом на исходную задачу.
{{Утверждение
|statement=Eсли ребро <tex> i \to (j, k) </tex> насыщено потоком, то работа <tex> i </tex> в оптимальном расписании должна стоять на станке <tex> j </tex> в позиции <tex> k </tex> с конца.
|proof=
# Целевя функция текущей задачи совпадает со стомостью максимального потока в построенной сети, так как у ребер между долями пропускная способность 1, а у дополнительных ребер из истока и в сток нулевая стоимость, и они не могут внести вклад в целевую функцию.
# Расписание, построенное по вышепредставленному способу действительно будет допустимым.
## Благодаря ограничениям на поток, входящий в левую долю, каждая работа будет назначена только один раз.
## Благодаря ограничениям на поток, выходящий из правой доли, на каждую позицию будет назначено не более одной работы.
## Докажем, что не возникает ситуации такой, что существует такая позиция <tex> l </tex>, что в этой позиции с конца стоит какая-то работа, а в позиции <tex> l - 1 </tex> с конца — нет (это противоречит определению <tex>l</tex>-й с конца работы). Такая ситуация означает, что ребро <tex> i \to (j, l) </tex> оказалось насышено потоком, а ребро <tex>i \to (j, l - 1) </tex> — не насыщено. Но стоимость ребра <tex> i \to (j, l - 1) </tex> меньше стоимости ребра <tex> i \to (j, l) </tex>, поэтому можем переместить поток с ребра <tex> i \to (j, l) </tex> на ребро <tex> i \to (j, l - 1) </tex>, не нарушив свойства потока и улучшив целевую функцию, что противоречит оптимальности ответа для mincost-maxflow. Следовательно, такой позиции не возникнет и расписание будет допустимым.
}}

===Время выполнения===
Время выполнения алгоритма поиска максимального потока минимальной стоймости равно <tex> \mathcal{O}(V \cdot E^2) </tex>. Количество вершин в получаемой сети равно <tex> \mathcal{O}(m \cdot n) </tex>. Количество ребер в сети равно <tex> \mathcal{O}(m \cdot n^2) </tex>. Следовательно, ассимптотика алгоритма равна <tex> \mathcal{O}(m^3 \cdot n^5) </tex>.

==См. также==
* [[Поток минимальной стоимости]]
* [[Методы решения задач теории расписаний]]
* [[PSumCi|<tex>P \mid \mid \sum C_i</tex>]]
* [[QSumCi|<tex>Q \mid \mid \sum C_i</tex>]]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

RSumCi

2016-06-07T02:46:27Z

Qradimir: точки

<tex dpi="200">R \mid \mid \sum C_i</tex>
{{Задача
|definition=Дано <tex> n </tex> работ и <tex> m </tex> станков, причем для каждого станка длительность выполнения на нем <tex>i</tex>-й работы составляет <tex> p_{ij} </tex>. Необходимо минимизировать сумму времени выполнения работ.
}}
==Алгоритм==

===Описание алгоритма===
Рассмотрим произвольное допустимое расписание для этой задачи. Рассмотрим какую-то станок <tex> j </tex>, пусть на нем выполняется <tex>n_j</tex> работ. Тогда вклад этого станка в целевую функцию (не теряя общности, пронумеруем работы на этом станке от <tex>1 </tex> до <tex>n_j</tex>) рассчитывается как:

<tex>
\sum\limits_{i=1}^{n_j} \left( p_ij + \sum\limits_{q=1}^{i-1} \cdot p_qj \right) =
n_j \cdot p_{1j} + (n_j - 1) \cdot p_{2j} + \dots + 2 p_{(n_j-1)j} + p_{n_jj}
</tex>

Заметим, что в каждом допустимом расписании перед каждой работой окажется коэффициент <tex> k </tex>, означающий, что соответствующая работа выпллняется <tex> k </tex>-й с конца. Понятно, что в различных расписаниях <tex> k </tex> может принимать значения от <tex>1</tex> до <tex>n</tex>.

Сведем задачу к назначению каждой работы <tex> i </tex> позиции с конца <tex> k </tex> на станке <tex> j </tex> с помощью алгоритма [[Поток минимальной стоимости | поиска максимального потока минимальной стоимости]]. Поместим в левую долю графа работы, в правую долю — пары из станка и коэффициента и проведем соответствующие ребра пропускной способности <tex>1</tex> и стоимости <tex>k \cdot p_{ij}</tex>, соответствующие вкладу работы в целевую функцию, если она окажется в позиции <tex> k </tex> с конца на станке <tex> j </tex>. Проведем из стока в левую долю ребра стоимости <tex>0</tex> и пропускной способности <tex>1</tex>, из правой доли в сток — также ребра стоимости <tex> 0 </tex> и пропускной способности <tex>1</tex>. Максимальный поток минимальной стоймости в построенной сети будет ответом на исходную задачу.
{{Утверждение
|statement=Eсли ребро <tex> i \to (j, k) </tex> насыщено потоком, то работа <tex> i </tex> в оптимальном расписании должна стоять на станке <tex> j </tex> в позиции <tex> k </tex> с конца.
|proof=
# Целевя функция текущей задачи совпадает со стомостью максимального потока в построенной сети, так как у ребер между долями пропускная способность 1, а у дополнительных ребер из истока и в сток нулевая стоимость, и они не могут внести вклад в целевую функцию.
# Расписание, построенное по вышепредставленному способу действительно будет допустимым.
## Благодаря ограничениям на поток, входящий в левую долю, каждая работа будет назначена только один раз.
## Благодаря ограничениям на поток, выходящий из правой доли, на каждую позицию будет назначено не более одной работы.
## Докажем, что не возникает ситуации такой, что существует такая позиция <tex> l </tex>, что в этой позиции с конца стоит какая-то работа, а в позиции <tex> l - 1 </tex> с конца — нет (это противоречит определению <tex>l</tex>-й с конца работы). Такая ситуация означает, что ребро <tex> i \to (j, l) </tex> оказалось насышено потоком, а ребро <tex>i \to (j, l - 1) </tex> — не насыщено. Но стоимость ребра <tex> i \to (j, l - 1) </tex> меньше стоимости ребра <tex> i \to (j, l) </tex>, поэтому можем переместить поток с ребра <tex> i \to (j, l) </tex> на ребро <tex> i \to (j, l - 1) </tex>, не нарушив свойства потока и улучшив целевую функцию, что противоречит оптимальности ответа для mincost-maxflow. Следовательно, такой позиции не возникнет и расписание будет допустимым.
}}

===Время выполнения===
Время выполнения алгоритма поиска максимального потока минимальной стоймости равно <tex> \mathcal{O}(V \cdot E^2) </tex>. Количество вершин в получаемой сети равно <tex> \mathcal{O}(m \cdot n) </tex>. Количество ребер в сети равно <tex> \mathcal{O}(m \cdot n^2) </tex>. Следовательно, ассимптотика алгоритма равна <tex> \mathcal{O}(m^3 \cdot n^5) </tex>.

==См. также==
* [[Поток минимальной стоимости]]
* [[Методы решения задач теории расписаний]]
* [[PSumCi|<tex>P \mid \mid \sum C_i</tex>]]
* [[QSumCi|<tex>Q \mid \mid \sum C_i</tex>]]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

Методы решения задач теории расписаний

2016-06-07T02:38:25Z

Qradimir: Фиксы

== Сведение к другой задаче ==
При сведении текущей задачи теории расписаний <tex> S </tex> к какой-то другой <tex> S' </tex> (не обязательно задаче теории расписаний) необходимо доказать два пункта:
# Допустимость расписания, построенного с помощью задачи <tex> S' </tex>, или существование способа его трансформации в допустимое без нарушения оптимальности.
# Следствие того, что если мы оптимизируем <tex> S' </tex>, мы также оптимизируем ответ для <tex> S </tex>.
'''Примечание''': если требуется полиномиальное время для решения задачи, сведение к другой задаче и трансформация расписания в допустимое также должны происходить за полиномиальное время.

С помощью этого метода решаются:
* Некоторые задачи класса Open Shop при условии <tex>p_{ij}=1</tex> сводятся к задачам равной длительности на параллельных станках.
*:[[Opij1Sumwc|<tex> O \mid p_{ij} = 1 \mid \sum w_i C_i </tex>]]
*:<tex> O \mid p_{ij} = 1, r_i \mid C_{max} </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 161</ref>
* Некоторые задачи класса Flow Shop при условии <tex>p_{ij}=1</tex> сводятся к задаче на одном станке.
*:[[Fpij1sumwu|<tex> F \mid p_{ij} = 1 \mid \sum w_i U_i </tex>]]
* Часто в задачах, в которых допускаются прерывания, оптимальный ответ совпадает с соответствующими задачами без прерываний:
*:<tex> P \mid pmtn \mid \sum w_i C_i </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 121</ref>
*:[[Flow shop|<tex> F2 \mid pmtn \mid C_{max} </tex>]]
* Некоторые задачи проверки существования расписания сводятся к задаче поиска максимального потока:
*:<tex> Q \mid pmtn, r_i\mid L_{max} </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 129-133</ref>
*:[[RSumCi|<tex> R \mid \mid \sum C_i </tex>]]
* Некоторые задачи сводятся к другим похожим задачам теории расписаний путем преобразования их расписаний:
*:[[1outtreesumwc|<tex> 1 \mid intree \mid \sum w_i C_i </tex>]]

== Построение расписания по нижней оценке ==
Этот метод обычно применим к задачам, в которых целевая функция — <tex> C_{max}</tex>.
Обычно построение расписания по нижней оценке происходит в два этапа:
# Построение некоторого набора нижних ограничений на произвольное расписание для задачи <tex> S </tex>.
# Построение произвольного допустимого расписания, достигающего максимального ограничения из построенного набора.

С помощью этого метода решаются следующие задачи:
* <tex> P \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 108</ref>
* <tex> R \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 137-139</ref>
* [[Opij1Cmax|<tex> O \mid p_{ij}=1 \mid C_{max}</tex>]]
* [[QpmtnCmax|<tex> Q \mid pmtn \mid C_{max}</tex>]]

=== P | pmtn | C_max ===
Найдем набор ограничений на значение <tex> C_{max} </tex> для произвольного допустимого расписания <tex> S </tex> :
# В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому <tex> C_{max} \geqslant p_i </tex>.
# Если все станки работали время <tex> C_{max} </tex>, на них могло выполниться не больше <tex> C_{max} \cdot m </tex> работы, то есть <tex> \sum\limits_i p_i \leqslant C_{max} \cdot m </tex> и <tex> C_{max} \geqslant \dfrac1m \sum\limits_i p_i </tex>.
Из этих ограничений следует, что <tex> C_{max} = \max {\left( \max\limits_i p_i; \dfrac1m \sum\limits_i p_i \right)} </tex>.

Построим расписание, подходящее под эту границу: будем по очереди заполнять машины работами в произвольном порядке, и если очередная работа не помещается на текущей машине полностью, перенесем ее выходящую за <tex> C_{max} </tex> часть на следующую машину. Благодаря первому ограничению никакая работа не будет выполняться одновременно на двух станках, а благодаря второму — не останется работы, которую мы не сможем выполнить.

== Бинарный поиск по ответу ==
Этот способ часто подходит для задач, в которых надо минимизировать <tex>C_{max} </tex> (если мы умеем решать соответствующую задачу существования расписания), реже для <tex> \sum w_i U_i </tex>. Важно помнить, что если требуется полиномиальное по <tex> n </tex> решение, оно не должно зависеть от логарифма ответа, но иногда ответ ограничен полиномом от <tex>n</tex>, и мы можем применить этот метод.

Примером решения задач подобным методом служит следующая задача:
[[QpmtnriLmax|<tex> Q \mid pmtn, r_i \mid L_{max} </tex>]]

== Жадное построение расписания ==
{{Определение
|definition=[[Теорема Радо-Эдмондса (жадный алгоритм)|'''Жадный алгоритм''']] — алгоритм решения задач путем выбора локально оптимальных решений на каждом этапе алгоритма.
}}
Естественно, далеко не все оптимизационные задачи можно решать жадно — для этого сначала необходимо доказать оптимальность жадного выбора.

С помощью этого метода решаются:
* [[Правило Лаулера|<tex> 1 \mid prec \mid f_{max} </tex>]]
* [[1outtreesumwc|<tex> 1 \mid outtree \mid \sum w_i C_i </tex>]]
* [[1pi1sumwu|<tex> 1 \mid p_i = 1 \mid \sum w_i U_i </tex>]]
* [[1sumu|<tex> 1 \mid \mid \sum U_i </tex>]]

Обычно оптимальность жадного выбора доказывают двумя способами:

=== Неправильно ===
Приведем пример часто распространенных '''неправильных''' действий при доказательстве оптимальности жадного алгоритма:

Пусть предложенным нами алгоритмом мы получили какое-то решение <tex> S </tex>. Атомарными изменениями в этом решении <tex> S </tex> будем получать другие допустимые решения <tex> S' </tex> и докажем, что <tex> f(S) \leqslant f(S') </tex>. Тогда решение <tex> S </tex> — оптимально.

Проблема в этих рассуждениях в том, что ими мы доказываем локальную оптимальность алгоритма в решении <tex> S </tex>. Получение же глобального минимума может потребовать нескольких атомарных изменений в расписании, поэтому доказать оптимальность таким образом в общем случае невозможно. Как ближайшую аналогию, можно привести '''неправильное''' утверждение для произвольной функции <tex> f(\bar x) </tex> — «если все частные производные <tex> \dfrac{\partial f}{\partial x_1} \dots \dfrac{\partial f}{\partial x_n} </tex> неотрицательны, то в точке <tex> \bar x </tex> наблюдается глобальный минимум».

=== Правильно ===
При доказательстве оптимательности применима стратегия '''аргумент замены''' (англ. ''exchange argument''). Стратегия заключается в рассмотрении текущего решения <tex> S </tex> и оптимального решения <tex> O </tex>. Далее предлагается способ модификации <tex> O </tex> в <tex> O'</tex> так, что:
# <tex> f(O') \leqslant f(O) </tex>, то есть <tex> O' </tex> также оптимально.
# <tex> O' </tex> «более похоже» на <tex> S </tex>, чем на <tex> O </tex>.

Если такой способ найден, получаем, что какой-то последовательностью модификаций <tex> O \to O_t' \to \dots \to O_1' \to S </tex> получим <tex> f(S) \leqslant f(O_1') \leqslant \dots \leqslant f(O_t') \leqslant f(O) </tex>, из чего следует оптимальность <tex> S </tex>.

Отношение «более похоже» должно быть [[Отношение порядка | отношением частичного строгого порядка]]. Часто в качестве него можно выбрать отношение «длина наибольшего общего префикса решения <tex> A </tex> и <tex> S </tex> меньше наибольшего общего префикса решения <tex> B </tex> и <tex> S </tex>». Тогда если мы сможем увеличить длину наибольшего общего префикса для оптимального решения, не нарушив оптимальности, мы приблизимся к <tex> S </tex>. Можно выбирать и более сложные отношения, например, в доказательстве оптимальности алгоритма <tex> P \mid \mid \sum w_i C_i </tex> для решения задачи <tex> P \mid pmtn \mid \sum w_i C_i </tex> используется отношение «время последнего прерывания больше или количество прерываний меньше».

== См. также. ==
* [[Правило Лаулера]]
* [[Flow shop]]
* [[Opi1sumu|<tex> O \mid p_{ij} = 1 \mid \sum U_i</tex>]]

== Примечания ==
<references/>

== Источники информации ==
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer ISBN 978-3-540-69515-8

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

Opij1Sumwc

2016-06-07T01:18:19Z

Qradimir: Скобки, см. также

<tex dpi="200">O \mid p_{ij}=1 \mid \sum w_i C_i</tex>
{{Задача
|definition = Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex> работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно 1. Необходимо минимизировать взвешенную сумму времен завершения работ.
}}
==Алгоритм==

===Описание алгоритма===
{{Утверждение
|statement=Оптимальный ответ для <tex>S = O \mid p_{ij}=1 \mid \sum w_i C_i</tex> равен оптимальному ответу к задаче <tex>S' = P \mid p_i=m, pmtn \mid \sum w_i C_i</tex>
|proof=Для доказательства этого утверждения необходимо показать то, что из оптимальности <tex> S' </tex> следует оптимальность <tex> S </tex>, и предоставить способ построения допустимого расписания для <tex> S </tex> из расписания для <tex> S' </tex>:
# Целевые функции задач совпадают, поэтому из оптимальности <tex> S' </tex> следует оптимальность <tex> S </tex>.
# Покажем, как получить из расписания <tex> S' </tex> допустимое расписание для <tex>S</tex> (в расписании для <tex>S'</tex> допустимость нарушает то, что на одном станке выполняется несколько блоков одной работы):
## Построим двудольный граф, в левую долю которого поместим работы, а в правую — возможные моменты времени. Из вершины, соответствующей работе <tex> i </tex> будет идти ребро в вершину, соответствующую временному моменту <tex> t</tex>, если работа <tex> i </tex> в расписании для <tex> S' </tex> претендует на выполнение в момент времени <tex>t</tex>.
## Раскрасим ребра этого графа в <tex>m</tex> цветов, из теории графов известно, что это можно сделать.
## Назначим выполнение единичного элемента работы <tex>i</tex> в момент времени <tex>t</tex> на станке <tex>k</tex>, если соответствующее ребро раскрашено в цвет <tex>k</tex>.
## После данного преобразования мы не изменим значение целевой функции (так как мы переставляем только элементы работ, выполняющихся в один и тот же момент времени). Также расписание станет допустимым для <tex> S </tex>, так как по определению реберной раскраски, не будет ни одной работы, два единичных блока которых выполняется на одном станке и во все моменты времени не окажется того, что на один станок назначено две работы.
}}
Чтобы непосредственно решить эту задачу, воспользуемся теоремой о том, что для задачи <tex> P \mid p_i=m, pmtn \mid \sum w_i C_i </tex> существует оптимальное расписание без прерываний<ref>P. Brucker. Scheduling Algorithms (2006), 5th edition, p. 121 </ref>. Известно, что для того, чтобы получить оптимальное расписание для такой задачи без прерываний, надо помещать работы по очереди на станки <tex>1 \dots m </tex> в порядке убывания весов. Длительности у всех работ совпадают, поэтому расписание будет состоять из <tex> \left\lfloor \dfrac{n}{m} \right\rfloor </tex> блоков по <tex> m </tex> работ и, возможно, одного неполного блока из <tex> n \bmod m </tex> работ. Таким образом, аналогично задаче <tex> O \mid p_{ij}=1 \mid C_{max}</tex>, чтобы получить допустимое расписание, можно не строить раскраску графа, а просто циклически сдвигать последовательности работ внутри каждого блока.

===Время работы===
Чтобы построить циклические сдвиги внутри одного блока требуется <tex> \mathcal{O} \left( m^2 \right) </tex> времени. Всего блоков <tex> \mathcal{O} \left( \dfrac{n}{m} \right) </tex>.
Значит, итоговая ассимптотика равна <tex> \mathcal{O}(n \cdot m) </tex>.

==См. также.==
* [[Методы решения задач теории расписаний]]
* [[1outtreesumwc|<tex> 1 \mid outtree \mid \sum w_i C_i </tex>]]
* [[1ripi1sumwc|<tex> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex>]]
* [[RSumCi|<tex> R \mid \mid \sum C_i </tex>]]

==Примечания==
<references/>

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

Opij1Cmax

2016-06-07T01:04:13Z

Qradimir: Вики-таблица, см. также

<tex dpi = "200">O \mid p_{ij} = 1 \mid C_{max}</tex>
{{Задача
|definition = Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex> работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно 1. Необходимо минимизировать время выполнения всех работ.
}}
==Алгоритм==

===Описание алгоритма===
Минимальное значение <tex> C_{max} </tex> упирается в следующие ограничения:
# В допустимом расписании на каждом станке надо обработать каждую работу, поэтому <tex> C_{max} \geqslant n </tex>.
# В допустимом расписании каждую работу нужно обработать на всех станках, причем ее нельзя обрабатывать на двух станках одновременно, поэтому <tex> C_{max} \geqslant m </tex>.
Тогда <tex> C_{max} = \max{(m, n)} </tex>.

В случае <tex> n \geqslant m </tex> оптимальное расписание строится циклическими сдвигами последовательности <tex> 1 \dots n </tex> и выглядит следующим образом:
{| class="wikitable"
|-
!
!| 1 || 2 || 3 ||<tex>\hdots</tex>|| n - 1 || n
|- style="text-align:center;"
!<tex>M_1</tex>
|| 1 || 2 || 3 ||<tex>\hdots</tex>|| n - 1 || n
|- style="text-align:center;"
!<tex>M_2</tex>
|| n || 1 || 2 ||<tex>\hdots</tex>|| n - 2 || n - 1
|- style="text-align:center;"
!<tex>M_3</tex>
|| n - 1 || n || 1 ||<tex>\hdots</tex>|| n - 3 || n - 2
|- style="text-align:center;"
!<tex>\vdots</tex>
||<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\ddots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>
|- style="text-align:center;"
!<tex>M_m</tex>
|| n - m + 2 || n - m + 3 || n - m + 4 ||<tex>\hdots</tex>|| n - m ||n - m + 1
|}

Если же <tex> n < m </tex>, добавим <tex> m - n </tex> фиктивных работ с номерами <tex> n + 1 \dots m </tex>, построим расписание способом выше и удалим из полученного расписания фиктивные работы.

===Оценка сложности алгоритма===
Минимальное значение <tex> C_{max} </tex> вычисляется за <tex> \mathcal{O}(1) </tex> времени.
Построение расписания сводится к заполнению матрицы размером <tex> m \times \max{(m, n)} </tex> и выполняется за <tex> \mathcal{O}(m \dot (m + n)) </tex> времени.

==См. также.==
* [[Методы решения задач теории расписаний]]
* [[O2Cmax|<tex> O2 \mid \mid C_{max} </tex>]]
* [[QpmtnCmax|<tex> Q \mid pmtn \mid C_{max} </tex>]]
* [[Opij1Sumwc|<tex> O \mid p_{ij} = 1 \mid \sum w_i C_i </tex>]]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

RSumCi

2016-06-06T23:55:46Z

Qradimir: Фиксы

<tex dpi="200">R \mid \mid \sum C_i</tex>
{{Задача
|definition=Дано <tex> n </tex> работ и <tex> m </tex> станков, причем для каждого станка длительность выполнения на нем <tex>i</tex>-й работы составляет <tex> p_{ij} </tex>. Необходимо минимизировать сумму времени выполнения работ.
}}
==Алгоритм==

===Описание алгоритма===
Рассмотрим произвольное допустимое расписание для этой задачи. Рассмотрим какую-то станок <tex> j </tex>, пусть на нем выполняется <tex>n_j</tex> работ. Тогда вклад этого станка в целевую функцию (не теряя общности, пронумеруем работы на этом станке от <tex>1 </tex> до <tex>n_j</tex>) рассчитывается как:

<tex>
\sum\limits_{i=1}^{n_j} \left( p_ij + \sum\limits_{q=1}^{i-1} p_qj \right) =
n_j p_{1j} + (n_j - 1) p_{2j} + \dots + 2 p_{(n_j-1)j} + p_{n_jj}
</tex>

Заметим, что в каждом допустимом расписании перед каждой работой окажется коэффициент <tex> k </tex>, означающий, что соответствующая работа выпллняется <tex> k </tex>-й с конца. Понятно, что в различных расписаниях <tex> k </tex> может принимать значения от <tex>1</tex> до <tex>n</tex>.

Сведем задачу к назначению каждой работы <tex> i </tex> позиции с конца <tex> k </tex> на станке <tex> j </tex> с помощью алгоритма [[Поток минимальной стоимости | поиска максимального потока минимальной стоимости]]. Поместим в левую долю графа работы, в правую долю — пары из станка и коэффициента и проведем соответствующие ребра пропускной способности <tex>1</tex> и стоимости <tex>k \cdot p_{ij}</tex>, соответствующие вкладу работы в целевую функцию, если она окажется в позиции <tex> k </tex> с конца на станке <tex> j </tex>. Проведем из стока в левую долю ребра стоимости <tex>0</tex> и пропускной способности <tex>1</tex>, из правой доли в сток — также ребра стоимости <tex> 0 </tex> и пропускной способности <tex>1</tex>. Максимальный поток минимальной стоймости в построенной сети будет ответом на исходную задачу.
{{Утверждение
|statement=Eсли ребро <tex> i \to (j, k) </tex> насыщено потоком, то работа <tex> i </tex> в оптимальном расписании должна стоять на станке <tex> j </tex> в позиции <tex> k </tex> с конца.
|proof=
# Целевя функция текущей задачи совпадает со стомостью максимального потока в построенной сети, так как у ребер между долями пропускная способность 1, а у дополнительных ребер из истока и в сток нулевая стоимость, и они не могут внести вклад в целевую функцию.
# Расписание, построенное по вышепредставленному способу действительно будет допустимым.
## Благодаря ограничениям на поток, входящий в левую долю, каждая работа будет назначена только один раз.
## Благодаря ограничениям на поток, выходящий из правой доли, на каждую позицию будет назначено не более одной работы.
## Докажем, что не возникает ситуации такой, что существует такая позиция <tex> l </tex>, что в этой позиции с конца стоит какая-то работа, а в позиции <tex> l - 1 </tex> с конца — нет (это противоречит определению <tex>l</tex>-й с конца работы). Такая ситуация означает, что ребро <tex> i \to (j, l) </tex> оказалось насышено потоком, а ребро <tex>i \to (j, l - 1) </tex> — не насыщено. Но стоимость ребра <tex> i \to (j, l - 1) </tex> меньше стоимости ребра <tex> i \to (j, l) </tex>, поэтому можем переместить поток с ребра <tex> i \to (j, l) </tex> на ребро <tex> i \to (j, l - 1) </tex>, не нарушив свойства потока и улучшив целевую функцию, что противоречит оптимальности ответа для mincost-maxflow. Следовательно, такой позиции не возникнет и расписание будет допустимым.
}}

===Время выполнения===
Время выполнения алгоритма поиска максимального потока минимальной стоймости равно <tex> \mathcal{O}(V \cdot E^2) </tex>. Количество вершин в получаемой сети равно <tex> \mathcal{O}(m \cdot n) </tex>. Количество ребер в сети равно <tex> \mathcal{O}(m \cdot n^2) </tex>. Следовательно, ассимптотика алгоритма равна <tex> \mathcal{O}(m^3 \cdot n^5) </tex>.

==См. также==
* [[Поток минимальной стоимости]]
* [[Методы решения задач теории расписаний]]
* [[PSumCi|<tex>P \mid \mid \sum C_i</tex>]]
* [[QSumCi|<tex>Q \mid \mid \sum C_i</tex>]]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

1outtreesumwc

2016-06-06T23:29:04Z

Qradimir: 1 | intree | Sum(w*C) - наводим красоту

<tex dpi = "200" >1 \mid outtree \mid \sum w_i C_i</tex>

{{Задача
|definition=
Необходимо составить расписание на одном станке работ с произвольными временами выполнения. Минимизировать нужно взвешенную сумму времен завершения работ. Зависимости между работами заданы исходящим [[Дерево, эквивалентные определения | деревом]] {{---}} работа, которая соответствует корню, доступна в начале, все другие работы зависят от одной работы {{---}} отца в дереве.
}}
Тривиальным примером подобной задачи является демонтаж сложного механизма.

== Свойства оптимального расписания ==

Докажем некоторые свойства оптимального расписания, которые мы будем использовать в доказательстве корректности алгоритма.

Введем некоторые обозначения для удобства. За <tex>\mathrm{edges} </tex> обозначим список всех ребёр дерева. Для всех работ <tex>i = 1, \ldots, n</tex> обозначим за <tex>S(i)</tex> всех потомков <tex>i</tex> в дереве зависимостей, включая саму работу <tex>i</tex>, введём новый параметр работы <tex>q_i = \dfrac{w_i}{p_i}</tex>.

Для подмножества работ <tex>I \subseteq \{1, \ldots, n\}</tex> определим:

<tex>w(I) = \sum\limits_{i \in I} w_i, p(I) = \sum\limits_{i \in I} p_i, q(I) = \dfrac{w(I)}{p(I)}</tex>

Два непересекающихся множества работ <tex>I, J \subseteq \{1, \ldots, n\}</tex> будем называть '''параллельными''' <tex>(I \sim J)</tex>, если для всех <tex>i \in I, j \in J</tex> выполняется: <tex>i</tex> не является ни предком, ни потомком <tex>j</tex>. Если множества состоят из одной работы <tex>I = \{i\},\ J = \{j\}</tex>, будем писать <tex>i \sim j</tex>. Каждое расписание представлено перестановкой <tex>\pi</tex>.

{{Лемма
|id=lemma1
|statement= Пусть <tex>\pi</tex> {{---}} оптимальное расписание, <tex>I</tex> и <tex>J</tex> {{---}} два таких параллельных блока (множества работ, выполняемых последовательно) из <tex>\pi</tex>, что <tex>J</tex> выполняется сразу после <tex>I</tex>. Пусть <tex>\pi'</tex> {{---}} расписание, полученное из <tex>\pi</tex> перестановкой <tex>I</tex> и <tex>J</tex>. Тогда выполяются следующие пункты:
:<tex>(a)~ I \sim J \Rightarrow q(I) \geqslant q(J)</tex>
:<tex>(b)</tex> Если <tex>I \sim J</tex> и <tex>q(I) = q(J)</tex>, то <tex>\pi'</tex> {{---}} оптимальное расписание.
|proof=
<tex>(a)</tex>

:Пусть <tex>f = \sum w_i C_i</tex>. Так как <tex>\pi</tex> {{---}} оптимальное расписание, то <tex>f(\pi) \leqslant f(\pi')</tex>. Таким образом:

:<tex>0 \leqslant f(\pi') - f(\pi) = w(I) p(J) - w(J) p(I)</tex>

:Поделим на <tex>p(I)p(J)</tex>:

:<tex>q(I) = \dfrac{w(I)}{p(I)} \geqslant \dfrac{w(J)}{p(J)} = q(J) </tex>

<tex>(b)</tex>

:Если <tex>q(I) = q(J) </tex>, то <tex>f(\pi) = f(\pi') </tex>, следовательно расписание <tex>\pi'</tex> оптимально.
}}

{{Теорема
|id = theorem1
|statement = Пусть <tex>i, ~j</tex> работы такие, что <tex>i</tex> {{---}} предок <tex>j</tex>, и <tex> q_j = \max \{q_k \mid ~ (i, k) \in \mathrm{edges} \}</tex>. 
Тогда существует оптимальное расписание, в котором работа <tex>j</tex> идёт сразу после работы <tex>i</tex>
|proof =
Каждое расписание может быть представлено последовательностью работ в порядке, в котором они выполняются. Пусть <tex> \pi </tex> будет оптимальной такой последовательностью. Также предположим, что количество работ между <tex> i </tex> и <tex> j </tex> равное <tex> l </tex> было бы минимальным. Можно считать, что <tex> l > 0 </tex>. Тогда расписание можно представить следующим образом:

[[Файл:JobBlock.jpg]]

Рассмотрим <tex>2</tex> случая.

'''Случай 1''': <tex> k \in S(i) </tex>

:Работа <tex> j </tex> не является потомком работы <tex> k </tex> , иначе у неё было бы <tex>2</tex> предка. Следовательно, <tex> k \sim j </tex>. По [[#lemma1 | лемме]] <tex> q(k) \geqslant q(j) </tex>, а по условию выбора <tex> j </tex> имеем <tex> q(j) \geqslant q(k) </tex>, значит, <tex> q(j) = q(k) </tex>. Опять же из [[#lemma1 | леммы]] следует, что работы <tex> k </tex> и <tex> j </tex> можно поменять местами, не ухудшив расписание. Это противоречит тому, что мы выбрали минимальное <tex> l </tex>.

'''Случай 2''': <tex> k \not\in S(i) </tex>

:Пусть <tex> h </tex> будет последней работой в расписании между <tex> i </tex> и <tex> j\ ( </tex>включая работу <tex> i) </tex>, которая принадлежит <tex> S(i) </tex>, то есть для всех работ <tex> r </tex> в множестве <tex> K </tex>, назначенных между <tex> h </tex> и <tex> j </tex>, имеем, что <tex> r \not\in S(i) </tex>. Так как наш [[Основные определения теории графов | граф]] зависимостей работ является исходящим деревом и <tex>(i, j) \in \mathrm{edges} </tex>, то любой предок работы <tex> j </tex> также является и предком работы <tex> i </tex>. Поэтому никакая работа из <tex> K </tex> не является предком <tex> j\ (</tex>иначе бы она не смогла стоять после <tex> i) </tex> или потомком, значит, <tex> K \sim j </tex>. Из этого следует, что <tex> q(K) \geqslant q(j) </tex>.

:Работа <tex> h \in S(i) </tex> не является потомком какой-либо работы <tex> r \in K </tex>. В противном же случае получалось, что <tex> r \in S(i) </tex>, значит, <tex> h </tex> является не последней работой из <tex> S(i) </tex> между <tex> i </tex> и <tex> j </tex>. Поэтому <tex> h \sim K </tex>, откуда тут же следует, что <tex> q(h) \geqslant q(K) \geqslant q(j) </tex>. По определению <tex> j </tex> имеем, что <tex> q(j) \geqslant q(h) </tex>, следовательно <tex> q(j) = q(h) = q(K) </tex>. По [[#lemma1 | лемме]] мы можем поменять блоки <tex> K </tex> и <tex> j </tex> не нарушив оптимальности расписания.

Таким образом мы можем менять соседние работы или блоки работ, пока <tex> j </tex> не окажется сразу за <tex> i </tex>.
}}

== Алгоритм ==
Доказанная в предыдущем пункте [[#theorem1 | теорема]] уже даёт основную идею алгоритма: взять работу <tex> j </tex>, отличную от корня дерева, с максимальным значением <tex> q_j </tex> и поставить её в расписании сразу после своего непосредственного предка <tex> i </tex>. Так как существует оптимальное расписание, в котором работа <tex> j </tex> идёт сразу после <tex> i </tex>, то мы можем объедить вершины графа в одну вершину <tex> J_i = \{i, j\}</tex>, которая представляет собой последовательность <tex> \pi_i \colon i, j </tex>. Все сыновья работы <tex> j </tex> станут сыновьями новой вершины <tex> J_i </tex>.

Будем повторять процесс слияния вершин, пока не останется всего одна вершина.

Таким образом каждая вершина <tex> i </tex> представляется множеством работ <tex> J_i </tex> и соответствующей этому множеству последовательностью <tex> \pi_i </tex>. На очередном шаге алгоритма мы находим вершину <tex> j </tex>, отличную от корня, с максимальным значением <tex> q_j </tex>. Пусть <tex> par </tex> {{---}} непосредственный предок работы <tex> j </tex>. Тогда нам надо найти такую вершину <tex> i </tex>, что <tex> par \in J_i </tex>. После этого мы объединяем обе вершины, заменяя <tex> J_i </tex> и <tex> \pi_i </tex> на <tex> J_i \cup J_j </tex> и <tex> \pi_i \circ \pi_j </tex>, где <tex> \pi_i \circ \pi_j </tex> {{---}} это конкатенация последовательностей <tex> \pi_i </tex> и <tex> \pi_j </tex>.

Детали описаны в алгоритме ниже, в котором
* <tex> E(i) </tex> обозначает последнюю работу в последовательности <tex> \pi_i </tex>,
* <tex> P(i) </tex> обозначает предка в графе зависимостей, а после слияния с какой-то вершиной <tex> j </tex> {{---}} предыдущую работу в последовательности <tex> \pi_j </tex>.

w[root] = <tex> - \infty </tex>
'''for''' i = 1..n
E[i] = {i}
J[i] = {i}
q[i] = w[i] \ p[i]
L = {1, ... , n}
'''while''' L <tex> \ne </tex> {root} // пока в списке работ не останется только корень
Найти работу j <tex> \in </tex> L с маскимальным значением q[j]
par = P[j]
Найти i, что par <tex> \in </tex> J[i]
w[i] += w[j]
p[i] += p[j]
q[i] = w[i] / w[j] // пересчитаем значения в вершине
P[j] = E[i] // предком работы j теперь будет последняя работа в <tex> \pi_i </tex>
E[i] = E[j] // последней работой в <tex> \pi_i </tex> теперь будет последняя работа в <tex> \pi_j </tex>
J[i] = J[i] <tex> \cup </tex> J[j]
L = L \ {j}
Вначале делаем присваивание <tex> w(root) = -\infty </tex>, чтобы корень никогда не выбрался на шаге выбора вершины с максимальным значением <tex> q </tex>. В реализации же можно просто дополнительно проверять на равенство с корнем, чтобы избежать переполнений или испортить значение <tex>-\infty</tex>.

После завершения этой процедуры оптимальное расписание можно восстановить с конца, зная <tex> E(root) </tex> и массив <tex> P </tex>.

Если для получения работы <tex> j </tex> с минимальным значением <tex> q(j) </tex> использовать очередь с приоритетами, а для поиска родителям вершины использовать систему непересекающихся множеств, то время работы алгоритма будет <tex> \mathcal{O}(n\log{n}) </tex>.

Проиллюстрируем работу алгоритма на следующем примере.

[[Файл:JobsOuttrees.jpg|650px]]

Первой выберется работа с номером <tex> 5 </tex>. Она объединиться со своим родителем <tex> 2 </tex> и допишется в конец <tex> \pi_2 </tex>. Потом выберется работа <tex> 4 </tex>, потом <tex> \{2, 5\} </tex> и т. д. Процесс будет продолжаться, пока не останется одна вершина. Ответ {{---}} оптимальная последовательность работ {{---}} содержится в <tex> \pi_1 </tex>, который написан внутри последней вершины.

== Доказательство оптимальности алгоритма ==
{{Теорема
|id = theorem2
|statement = Алгоритм <tex> 1 \mid outtree \mid \sum w_i C_i</tex> строит оптимальное расписание.
|proof =
Доказательство проведём по индукции. Очевидно, что для одной вершины алгоритм построит оптимальное расписание. Пусть теперь он может составить оптимальную последовательность назначенных работ числом меньше <tex> n </tex>. Пусть также работы <tex> i, j </tex> {{---}} работы, которые объединятся на первом шаге алгоритма. Тогда оптимальное расписание <tex> R </tex> можно представить следующим образом:

<tex> \pi \colon \pi (1), \ldots, \pi (k), i, j, \pi (k + 3), \ldots, \pi (n) </tex>

После объединения работ <tex> i </tex> и <tex> j </tex> в одну расписание <tex> R' </tex> примет такой вид:

<tex> \pi ' \colon \pi (1), \ldots, \pi (k), I, \pi (k + 3), \ldots, \pi (n) </tex>

где <tex> I = \{i, j\}, ~w(I) = w(i) + w(j), p(I) = p(i) + p(j)</tex>. Обозначим за <tex> f_n(\pi ), ~f_{n-1}(\pi ') </tex> целевые функции для последовательностей <tex> \pi </tex> и <tex> \pi ' </tex> соответственно. Тогда

<tex> f_n(\pi ) - f_{n-1}(\pi') = w(i)p(i) + w(j)(p(i) + p(j)) - (w(i) + w(j))(p(i) + p(j)) = -w(i) p(j)\ (*) </tex>

Следовательно, расписание <tex> R </tex> будет оптимальным тогда и только тогда, когда расписание <tex> R' </tex> будет оптимальным. А по предположению индукции наш алгоритм составит оптимальное расписание для последовательности <tex> \pi ' </tex>.

Теперь разделим обе части равенства <tex> (*) </tex> на <tex> w(i)w(j) </tex>. Получим, что расстояние между целевыми функциями равно

<tex> -\dfrac{p(j)}{w(j)} = -\dfrac{1}{q(j)} </tex>

Это расстояние минимально (по модулю), так как мы выбирали работу <tex> j </tex> с максимальным значением <tex> q(j) </tex>. Из этих утверждений и следует оптимальность построенного алгоритмом расписания.
}}

== 1 | intree | Sum(w*C)==
<tex dpi="200"> 1 \mid intree \mid \sum w_i C_i </tex>
{{Задача
|definition=
Необходимо составить расписание на одном станке работ с произвольными временами выполнения. Минимизировать нужно взвешенную сумму времен завершения работ. Зависимости между работами заданы [[Дерево, эквивалентные определения | деревом]], в котором листья {{---}} работы, которые доступны в начале, а все остальные работы недоступны пока все их дети не будут выполнены.
}}
Сведем задачу <tex> S_{in} = 1 \mid intree \mid \sum w_i C_i </tex> к решенной задаче <tex>S_{out} = 1 \mid outtree \mid \sum w_i C_i </tex> следующим образом:
# Развернем все ребра: если работа <tex> i </tex> зависела от работы <tex> j </tex>, теперь работа <tex> j </tex> будет зависеть от <tex> i </tex>.
# Заменим все стоимости <tex> w_i </tex> на противоположные <tex> w'_i = - w_i</tex>.
{{Теорема
|statement=Развернутое оптимальное расписание соответствующей задачи <tex> S_{out} </tex> с весами <tex> w'_i </tex> является оптимальным расписанием для задачи <tex> S_{in} </tex>
|proof=
Полученное расписание будет допустимым, так как расписание для <tex> S_{out} </tex> было допустимым, и в нем никакие две работы не пересекались и не прерывались. Развернув ребра, мы не могли нарушить это свойство. Также из-за того, что мы развернули ребра в расписании, мы добились того, что все работы выполняются в правильном порядке (в расписании для <tex> S_{out} </tex> из-за того, что все ребра были развернуты, порядок был нарушен для всех работ). Таким образом получили, что расписание допустимое.

Пусть с помощью задачи <tex> S_{out} </tex> мы получили последовательность работ <tex> 1 \dots n </tex>. Распишем по определению значение целевой функции для <tex> S_{out} </tex>:
<tex>
\sum\limits_{i=1}^n \left( -w_i C_i \right)
= \sum \limits_{i=1}^n \left( -w_i \sum \limits_{j=1}^i p_j \right) = \\
= \sum\limits_{i=1}^n \left( w_i \sum\limits_{j=i+1}^n p_j \right)
- \sum\limits_{i=1}^n w_i \sum \limits_{i=1}^n p_i = \\
= \sum\limits_{i=1}^n \left( w_i \sum\limits_{j=i}^n p_j \right)
- \sum\limits_{i=1}^n w_i p_i
- \sum\limits_{i=1}^n w_i \sum \limits_{i=1}^n p_i
</tex>
Заметим, что первое слагаемое соответствует целевой функции <tex> \sum w_i C_i </tex> для последовательности <tex> n \dots 1 </tex>, а второе и третье слагаемые — константы, зависящие только от входных данных и не зависящие от перестановки работ. Таким образом, оптимальное значение для <tex> S_{out} </tex> также минимизирует <tex> S_{in} </tex>.
}}

== Источники информации ==
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 73 - 78

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

RSumCi

2016-06-06T09:38:47Z

Qradimir: /* Время выполнения */

<tex dpi="200">R \mid \mid \sum C_i</tex>
{{Задача
|definition=Дано <tex> n </tex> работ и <tex> m </tex> станков, причем для каждого станка длительность выполнения на нем <tex>i</tex>-й работы своя и равна <tex> p_{ij} </tex>. Необходимо минимизировать сумму времени выполнения работ.
}}
==Алгоритм==

===Описание алгоритма===
Рассмотрим произвольное допустимое расписание для этой задачи. Рассмотрим какую-то станок <tex> j </tex>, пусть на нем выполняется <tex>n_j</tex> работ. Тогда вклад этого станка в целевую функцию (не теряя общности, пронумеруем работы на этом станке от <tex>1 </tex> до <tex>n_j</tex>) рассчитывается как:

<tex> \sum\limits_{i=1}^{n_j} (p_ij + \sum\limits_{q=1}^{i-1} p_qj) = n_j p_{1j} + (n_j - 1) p_{2j} + \dots + 2 p_{(n_j-1)j} + p_{n_jj} </tex>

Заметим, что в каждом допустимом расписании перед каждой работой окажется коэффициент <tex> k </tex>, означающий, что соответствующая работа выпллняется <tex> k </tex>-й с конца. Понятно, что в различных расписаниях <tex> k </tex> может принимать значения от <tex>1</tex> до <tex>n</tex>.

Сведем задачу к назначению каждой работы <tex> i </tex> позиции с конца <tex> k </tex> на станке <tex> j </tex> с помощью задачи [[Поток минимальной стоимости | mincost-maxflow]]. Поместим в левую долю графа работы, в правую долю — пары из станка и коэффициента и проведем соответствующие ребра пропускной способности <tex>1</tex> и стоимости <tex>k p_{ij}</tex>, соответствующие вкладу работы в целевую функцию, если она окажется в позиции <tex> k </tex> с конца на станке <tex> j </tex>. Проведем из стока в левую долю ребра стоимости <tex>0</tex> и пропускной способности <tex>1</tex>, из правой доли в сток — также ребра стоимости <tex> 0 </tex> и пропускной способности <tex>1</tex>. Максимальный поток минимальной стоймости в построенной сети будет ответом на исходную задачу.
{{Утверждение
|statement=Eсли ребро <tex> i \to (j, k) </tex> насыщено потоком, то работа <tex> i </tex> в оптимальном расписании должна стоять на станке <tex> j </tex> в позиции <tex> k </tex> с конца.
|proof=
# Целевые функции задачи mincost-maxflow и текущей задачи совпадают, так как у ребер между долями пропускная способность 1, а у дополнительных ребер из истока и в сток нулевая стоимость, и они не могут внести вклад в целевую функцию.
# Расписание, построенное по вышепредставленному способу действительно будет допустимым.
## Благодаря ограничениям на поток, входящий в левую долю, каждая работа будет назначена только один раз.
## Благодаря ограничениям на поток, выходящий из правой доли, на каждую позицию будет назначено не более одной работы.
## Докажем, что не возникает ситуации такой, что существует такая позиция <tex> l </tex>, что в этой позиции с конца стоит какая-то работа, а в позиции <tex> l - 1 </tex> с конца — нет (это противоречит определению <tex>l</tex>-й с конца работы). Такая ситуация означает, что ребро <tex> i \to (j, l) </tex> оказалось насышено потоком, а ребро <tex>i \to (j, l - 1) </tex> — не насыщено. Но стоимость ребра <tex> i \to (j, l - 1) </tex> меньше стоимости ребра <tex> i \to (j, l) </tex>, поэтому можем переместить поток с ребра <tex> i \to (j, l) </tex> на ребро <tex> i \to (j, l - 1) </tex>, не нарушив свойства потока и улучшив целевую функцию, что противоречит оптимальности ответа для mincost-maxflow. Следовательно, такой позиции не возникнет и расписание будет допустимым.
}}

===Время выполнения===
Время выполнения mincost-maxflow равно <tex> \mathcal{O}(V \cdot E^2) </tex>. Количество вершин в получаемой сети равно <tex> \mathcal{O}(m \cdot n) </tex>. Количество ребер в сети равно <tex> \mathcal{O}(m \cdot n^2) </tex>. Следственно, ассимптотика алгоритма равна <tex> \mathcal{O}(m^3 \cdot n^5) </tex>.

==См. также==
* [[Поток минимальной стоимости]]
* [[Методы решения задач теории расписаний]]

Opij1Sumwc

2016-06-06T09:37:00Z

Qradimir:

<tex dpi="200">O \mid p_{ij}=1 \mid \sum w_i C_i</tex>
{{Задача
|definition = Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex> работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно 1. Необходимо минимизировать взвешенную сумму времен завершения работ.
}}
==Алгоритм==

===Описание алгоритма===
{{Утверждение
|statement=Оптимальный ответ для <tex>S = O \mid p_{ij}=1 \mid \sum w_i C_i</tex> равен оптимальному ответу к задаче <tex>S' = P \mid p_i=m, pmtn \mid \sum w_i C_i</tex>
|proof=Для доказательства этого утверждения необходимо показать то, что из оптимальности <tex> S' </tex> следует оптимальность <tex> S </tex>, и способ построения допустимого расписания для <tex> S </tex> из расписания для <tex> S' </tex>:
# Целевые функции задач совпадают, поэтому из оптимальности <tex> S' </tex> следует оптимальность <tex> S </tex>.
# Покажем, как получить из расписания <tex> S' </tex> допустимое расписание для <tex>S</tex> (в расписании для <tex>S'</tex> допустимость нарушает то, что на одном станке выполняется несколько блоков одной работы):
## Построим двудольный граф, в левую долю которого поместим работы, а в правую — возможные моменты времени. Из вершины, соответствующей работе <tex> i </tex> будет идти ребро в вершину, соответствующую временному моменту <tex> t</tex>, если работа <tex> i </tex> в расписании для <tex> S' </tex> претендует на выполнение в момент времени <tex>t</tex>.
## Раскрасим ребра этого графа в <tex>m</tex> цветов, из теории графов известно, что это можно сделать.
## Назначим выполнение единичного элемента работы <tex>i</tex> в момент времени <tex>t</tex> на станке <tex>k</tex>, если соответствующее ребро раскрашено в цвет <tex>k</tex>.
## После данного преобразования мы не изменим значение целевой функции (так как мы переставляем только элементы работ, выполняющихся в один и тот же момент времени). Также расписание станет допустимым для <tex> S </tex>, так как по определению реберной раскраски, не будет ни одной работы, два единичных блока которых выполняется на одном станке и во все моменты времени не окажется того, что на один станок назначено две работы.
}}
Чтобы непосредственно решить эту задачу, воспользуемся теоремой о том, что для задачи <tex> P \mid p_i=m, pmtn \mid \sum w_i C_i </tex> существует оптимальное расписание без прерываний<ref>P. Brucker. Scheduling Algorithms (2006), 5th edition, p. 121 </ref>. Известно, что для того, чтобы получить оптимальное расписание для такой задачи без прерываний, надо помещать работы по очереди на станки <tex>1 \dots m </tex> в порядке убывания весов. Длительности у всех работ совпадают, поэтому расписание будет состоять из <tex> \lfloor \frac{n}{m} \rfloor </tex> блоков по <tex> m </tex> работ и, возможно, одного неполного блока из <tex> n \bmod m </tex> работ. Таким образом, аналогично задаче <tex> O \mid p_{ij}=1 \mid C_{max}</tex>, чтобы получить допустимое расписание, можно не строить раскраску графа, а просто циклически сдвигать последовательности работ внутри каждого блока.

===Время работы===
Чтобы построить циклические сдвиги внутри одного блока требуется <tex> \mathcal{O}(m^2) </tex> времени. Всего блоков <tex> \mathcal{O}(\frac{n}{m}) </tex>.
Значит, итоговая ассимптотика равна <tex> \mathcal{O}(n \cdot m) </tex>.

==См. также.==
* [[Методы решения задач теории расписаний]]

==Примечания==
<references/>

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

Opij1Cmax

2016-06-06T09:35:00Z

Qradimir:

<tex dpi = "200">O \mid p_{ij} = 1 \mid C_{max}</tex>
{{Задача
|definition = Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex> работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно 1. Необходимо минимизировать время выполнения всех работ.
}}
==Алгоритм==

===Описание алгоритма===
Минимальное значение <tex> T_{min} </tex> минимизуруемой функции упирается в следующие ограничения:
# В допустимом расписании на каждом станке надо обработать каждую работу, поэтому <tex> T_{min} \geqslant n </tex>.
# В допустимом расписании каждую работу нужно обработать на всех станках, причем ее нельзя обрабатывать на двух станках одновременно, поэтому <tex> T_{min} \geqslant m </tex>.
Тогда <tex> T_{min} = \max{(m, n)} </tex>.

В случае <tex> n \geqslant m </tex> оптимальное расписание циклическими сдвигами последовательности <tex> 1 \dots n </tex> и выглядит следующим образом:
'''1 2 3 ... k k+1 ... n-1 n'''
'''M_1''' 1 2 3 ... k k+1 ... n-1 n
'''M_2''' n 1 2 ... k-1 k ... n-2 n-1
'''.''' ... ... ... ... ... ... ... ... ...
'''.''' ... ... ... ... ... ... ... ... ...
'''M_m''' n-m+2 n-m+3 ... ... ... ... ... n-m n-m+1

Если же <tex> n < m </tex>, добавим <tex> m - n </tex> фиктивных работ с номерами <tex> n + 1 \dots m </tex>, построим расписание способом выше и удалим из полученного расписания фиктивные работы.

===Оценка сложности алгоритма===
Минимальное значение <tex> C_{max} </tex> вычисляется за <tex> \mathcal{O}(1) </tex> времени.
Построение расписания сводится к заполнению матрицы размером <tex> m \times \max{(m, n)} </tex> и выполняется за <tex> \mathcal{O}(m \dot (m + n)) </tex> времени.

==См. также.==
* [[Методы решения задач теории расписаний]]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

Методы решения задач теории расписаний

2016-06-06T09:31:55Z

Qradimir: Выделены задачи в конспекты, добавлены ссылки, разделы в конце конспекта

== Сведение к другой задаче ==
При сведении текущей задачи теории расписаний <tex> S </tex> к какой-то другой <tex> S' </tex>(не обязательно задаче теории расписаний) необходимо доказать два пункта:
# Допустимость расписания, построенного с помощью задачи <tex> S' </tex>, или существование способа его трансформации в допустимое без нарушения оптимальности.
# Следствие того, что если мы оптимизируем <tex> S' </tex>, мы также оптимизируем ответ для <tex> S </tex>.
Примечание — если требуется полиномиальное время для решения задачи, требуется, чтобы сведение к другой задаче и трансформация расписания в допустимое также происходили за полиномиальное время.

С помощью этого метода решаются:
* Некоторые задачи класса Open Shop при условии <tex>p_{ij}=1</tex> сводятся к задачам равной длительности на параллельных станках.
** <tex> O \mid p_{ij} = 1 \mid \sum w_i C_i </tex> ([[Opij1Sumwc|ссылка]])
** <tex> O \mid p_{ij} = 1, r_i \mid C_{max} </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 161</ref>
* Некоторые задачи класса Flow Shop при условии <tex>p_{ij}=1</tex> сводятся к задаче на одном станке.
** <tex> F \mid p_{ij} = 1 \mid \sum w_i U_i </tex> ([[Fpij1sumwu|ссылка]])
* Часто в задачах, в которых допускаются прерывания, оптимальный ответ совпадает с соответствующими задачами без прерываний:
** <tex> P \mid pmtn \mid \sum w_i C_i </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 121</ref>
** <tex> F2 \mid pmtn \mid C_{max} </tex> ([[Flow_shop|ссылка]])
* Некоторые задачи проверки существования расписания сводятся к задаче поиска максимального потока:
** <tex> Q \mid pmtn, r_i\mid L_{max} </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 129-133</ref>
** <tex> R \mid \mid \sum C_i </tex> ([[RSumCi|ссылка]])
* <tex> 1 \mid intree \mid \sum w_i C_i </tex> ([[1outtreesumwc|ссылка]])

== Построение расписания по нижней оценке ==
Этот метод обычно применим к задачам, в которых целевая функция — <tex> C_{max}</tex>. Построим какой-то набор нижних ограничений на произвольное расписание для задачи <tex> S </tex> и возьмем из них максимальное. Затем построим произвольное допустимое расписание, достигающее этой оценки.

С помощью этого метода решаются:
* <tex> P \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 108</ref>
* <tex> R \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 137-139</ref>
* <tex> O \mid p_{ij}=1 \mid C_{max}</tex> ([[Opij1Cmax|ссылка]])
* <tex> Q \mid pmtn \mid C_{max}</tex> ([[QpmtnCmax|ссылка]])

=== P | pmtn | C_max ===
# В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому <tex> T \ge p_i </tex>.
# Если все станки работали время <tex> T </tex>, на них могло выполниться не больше <tex> Tm </tex> работы, то есть <tex> \sum\limits_i p_i \le Tm </tex> и <tex> T \ge \frac1m \sum\limits_i p_i </tex>.
# Тогда <tex> T_{min} = \max {(\max\limits_i p_i, \frac1m \sum\limits_i p_i)} </tex>.
Построим расписание, подходящее под эту границу: будем по очереди заполнять машины работами в произвольном порядке, и если очередная работа не помещается на текущей машине полностью, перенесем ее выходящую за <tex> T_{min} </tex> часть на следующую машину. Благодаря первому ограничению никакая работа не будет выполняться одновременно на двух станках, а благодаря второму — не останется работы, которую мы не сможем выполнить.

== Бинарный поиск по ответу ==
Этот способ часто подходит для задач, в которых надо минимизировать <tex>C_{max} </tex> (если мы умеем решать соответствующую задачу существования расписания), реже для <tex> \sum w_i U_i </tex>. Важно помнить, что если требуется полиномиальное по <tex> n </tex> решение, оно не должно зависеть от логарифма ответа, но иногда ответ ограничен полиномом от <tex>n</tex>, и мы можем применить этот метод.

Этим методом решаются:
* <tex> Q \mid pmtn, r_i \mid L_{max} </tex> ([[QpmtnriLmax |ссылка]])

== Жадное построение расписания ==
{{Определение
|definition=
'''Жадный алгоритм''' — алгоритм, в котором локальные оптимизации решения достигают глобального оптимума.
}}

Естественно, далеко не все оптимизационные задачи можно решать жадно — для этого сначала необходимо доказать оптимальность жадного выбора.

С помощью этого метода решаются:
* <tex> 1 \mid prec \mid f_{max} </tex> ([[Правило Лаулера|''Lawler's algorithm]])
* <tex> 1 \mid outtree \mid \sum w_i C_i </tex> ([[1outtreesumwc|ссылка]])
* <tex> 1 \mid p_i = 1 \mid \sum w_i U_i </tex> ([[1pi1sumwu|''Earliest Due Date rule'']])
* <tex> 1 \mid \mid \sum U_i </tex> ([[1sumu|ссылка]])

Обычно оптимальность жадного выбора доказывают двумя способами:

=== Неправильно ===
Приведем пример часто распространенных '''неправильных''' действий при доказательстве оптимальности жадного алгоритма:

Пусть предложенным нами алгоритмом мы получили какое-то решение <tex> S </tex>. Атомарными изменениями в этом решении <tex> S </tex> будем получать другие допустимые решения <tex> S' </tex> и докажем, что <tex> f(S) \le f(S') </tex>. Тогда решение <tex> S </tex> — оптимально.

Проблема в этих рассуждениях в том, что ими мы доказываем локальную оптимальность алгоритма в решении <tex> S </tex>. Получение же глобального минимума может потребовать нескольких атомарных изменений в расписании, поэтому доказать оптимальность таким образом в общем случае невозможно. Как ближайшую аналогию, можно привести '''неправильное''' утверждение для произвольной функции <tex> f(\bar x) </tex> — «если все частные производные <tex> \frac{\partial f}{\partial x_1} \dots \frac{\partial f}{\partial x_n} </tex> неотрицательны, то в точке <tex> \bar x </tex> наблюдается глобальный минимум».

=== Правильно ===
При доказательстве оптимательности применима стратегия '''аргумент замены''' (англ. ''exchange argument''). Стратегия заключается в рассмотрении текущего решения <tex> S </tex> и оптимального решения <tex> O </tex>. Далее предлагается способ модификации <tex> O </tex> в <tex> O'</tex> так, что:
# <tex> f(O') \le f(O) </tex>, то есть <tex> O' </tex> также оптимально.
# <tex> O' </tex> «более похоже» на <tex> S </tex>, чем на <tex> O </tex>.

Если такой способ найден, получаем, что какой-то последовательностью модификаций <tex> O \to O_t' \to \dots \to O_1' \to S </tex> получим <tex> f(S) \le f(O_1') \le \dots \le f(O_t') \le f(O) </tex>, из чего следует оптимальность <tex> S </tex>.

Отношение «более похоже» должно быть [[Отношение порядка | отношением частичного строгого порядка]]. Часто в качестве него можно выбрать отношение «длина наибольшего общего префикса решения <tex> A </tex> и <tex> S </tex> меньше наибольшего общего префикса решения <tex> B </tex> и <tex> S </tex>». Тогда если мы сможем увеличить длину наибольшего общего префикса для оптимального решения, не нарушив оптимальности, мы приблизимся к <tex> S </tex>. Можно выбирать и более сложные отношения, например, в доказательстве оптимальности алгоритма <tex> P \mid \mid \sum w_i C_i </tex> для решения задачи <tex> P \mid pmtn \mid \sum w_i C_i </tex> используется отношение «время последнего прерывания больше или количество прерываний меньше».

== См. также. ==
* [[Правило Лаулера]]
* [[Flow shop]]
* [[Opi1sumu|<tex> O \mid p_{ij} = 1 \mid \sum U_i</tex>]]

== Примечания ==
<references/>

== Источники информации ==
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer ISBN 978-3-540-69515-8

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

1outtreesumwc

2016-06-06T00:23:14Z

Qradimir: Добавлен раздел про intree расписание

<tex dpi = "200" >1 \mid outtree \mid \sum w_i C_i</tex>

{{Задача
|definition=
Необходимо составить расписание на одном станке работ с произвольными временами выполнения. Минимизировать нужно взвешенную сумму времен завершения работ. Зависимости между работами заданы исходящим [[Дерево, эквивалентные определения | деревом]] {{---}} работа, которая соответствует корню, доступна в начале, все другие работы зависят от одной работы {{---}} отца в дереве.
}}
Тривиальным примером подобной задачи является демонтаж сложного механизма.

== Свойства оптимального расписания ==

Докажем некоторые свойства оптимального расписания, которые мы будем использовать в доказательстве корректности алгоритма.

Введем некоторые обозначения для удобства. За <tex>\mathrm{edges} </tex> обозначим список всех ребёр дерева. Для всех работ <tex>i = 1, \ldots, n</tex> обозначим за <tex>S(i)</tex> всех потомков <tex>i</tex> в дереве зависимостей, включая саму работу <tex>i</tex>, введём новый параметр работы <tex>q_i = \dfrac{w_i}{p_i}</tex>.

Для подмножества работ <tex>I \subseteq \{1, \ldots, n\}</tex> определим:

<tex>w(I) = \sum\limits_{i \in I} w_i, p(I) = \sum\limits_{i \in I} p_i, q(I) = \dfrac{w(I)}{p(I)}</tex>

Два непересекающихся множества работ <tex>I, J \subseteq \{1, \ldots, n\}</tex> будем называть '''параллельными''' <tex>(I \sim J)</tex>, если для всех <tex>i \in I, j \in J</tex> выполняется: <tex>i</tex> не является ни предком, ни потомком <tex>j</tex>. Если множества состоят из одной работы <tex>I = \{i\},\ J = \{j\}</tex>, будем писать <tex>i \sim j</tex>. Каждое расписание представлено перестановкой <tex>\pi</tex>.

{{Лемма
|id=lemma1
|statement= Пусть <tex>\pi</tex> {{---}} оптимальное расписание, <tex>I</tex> и <tex>J</tex> {{---}} два таких параллельных блока (множества работ, выполняемых последовательно) из <tex>\pi</tex>, что <tex>J</tex> выполняется сразу после <tex>I</tex>. Пусть <tex>\pi'</tex> {{---}} расписание, полученное из <tex>\pi</tex> перестановкой <tex>I</tex> и <tex>J</tex>. Тогда выполяются следующие пункты:
:<tex>(a)~ I \sim J \Rightarrow q(I) \geqslant q(J)</tex>
:<tex>(b)</tex> Если <tex>I \sim J</tex> и <tex>q(I) = q(J)</tex>, то <tex>\pi'</tex> {{---}} оптимальное расписание.
|proof=
<tex>(a)</tex>

:Пусть <tex>f = \sum w_i C_i</tex>. Так как <tex>\pi</tex> {{---}} оптимальное расписание, то <tex>f(\pi) \leqslant f(\pi')</tex>. Таким образом:

:<tex>0 \leqslant f(\pi') - f(\pi) = w(I) p(J) - w(J) p(I)</tex>

:Поделим на <tex>p(I)p(J)</tex>:

:<tex>q(I) = \dfrac{w(I)}{p(I)} \geqslant \dfrac{w(J)}{p(J)} = q(J) </tex>

<tex>(b)</tex>

:Если <tex>q(I) = q(J) </tex>, то <tex>f(\pi) = f(\pi') </tex>, следовательно расписание <tex>\pi'</tex> оптимально.
}}

{{Теорема
|id = theorem1
|statement = Пусть <tex>i, ~j</tex> работы такие, что <tex>i</tex> {{---}} предок <tex>j</tex>, и <tex> q_j = \max \{q_k \mid ~ (i, k) \in \mathrm{edges} \}</tex>. 
Тогда существует оптимальное расписание, в котором работа <tex>j</tex> идёт сразу после работы <tex>i</tex>
|proof =
Каждое расписание может быть представлено последовательностью работ в порядке, в котором они выполняются. Пусть <tex> \pi </tex> будет оптимальной такой последовательностью. Также предположим, что количество работ между <tex> i </tex> и <tex> j </tex> равное <tex> l </tex> было бы минимальным. Можно считать, что <tex> l > 0 </tex>. Тогда расписание можно представить следующим образом:

[[Файл:JobBlock.jpg]]

Рассмотрим <tex>2</tex> случая.

'''Случай 1''': <tex> k \in S(i) </tex>

:Работа <tex> j </tex> не является потомком работы <tex> k </tex> , иначе у неё было бы <tex>2</tex> предка. Следовательно, <tex> k \sim j </tex>. По [[#lemma1 | лемме]] <tex> q(k) \geqslant q(j) </tex>, а по условию выбора <tex> j </tex> имеем <tex> q(j) \geqslant q(k) </tex>, значит, <tex> q(j) = q(k) </tex>. Опять же из [[#lemma1 | леммы]] следует, что работы <tex> k </tex> и <tex> j </tex> можно поменять местами, не ухудшив расписание. Это противоречит тому, что мы выбрали минимальное <tex> l </tex>.

'''Случай 2''': <tex> k \not\in S(i) </tex>

:Пусть <tex> h </tex> будет последней работой в расписании между <tex> i </tex> и <tex> j\ ( </tex>включая работу <tex> i) </tex>, которая принадлежит <tex> S(i) </tex>, то есть для всех работ <tex> r </tex> в множестве <tex> K </tex>, назначенных между <tex> h </tex> и <tex> j </tex>, имеем, что <tex> r \not\in S(i) </tex>. Так как наш [[Основные определения теории графов | граф]] зависимостей работ является исходящим деревом и <tex>(i, j) \in \mathrm{edges} </tex>, то любой предок работы <tex> j </tex> также является и предком работы <tex> i </tex>. Поэтому никакая работа из <tex> K </tex> не является предком <tex> j\ (</tex>иначе бы она не смогла стоять после <tex> i) </tex> или потомком, значит, <tex> K \sim j </tex>. Из этого следует, что <tex> q(K) \geqslant q(j) </tex>.

:Работа <tex> h \in S(i) </tex> не является потомком какой-либо работы <tex> r \in K </tex>. В противном же случае получалось, что <tex> r \in S(i) </tex>, значит, <tex> h </tex> является не последней работой из <tex> S(i) </tex> между <tex> i </tex> и <tex> j </tex>. Поэтому <tex> h \sim K </tex>, откуда тут же следует, что <tex> q(h) \geqslant q(K) \geqslant q(j) </tex>. По определению <tex> j </tex> имеем, что <tex> q(j) \geqslant q(h) </tex>, следовательно <tex> q(j) = q(h) = q(K) </tex>. По [[#lemma1 | лемме]] мы можем поменять блоки <tex> K </tex> и <tex> j </tex> не нарушив оптимальности расписания.

Таким образом мы можем менять соседние работы или блоки работ, пока <tex> j </tex> не окажется сразу за <tex> i </tex>.
}}

== Алгоритм ==
Доказанная в предыдущем пункте [[#theorem1 | теорема]] уже даёт основную идею алгоритма: взять работу <tex> j </tex>, отличную от корня дерева, с максимальным значением <tex> q_j </tex> и поставить её в расписании сразу после своего непосредственного предка <tex> i </tex>. Так как существует оптимальное расписание, в котором работа <tex> j </tex> идёт сразу после <tex> i </tex>, то мы можем объедить вершины графа в одну вершину <tex> J_i = \{i, j\}</tex>, которая представляет собой последовательность <tex> \pi_i \colon i, j </tex>. Все сыновья работы <tex> j </tex> станут сыновьями новой вершины <tex> J_i </tex>.

Будем повторять процесс слияния вершин, пока не останется всего одна вершина.

Таким образом каждая вершина <tex> i </tex> представляется множеством работ <tex> J_i </tex> и соответствующей этому множеству последовательностью <tex> \pi_i </tex>. На очередном шаге алгоритма мы находим вершину <tex> j </tex>, отличную от корня, с максимальным значением <tex> q_j </tex>. Пусть <tex> par </tex> {{---}} непосредственный предок работы <tex> j </tex>. Тогда нам надо найти такую вершину <tex> i </tex>, что <tex> par \in J_i </tex>. После этого мы объединяем обе вершины, заменяя <tex> J_i </tex> и <tex> \pi_i </tex> на <tex> J_i \cup J_j </tex> и <tex> \pi_i \circ \pi_j </tex>, где <tex> \pi_i \circ \pi_j </tex> {{---}} это конкатенация последовательностей <tex> \pi_i </tex> и <tex> \pi_j </tex>.

Детали описаны в алгоритме ниже, в котором
* <tex> E(i) </tex> обозначает последнюю работу в последовательности <tex> \pi_i </tex>,
* <tex> P(i) </tex> обозначает предка в графе зависимостей, а после слияния с какой-то вершиной <tex> j </tex> {{---}} предыдущую работу в последовательности <tex> \pi_j </tex>.

w[root] = <tex> - \infty </tex>
'''for''' i = 1..n
E[i] = {i}
J[i] = {i}
q[i] = w[i] \ p[i]
L = {1, ... , n}
'''while''' L <tex> \ne </tex> {root} // пока в списке работ не останется только корень
Найти работу j <tex> \in </tex> L с маскимальным значением q[j]
par = P[j]
Найти i, что par <tex> \in </tex> J[i]
w[i] += w[j]
p[i] += p[j]
q[i] = w[i] / w[j] // пересчитаем значения в вершине
P[j] = E[i] // предком работы j теперь будет последняя работа в <tex> \pi_i </tex>
E[i] = E[j] // последней работой в <tex> \pi_i </tex> теперь будет последняя работа в <tex> \pi_j </tex>
J[i] = J[i] <tex> \cup </tex> J[j]
L = L \ {j}
Вначале делаем присваивание <tex> w(root) = -\infty </tex>, чтобы корень никогда не выбрался на шаге выбора вершины с максимальным значением <tex> q </tex>. В реализации же можно просто дополнительно проверять на равенство с корнем, чтобы избежать переполнений или испортить значение <tex>-\infty</tex>.

После завершения этой процедуры оптимальное расписание можно восстановить с конца, зная <tex> E(root) </tex> и массив <tex> P </tex>.

Если для получения работы <tex> j </tex> с минимальным значением <tex> q(j) </tex> использовать очередь с приоритетами, а для поиска родителям вершины использовать систему непересекающихся множеств, то время работы алгоритма будет <tex> \mathcal{O}(n\log{n}) </tex>.

Проиллюстрируем работу алгоритма на следующем примере.

[[Файл:JobsOuttrees.jpg|650px]]

Первой выберется работа с номером <tex> 5 </tex>. Она объединиться со своим родителем <tex> 2 </tex> и допишется в конец <tex> \pi_2 </tex>. Потом выберется работа <tex> 4 </tex>, потом <tex> \{2, 5\} </tex> и т. д. Процесс будет продолжаться, пока не останется одна вершина. Ответ {{---}} оптимальная последовательность работ {{---}} содержится в <tex> \pi_1 </tex>, который написан внутри последней вершины.

== Доказательство оптимальности алгоритма ==
{{Теорема
|id = theorem2
|statement = Алгоритм <tex> 1 \mid outtree \mid \sum w_i C_i</tex> строит оптимальное расписание.
|proof =
Доказательство проведём по индукции. Очевидно, что для одной вершины алгоритм построит оптимальное расписание. Пусть теперь он может составить оптимальную последовательность назначенных работ числом меньше <tex> n </tex>. Пусть также работы <tex> i, j </tex> {{---}} работы, которые объединятся на первом шаге алгоритма. Тогда оптимальное расписание <tex> R </tex> можно представить следующим образом:

<tex> \pi \colon \pi (1), \ldots, \pi (k), i, j, \pi (k + 3), \ldots, \pi (n) </tex>

После объединения работ <tex> i </tex> и <tex> j </tex> в одну расписание <tex> R' </tex> примет такой вид:

<tex> \pi ' \colon \pi (1), \ldots, \pi (k), I, \pi (k + 3), \ldots, \pi (n) </tex>

где <tex> I = \{i, j\}, ~w(I) = w(i) + w(j), p(I) = p(i) + p(j)</tex>. Обозначим за <tex> f_n(\pi ), ~f_{n-1}(\pi ') </tex> целевые функции для последовательностей <tex> \pi </tex> и <tex> \pi ' </tex> соответственно. Тогда

<tex> f_n(\pi ) - f_{n-1}(\pi') = w(i)p(i) + w(j)(p(i) + p(j)) - (w(i) + w(j))(p(i) + p(j)) = -w(i) p(j)\ (*) </tex>

Следовательно, расписание <tex> R </tex> будет оптимальным тогда и только тогда, когда расписание <tex> R' </tex> будет оптимальным. А по предположению индукции наш алгоритм составит оптимальное расписание для последовательности <tex> \pi ' </tex>.

Теперь разделим обе части равенства <tex> (*) </tex> на <tex> w(i)w(j) </tex>. Получим, что расстояние между целевыми функциями равно

<tex> -\dfrac{p(j)}{w(j)} = -\dfrac{1}{q(j)} </tex>

Это расстояние минимально (по модулю), так как мы выбирали работу <tex> j </tex> с максимальным значением <tex> q(j) </tex>. Из этих утверждений и следует оптимальность построенного алгоритмом расписания.
}}

== Применение алгоритма в задаче с intree-зависимостью ==
Сведем задачу <tex> S_{in} = 1 \mid intree \mid \sum w_i C_i </tex> к решенной задаче <tex>S_{out} = 1 \mid outtree \mid \sum w_i C_i </tex> следующим образом:
* Развернем все ребра, теперь если работа <tex> i </tex> зависела от работы <tex> j </tex>, работа <tex> j </tex> будет зависеть от <tex> i </tex>.
* Заменим все стоимости <tex> w_i </tex> на противоположные <tex> w'_i = - w_i</tex>.
{{Утверждение
|statement=Развернутое оптимальное расписание соответствующей задачи <tex> S_{out} </tex> с весами <tex> w'_i </tex> является оптимальным расписанием для задачи <tex> S_{in} </tex>
|proof=
Полученное расписание будет допустимым, так как расписание для <tex> S_{out} </tex> было допустимым, и в нем никакие две работы не пересекались и не прерывались. Развернув, мы не могли нарушить это свойство. Также из-за того, что мы развернули расписание, мы добились того, что все работы выполняются в правильном порядке (в расписании для <tex> S_{out} </tex> из-за того, что все ребра были развернуты, порядок был нарушен для всех работ). Таким образом, получили что расписание — допустимое.

Пусть с помощью задачи <tex> S_{out} </tex> мы получили последовательность работ <tex> 1 \dots n </tex>. Распишем по определению значение целевой функции для <tex> S_{out} </tex>:
<tex>\sum -w_i C_i = \sum \limits_{i=1}^n ( -w_i \sum \limits_{j=1}^i p_j ) = \\
\sum\limits_{i=1}^n ( w_i \sum\limits_{j=i+1}^n p_j ) - \sum\limits_{i=1}^n w_i \sum \limits_{i=1}^n p_i = \\
\sum\limits_{i=1}^n ( w_i \sum\limits_{j=i}^n p_j ) - \sum\limits_{i=1}^n w_i p_i - \sum\limits_{i=1}^n w_i \sum \limits_{i=1}^n p_i </tex>
Заметим, что первое слагаемое соответствует целевой функции <tex> \sum w_i C_i </tex> для последовательности <tex> n \dots 1 </tex>, а второе и третье слагаемые — константы, зависящие только от входных данных и не зависящие от перестановки работ. Таким образом, оптимальное значение для <tex> S_{out} </tex> также минимизирует <tex> S_{in} </tex>.
}}
== Источники информации ==
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 73 - 78

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

RSumCi

2016-06-05T22:25:47Z

Qradimir: Конспект создан

<tex dpi="200">R \mid \mid \sum C_i</tex>
{{Задача
|definition=Дано <tex> n </tex> работ и <tex> m </tex> станков, причем для каждого станка длительность выполнения на нем <tex>i</tex>-й работы своя и равна <tex> p_{ij} </tex>. Необходимо минимизировать сумму времени выполнения работ.
}}
==Алгоритм==

===Описание алгоритма===
Рассмотрим произвольное допустимое расписание для этой задачи. Рассмотрим какую-то станок <tex> j </tex>, пусть на нем выполняется <tex>n_j</tex> работ. Тогда вклад этого станка в целевую функцию (не теряя общности, пронумеруем работы на этом станке от <tex>1 </tex> до <tex>n_j</tex>) рассчитывается как:

<tex> \sum\limits_{i=1}^{n_j} (p_ij + \sum\limits_{q=1}^{i-1} p_qj) = n_j p_{1j} + (n_j - 1) p_{2j} + \dots + 2 p_{(n_j-1)j} + p_{n_jj} </tex>

Заметим, что в каждом допустимом расписании перед каждой работой окажется коэффициент <tex> k </tex>, означающий, что соответствующая работа выпллняется <tex> k </tex>-й с конца. Понятно, что в различных расписаниях <tex> k </tex> может принимать значения от <tex>1</tex> до <tex>n</tex>.

Сведем задачу к назначению каждой работы <tex> i </tex> позиции с конца <tex> k </tex> на станке <tex> j </tex> с помощью задачи [[Поток минимальной стоимости | mincost-maxflow]]. Поместим в левую долю графа работы, в правую долю — пары из станка и коэффициента и проведем соответствующие ребра пропускной способности <tex>1</tex> и стоимости <tex>k p_{ij}</tex>, соответствующие вкладу работы в целевую функцию, если она окажется в позиции <tex> k </tex> с конца на станке <tex> j </tex>. Проведем из стока в левую долю ребра стоимости <tex>0</tex> и пропускной способности <tex>1</tex>, из правой доли в сток — также ребра стоимости <tex> 0 </tex> и пропускной способности <tex>1</tex>. Максимальный поток минимальной стоймости в построенной сети будет ответом на исходную задачу.
{{Утверждение
|statement=Eсли ребро <tex> i \to (j, k) </tex> насыщено потоком, то работа <tex> i </tex> в оптимальном расписании должна стоять на станке <tex> j </tex> в позиции <tex> k </tex> с конца.
|proof=
# Целевые функции задачи mincost-maxflow и текущей задачи совпадают, так как у ребер между долями пропускная способность 1, а у дополнительных ребер из истока и в сток нулевая стоимость, и они не могут внести вклад в целевую функцию.
# Расписание, построенное по вышепредставленному способу действительно будет допустимым.
## Благодаря ограничениям на поток, входящий в левую долю, каждая работа будет назначена только один раз.
## Благодаря ограничениям на поток, выходящий из правой доли, на каждую позицию будет назначено не более одной работы.
## Докажем, что не возникает ситуации такой, что существует такая позиция <tex> l </tex>, что в этой позиции с конца стоит какая-то работа, а в позиции <tex> l - 1 </tex> с конца — нет (это противоречит определению <tex>l</tex>-й с конца работы). Такая ситуация означает, что ребро <tex> i \to (j, l) </tex> оказалось насышено потоком, а ребро <tex>i \to (j, l - 1) </tex> — не насыщено. Но стоимость ребра <tex> i \to (j, l - 1) </tex> меньше стоимости ребра <tex> i \to (j, l) </tex>, поэтому можем переместить поток с ребра <tex> i \to (j, l) </tex> на ребро <tex> i \to (j, l - 1) </tex>, не нарушив свойства потока и улучшив целевую функцию, что противоречит оптимальности ответа для mincost-maxflow. Следовательно, такой позиции не возникнет и расписание будет допустимым.
}}

===Время выполнения===
Время выполнения mincost-maxflow равно <tex> O(V \cdot E^2) </tex>. Количество вершин в получаемой сети равно <tex> O(m \cdot n) </tex>. Количество ребер в сети равно <tex> O(m \cdot n^2) </tex>. Следственно, ассимптотика алгоритма равна <tex> O(m^3 \cdot n^5) </tex>.

==См. также==
* [[Поток минимальной стоимости]]
* [[Методы решения задач теории расписаний]]

Opij1Sumwc

2016-06-05T21:36:09Z

Qradimir:

<tex dpi="200">O \mid p_{ij}=1 \mid \sum w_i C_i</tex>
{{Задача
|definition = Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex> работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно 1. Необходимо минимизировать взвешенную сумму времен завершения работ.
}}
==Алгоритм==

===Описание алгоритма===
{{Утверждение
|statement=Оптимальный ответ для <tex>S = O \mid p_{ij}=1 \mid \sum w_i C_i</tex> равен оптимальному ответу к задаче <tex>S' = P \mid p_i=m, pmtn \mid \sum w_i C_i</tex>
|proof=Для доказательства этого утверждения необходимо показать то, что из оптимальности <tex> S' </tex> следует оптимальность <tex> S </tex>, и способ построения допустимого расписания для <tex> S </tex> из расписания для <tex> S' </tex>:
# Целевые функции задач совпадают, поэтому из оптимальности <tex> S' </tex> следует оптимальность <tex> S </tex>.
# Покажем, как получить из расписания <tex> S' </tex> допустимое расписание для <tex>S</tex> (в расписании для <tex>S'</tex> допустимость нарушает то, что на одном станке выполняется несколько блоков одной работы):
## Построим двудольный граф, в левую долю которого поместим работы, а в правую — возможные моменты времени. Из вершины, соответствующей работе <tex> i </tex> будет идти ребро в вершину, соответствующую временному моменту <tex> t</tex>, если работа <tex> i </tex> в расписании для <tex> S' </tex> претендует на выполнение в момент времени <tex>t</tex>.
## Раскрасим ребра этого графа в <tex>m</tex> цветов, из теории графов известно, что это можно сделать.
## Назначим выполнение единичного элемента работы <tex>i</tex> в момент времени <tex>t</tex> на станке <tex>k</tex>, если соответствующее ребро раскрашено в цвет <tex>k</tex>.
## После данного преобразования мы не изменим значение целевой функции (так как мы переставляем только элементы работ, выполняющихся в один и тот же момент времени). Также расписание станет допустимым для <tex> S </tex>, так как по определению реберной раскраски, не будет ни одной работы, два единичных блока которых выполняется на одном станке и во все моменты времени не окажется того, что на один станок назначено две работы.
}}
Чтобы непосредственно решить эту задачу, воспользуемся теоремой о том, что для задачи <tex> P \mid p_i=m, pmtn \mid \sum w_i C_i </tex> существует оптимальное расписание без прерываний<ref>P. Brucker. Scheduling Algorithms (2006), 5th edition, p. 121 </ref>. Известно, что для того, чтобы получить оптимальное расписание для такой задачи без прерываний, надо помещать работы по очереди на станки <tex>1 \dots m </tex> в порядке убывания весов. Длительности у всех работ совпадают, поэтому расписание будет состоять из <tex> \lfloor \frac{n}{m} \rfloor </tex> блоков по <tex> m </tex> работ и, возможно, одного неполного блока из <tex> n \mod m </tex> работ. Таким образом, аналогично задаче <tex> O \mid p_{ij}=1 \mid C_{max}</tex>, чтобы получить допустимое расписание, можно не строить раскраску графа, а просто циклически сдвигать последовательности работ внутри каждого блока.

===Время работы===
Чтобы построить циклические сдвиги внутри одного блока требуется <tex> O(m^2) </tex> времени. Всего блоков <tex> O(\frac{n}{m}) </tex>.
Значит, итоговая ассимптотика равна <tex> O(n \cdot m) </tex>.

==См. также.==
* [[Методы решения задач теории расписаний]]

==Примечания==
<references/>

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

Opij1Sumwc

2016-06-05T21:34:26Z

Qradimir: Конспект создан

<tex dpi="200">O \mid p_{ij}=1 \mid \sum w_i C_i</tex>
{{Задача
|definition = Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex> работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно 1. Необходимо минимизировать взвешенную сумму времен завершения работ.
}}

==Алгоритм==

===Описание алгоритма===
{{Утверждение
|statement=Оптимальный ответ для <tex>S = O \mid p_{ij}=1 \mid \sum w_i C_i</tex> равен оптимальному ответу к задаче <tex>S' = P \mid p_i=m, pmtn \mid \sum w_i C_i</tex>
|proof=Для доказательства этого утверждения необходимо показать то, что из оптимальности <tex> S' </tex> следует оптимальность <tex> S </tex>, и способ построения допустимого расписания для <tex> S </tex> из расписания для <tex> S' </tex>:
# Целевые функции задач совпадают, поэтому из оптимальности <tex> S' </tex> следует оптимальность <tex> S </tex>.
# Покажем, как получить из расписания <tex> S' </tex> допустимое расписание для <tex>S</tex> (в расписании для <tex>S'</tex> допустимость нарушает то, что на одном станке выполняется несколько блоков одной работы):
## Построим двудольный граф, в левую долю которого поместим работы, а в правую — возможные моменты времени. Из вершины, соответствующей работе <tex> i </tex> будет идти ребро в вершину, соответствующую временному моменту <tex> t</tex>, если работа <tex> i </tex> в расписании для <tex> S' </tex> претендует на выполнение в момент времени <tex>t</tex>.
## Раскрасим ребра этого графа в <tex>m</tex> цветов, из теории графов известно, что это можно сделать.
## Назначим выполнение единичного элемента работы <tex>i</tex> в момент времени <tex>t</tex> на станке <tex>k</tex>, если соответствующее ребро раскрашено в цвет <tex>k</tex>.
## После данного преобразования мы не изменим значение целевой функции (так как мы переставляем только элементы работ, выполняющихся в один и тот же момент времени). Также расписание станет допустимым для <tex> S </tex>, так как по определению реберной раскраски, не будет ни одной работы, два единичных блока которых выполняется на одном станке и во все моменты времени не окажется того, что на один станок назначено две работы.
}}
Чтобы непосредственно решить эту задачу, воспользуемся теоремой о том, что для задачи <tex> P \mid p_i=m, pmtn \mid \sum w_i C_i </tex> существует оптимальное расписание без прерываний<ref>P. Brucker. Scheduling Algorithms (2006), 5th edition, p. 121 </ref>. Известно, что для того, чтобы получить оптимальное расписание для такой задачи без прерываний, надо помещать работы по очереди на станки <tex>1 \dots m </tex> в порядке убывания весов. Длительности у всех работ совпадают, поэтому расписание будет состоять из <tex> \lfloor \frac{n}{m} \rfloor </tex> блоков по <tex> m </tex> работ и, возможно, одного неполного блока из <tex> n \mod m </tex> работ. Таким образом, аналогично задаче <tex> O \mid p_{ij}=1 \mid C_{max}</tex>, чтобы получить допустимое расписание, можно не строить раскраску графа, а просто циклически сдвигать последовательности работ внутри каждого блока.

===Время работы===
Чтобы построить циклические сдвиги внутри одного блока требуется <tex> O(m^2) </tex> времени. Всего блоков <tex> O(\frac{n}{m}) </tex>.
Значит, итоговая ассимптотика равна <tex> O(n \cdot m) </tex>.

==См. также.==
* [[Методы решения задач теории расписаний]]

==Примечания==
<references/>

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

Opij1Cmax

2016-06-05T20:34:54Z

Qradimir: /* Оценка сложности алгоритма */

<tex dpi = "200">O \mid p_{ij} = 1 \mid C_{max}</tex>
{{Задача
|definition = Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex> работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно 1. Необходимо минимизировать время выполнения всех работ.
}}
==Алгоритм==

===Описание алгоритма===
Минимальное значение <tex> T_{min} </tex> минимизуруемой функции упирается в следующие ограничения:
# В допустимом расписании на каждом станке надо обработать каждую работу, поэтому <tex> T_{min} \ge n </tex>.
# В допустимом расписании каждую работу нужно обработать на всех станках, причем ее нельзя обрабатывать на двух станках одновременно, поэтому <tex> T_{min} \ge m </tex>.
Тогда <tex> T_{min} = \max{(m, n)} </tex>.

В случае <tex> n \ge m </tex> оптимальное расписание циклическими сдвигами последовательности <tex> 1 \dots n </tex> и выглядит следующим образом:
'''1 2 3 ... k k+1 ... n-1 n'''
'''M_1''' 1 2 3 ... k k+1 ... n-1 n
'''M_2''' n 1 2 ... k-1 k ... n-2 n-1
'''.''' ... ... ... ... ... ... ... ... ...
'''.''' ... ... ... ... ... ... ... ... ...
'''M_m''' n-m+2 n-m+3 ... ... ... ... ... n-m n-m+1

Если же <tex> n < m </tex>, добавим <tex> m - n </tex> фиктивных работ с номерами <tex> n + 1 \dots m </tex>, построим расписание способом выше и удалим из полученного расписания фиктивные работы.

===Оценка сложности алгоритма===
Минимальное значение <tex> C_{max} </tex> вычисляется за <tex> \mathcal{O}(1) </tex> времени.
Построение расписания сводится к заполнению матрицы размером <tex> m \times \max{(m, n)} </tex> и выполняется за <tex> \mathcal{O}(m \dot (m + n)) </tex> времени.

==См. также.==
* [[Методы решения задач теории расписаний]]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

Opij1Cmax

2016-06-05T20:02:13Z

Qradimir: Добавлен конспект

<tex dpi = "200">O \mid p_{ij} = 1 \mid C_{max}</tex>
{{Задача
|definition = Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex> работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно 1. Необходимо минимизировать время выполнения всех работ.
}}
==Алгоритм==

===Описание алгоритма===
Минимальное значение <tex> T_{min} </tex> минимизуруемой функции упирается в следующие ограничения:
# В допустимом расписании на каждом станке надо обработать каждую работу, поэтому <tex> T_{min} \ge n </tex>.
# В допустимом расписании каждую работу нужно обработать на всех станках, причем ее нельзя обрабатывать на двух станках одновременно, поэтому <tex> T_{min} \ge m </tex>.
Тогда <tex> T_{min} = \max{(m, n)} </tex>.

В случае <tex> n \ge m </tex> оптимальное расписание циклическими сдвигами последовательности <tex> 1 \dots n </tex> и выглядит следующим образом:
'''1 2 3 ... k k+1 ... n-1 n'''
'''M_1''' 1 2 3 ... k k+1 ... n-1 n
'''M_2''' n 1 2 ... k-1 k ... n-2 n-1
'''.''' ... ... ... ... ... ... ... ... ...
'''.''' ... ... ... ... ... ... ... ... ...
'''M_m''' n-m+2 n-m+3 ... ... ... ... ... n-m n-m+1

Если же <tex> n < m </tex>, добавим <tex> m - n </tex> фиктивных работ с номерами <tex> n + 1 \dots m </tex>, построим расписание способом выше и удалим из полученного расписания фиктивные работы.

===Оценка сложности алгоритма===
Минимальное значение <tex> C_{max} </tex> вычисляется за <tex> O(1) </tex> времени.
Построение расписания сводится к заполнению матрицы размером <tex> m \times \max{(m, n)} </tex> и выполняется за <tex> O(m \dot (m + n)) </tex> времени.

==См. также.==
* [[Методы решения задач теории расписаний]]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

Дискретная математика, алгоритмы и структуры данных

2016-06-05T19:04:48Z

Qradimir: Новые конспекты из методов решений

[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы и структуры данных]]
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].

Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.

= Первый семестр =

== Отношения ==
*[[Определение отношения]]
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
*[[Симметричное отношение]]
*[[Антисимметричное отношение]]
*[[Транзитивное отношение]]
*[[Отношение порядка]]
*[[Отношение эквивалентности]]
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
*[[Транзитивный остов]]

== Булевы функции ==
*[[Определение булевой функции]]
*[[Побитовые операции]]<tex>^\star</tex>
*[[Суперпозиции]]
*[[ДНФ]]
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
*[[КНФ]]
*[[2-SAT]]
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
*[[Полные системы функций. Теорема Поста о полной системе функций]]
*[[Представление функции класса DM с помощью медианы]]
*[[Пороговая функция]]
*[[Троичная логика]]<tex>^\star</tex>

== Схемы из функциональных элементов ==
*[[Реализация булевой функции схемой из функциональных элементов]]
*[[Простейшие методы синтеза схем из функциональных элементов]]
*[[Метод Лупанова синтеза схем]]
*[[Cумматор]]
*[[Каскадный сумматор]]
*[[Двоичный каскадный сумматор]]
*[[Троичный сумматор]]<tex>^\star</tex>
*[[Реализация вычитания сумматором]]
*[[Матричный умножитель]]
*[[Дерево Уоллеса]]
*[[Контактная схема]]
*[[Триггеры]]<tex>^\star</tex>
*[[Квантовые гейты]]<tex>^\star</tex>

== Представление информации ==
*[[Кодирование информации]]
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
*[[Представление вещественных чисел]]
*[[Представление символов, таблицы кодировок]]<tex>^\star</tex>

== Алгоритмы сжатия ==
* [[Алгоритм Хаффмана]]
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]
* [[Алгоритм Хаффмана за O(n)]]
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
* [[Неравенство Крафта]]
* [[Неравенство Макмиллана]]
* [[Код Шеннона]]
* [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
* [[Алгоритмы LZ77 и LZ78]]
* [[Алгоритм LZW]]
* [[Алгоритм LZSS]]<tex>^\star</tex>
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
* [[Преобразование MTF]]
* [[Расстояние Хэмминга]]
* [[Избыточное кодирование, код Хэмминга]]
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>

== Комбинаторика ==
=== Комбинаторные объекты ===
* [[Комбинаторные объекты]]
* [[Лексикографический порядок]]
* [[Коды Грея]]
* [[Коды Грея для перестановок]]
* [[Коды антигрея]]
* [[Цепные коды]]
* [[Правильные скобочные последовательности]]

=== Генерация комбинаторных объектов ===
* [[Генерация комбинаторных объектов в лексикографическом порядке]]
* [[Получение номера по объекту]]
* [[Получение объекта по номеру]]
* [[Получение следующего объекта]]
* [[Получение предыдущего объекта]]<tex>^\star</tex>
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
* [[Методы генерации случайного сочетания]]<tex>^\star</tex>

=== Подсчёт числа объектов ===
* [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* [[Производящая функция]]
* [[Лемма Бёрнсайда и Теорема Пойа]]
* [[Задача об ожерельях]]
* [[Числа Стирлинга первого рода]]
* [[Числа Стирлинга второго рода]]
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex>
* [[Числа Каталана]]

=== Свойства комбинаторных объектов ===
* [[Умножение перестановок, обратная перестановка, группа перестановок]]
* [[Действие перестановки на набор из элементов, представление в виде циклов]]
* [[Таблица инверсий]]
* [[Теорема Кэли]]
* [[Матричное представление перестановок]]
* [[Задача о минимуме/максимуме скалярного произведения]]
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]

== [[Динамическое программирование]] ==
=== Классические задачи динамического программирования ===
*[[Кратчайший путь в ациклическом графе]]
*[[Задача о числе путей в ациклическом графе]]
*[[Задача о расстановке знаков в выражении]]
*[[Задача о порядке перемножения матриц]]
*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Задача коммивояжера, ДП по подмножествам]]
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
*[[Задача о рюкзаке]]

=== Способы оптимизации методов динамического программирования ===
*[[Метод четырех русских для умножения матриц]]
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex>
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
*[[Meet-in-the-middle]]<tex>^\star</tex>

=== Другие задачи ===
*[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex>
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
*[[Задача о наибольшей подпоследовательности-палиндроме]]
*[[Наибольшая общая возрастающая подпоследовательность]]<tex>^\star</tex>
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
*[[Динамическое программирование по профилю]]<tex>^\star</tex>
*[[Динамика по поддеревьям]]

== Теория вероятностей ==
*[[Вероятностное пространство, элементарный исход, событие]]
*[[Независимые события]]
*[[Условная вероятность]]
*[[Формула полной вероятности]]
*[[Формула Байеса]]
*[[Дискретная случайная величина]]
*[[Независимые случайные величины]]
*[[Математическое ожидание случайной величины]]
*[[Дисперсия случайной величины]]
*[[Ковариация случайных величин]]
*[[Корреляция случайных величин]]
*[[Неравенство Маркова]]
*[[Энтропия случайного источника]]
*[[Симуляция одним распределением другого]]
*[[Арифметическое кодирование]]
*[[Парадоксы теории вероятностей]]<tex>^\star</tex>
*[[Схема Бернулли]]<tex>^\star</tex>

== Марковские цепи ==

* [[Марковская цепь]]
* [[Теорема о поглощении]]
* [[Фундаментальная матрица]]
* [[Математическое ожидание времени поглощения]]
* [[Расчет вероятности поглощения в состоянии]]
* [[Эргодическая марковская цепь]]
* [[Регулярная марковская цепь]]
* [[Примеры использования Марковских цепей]]
* [[Скрытые Марковские модели]]<tex>^\star</tex>
* [[Алгоритм Витерби]]<tex>^\star</tex>
* [[Алгоритм "Вперед-Назад"]]<tex>^\star</tex>
* [[Алгоритм Баума-Велша]]<tex>^\star</tex>

= Второй семестр =

== Амортизационный анализ ==
* [[Амортизационный анализ]]
* [[Динамический массив]]
* [[Hashed Array Tree]]<tex>^\star</tex>
* [[Список]]
* [[Стек]]
* [[Очередь]]
* [[Дек]]
* [[Мажорирующий элемент]]
* [[Счетчик Кнута]]
* [[Мастер-теорема]]<tex>^\star</tex>
* [[List order maintenance]]<tex>^\star</tex>

== Персистентные структуры данных ==
* [[Персистентные структуры данных]]
* [[Персистентный стек]]
* [[Персистентная очередь]]
* [[Персистентный дек]]
* [[Персистентная приоритетная очередь]]

== [[Приоритетные очереди]] ==
* [[Двоичная куча]]
* [[Биномиальная куча]]
* [[Фибоначчиева куча]]
* [[Левосторонняя куча]]
* [[Тонкая куча]]
* [[Толстая куча на избыточном счетчике]]
* [[Куча Бродала-Окасаки]]<tex>^\star</tex>

== Система непересекающихся множеств ==
* [[СНМ (наивные реализации) | Наивные реализации]]
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
* [[СНМ с операцией удаления за О(1)]]<tex>^\star</tex>

== [[Поисковые структуры данных]] ==
* [[Упорядоченное множество]]
* [[Дерево поиска, наивная реализация]]
* [[АВЛ-дерево]]
* [[2-3 дерево]]
* [[B-дерево]]
* [[Красно-черное дерево]]
* [[Декартово дерево]]
* [[Декартово дерево по неявному ключу]]
* [[Splay-дерево]]
* [[Tango-дерево]]<tex>^\star</tex>
* [[Рандомизированное бинарное дерево поиска]]
* [[Дерево ван Эмде Боаса]]
* [[Список с пропусками]]
* [[Fusion tree]]<tex>^\star</tex>
* [[Сверхбыстрый цифровой бор]]
* [[Rope]]<tex>^\star</tex>

== Дерево отрезков ==

* [[Статистики на отрезках. Корневая эвристика]]
* [[Дерево отрезков. Построение]]
* [[Реализация запроса в дереве отрезков сверху]]
* [[Реализация запроса в дереве отрезков снизу]]
* [[Несогласованные поддеревья. Реализация массового обновления]]
* [[Многомерное дерево отрезков]]
* [[Сжатое многомерное дерево отрезков]]

== Дерево Фенвика ==
* [[Дерево Фенвика]]
* [[Встречное дерево Фенвика]]
* [[Дерево Фенвика для некоммутативных операций]]
* [[Многомерное дерево Фенвика]]

== Хеширование ==
* [[Хеш-таблица]]
* [[Разрешение коллизий]]
* [[Хеширование кукушки]]
* [[Идеальное хеширование]]
* [[Перехеширование]]
* [[Фильтр Блума]]
* [[Quotient filter]]<tex>^\star</tex>
* [[Универсальное семейство хеш-функций]]
* [[Расширяемое хеширование]]<tex>^\star</tex>

== [[Сортировки]] ==
=== Квадратичные сортировки ===
* [[Сортировка выбором]]
* [[Сортировка пузырьком]]
* [[Сортировка вставками]]
=== Сортировки на сравнениях ===
* [[Сортировка Шелла]]<tex>^\star</tex>
* [[Сортировка кучей]]
* [[Быстрая сортировка]]
* [[Сортировка слиянием]]
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
* [[Терпеливая сортировка]]<tex>^\star</tex>
* [[Timsort]]<tex>^\star</tex>
* [[Smoothsort]]<tex>^\star</tex>
* [[Теорема о нижней оценке для сортировки сравнениями]]

=== Многопоточные сортировки ===
* [[Многопоточная сортировка слиянием]]<tex>^\star</tex>
* [[PSRS-сортировка]]<tex>^\star</tex>
=== Другие сортировки ===
* [[Поиск k-ой порядковой статистики]]
* [[Поиск k-ой порядковой статистики за линейное время]]
* [[Поиск k-ой порядковой статистики в двух массивах]]<tex>^\star</tex>
* [[Сортировка подсчетом]]
* [[Цифровая сортировка]]
* [[Карманная сортировка]]
* [[Сортировка Хана]]<tex>^\star</tex>
* [[Задача флага Нидерландов]]<tex>^\star</tex>
* [[Блинная сортировка]]<tex>^\star</tex>

== Сортирующие сети ==
* [[Сортирующие сети]]
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
* [[Сортирующие сети для квадратичных сортировок]]
* [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex>
* [[Сеть Бетчера]]

== Алгоритмы поиска ==
* [[Целочисленный двоичный поиск]]
* [[Поиск в матрице]]<tex>^\star</tex>
* [[Вещественный двоичный поиск]]
* [[Троичный поиск]]
* [[Поиск с помощью золотого сечения]]
* [[Интерполяционный поиск]]
* [[Метод Фибоначчи]]<tex>^\star</tex>

== Связь между структурами данных ==
* [[Связь между структурами данных]]

= Третий семестр =

== Основные определения теории графов ==
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
* [[Лемма о рукопожатиях]]
* [[Теорема о существовании простого пути в случае существования пути]]
* [[Теорема о существовании простого цикла в случае существования цикла]]
* [[Матрица смежности графа]]
* [[Матрица инцидентности графа]]
* [[Циклическое пространство графа]]<tex>^\star</tex>
* [[Фундаментальные циклы графа]]<tex>^\star</tex>
* [[Дерево, эквивалентные определения]]
* [[Алгоритмы на деревьях]]<tex>^\star</tex>
* [[Дополнительный, самодополнительный граф]]
* [[Теоретико-множественные операции над графами]]<tex>^\star</tex>
* [[Рёберное ядро]]
* [[Факторизация графов]]<tex>^\star</tex>

== Связность в графах ==
* [[Отношение связности, компоненты связности]]
* [[Отношение реберной двусвязности]]
* [[Отношение вершинной двусвязности]]
* [[Точка сочленения, эквивалентные определения]]
* [[Мост, эквивалентные определения]]
* [[Граф компонент реберной двусвязности]]
* [[Граф блоков-точек сочленения]]
* [[k-связность]]
* [[Теорема Менгера]]
* [[Теорема Менгера, альтернативное доказательство]]
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]

== Остовные деревья ==
=== Построение остовных деревьев ===
* [[Остовные деревья: определения, лемма о безопасном ребре]]
* [[Алгоритм Прима]]
* [[Алгоритм Краскала]]
* [[Алгоритм Борувки]]
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
* [[Алгоритм двух китайцев]]

=== Свойства остовных деревьев ===
* [[Матрица Кирхгофа]]
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
* [[Количество помеченных деревьев]]
* [[Коды Прюфера]]

== Обходы графов ==
=== Эйлеровы графы ===
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [[Покрытие ребер графа путями]]
* [[Алгоритм построения Эйлерова цикла]]
* [[Произвольно вычерчиваемые из заданной вершины графы]]
=== Гамильтоновы графы ===
* [[Гамильтоновы графы]]
* [[Теорема Хватала]]
* [[Теорема Дирака]]
* [[Теорема Оре]]
* [[Теорема Поша]]<tex>^\star</tex>
* [[Теорема Гуйя-Ури]]<tex>^\star</tex>
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
* [[Теорема Гринберга]]<tex>^\star</tex>
* [[Турниры]]
* [[Теорема Редеи-Камиона]]

== Укладки графов ==
* [[Укладка графа на плоскости]]
* [[Формула Эйлера]]
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
* [[Укладка дерева]]
* [[Укладка графа с планарными компонентами реберной двусвязности]]
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
* [[Теорема Понтрягина-Куратовского]]
* [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex>
* [[Двойственный граф планарного графа]]
* [[Теорема Фари]]<tex>^\star</tex>
* [[Гамма-алгоритм]]

== Раскраски графов ==
* [[Раскраска графа]]
* [[Двудольные графы и раскраска в 2 цвета]]
* [[Хроматический многочлен]]
* [[Формула Зыкова]]
* [[Формула Уитни]]
* [[Теорема Брукса]]
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>
* [[Хроматическое число планарного графа]]
* [[Многочлен Татта]]<tex>^\star</tex>
* [[Теория Рамсея]]<tex>^\star</tex>

== Обход в глубину ==
* [[Обход в глубину, цвета вершин]]
* [[Лемма о белых путях]]
* [[Использование обхода в глубину для проверки связности]]
* [[Использование обхода в глубину для поиска цикла]]
* [[Использование обхода в глубину для топологической сортировки]]
* [[Использование обхода в глубину для поиска компонент сильной связности]]
* [[Использование обхода в глубину для поиска точек сочленения]]
* [[Построение компонент вершинной двусвязности]]
* [[Использование обхода в глубину для поиска мостов]]
* [[Построение компонент реберной двусвязности]]

== Кратчайшие пути в графах ==
* [[Обход в ширину]]
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Флойда]]
* [[Алгоритм Джонсона]]
* [[Алгоритм Левита]]<tex>^\star</tex>
* [[Алгоритм A*]] <tex>^\star</tex>
* [[Алгоритм D*]] <tex>^\star</tex>
* [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex>

== Задача о паросочетании ==
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
* [[Алгоритм Куна для поиска максимального паросочетания]]
* [[Теорема Холла]]
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
* [[Связь вершинного покрытия и независимого множества]]
* [[Рёберное ядро]]<tex>^\star</tex>
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
* [[Теорема Татта о существовании полного паросочетания]]
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
* [[Декомпозиция Эдмондса-Галлаи]]
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex>
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>

== Задача о максимальном потоке ==
* [[Определение сети, потока]]
* [[Разрез, лемма о потоке через разрез]]
* [[Дополняющая сеть, дополняющий путь]]
* [[Сложение и разность потоков]]
* [[Теорема Форда-Фалкерсона]]
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алоритм Эдмондса-Карпа]]
* [[Алгоритм масштабирования потока]]
* [[Блокирующий поток]]
* [[Схема алгоритма Диница]]
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
* [[Алгоритм Голдберга-Тарьяна]]<tex>^\star</tex>
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Метод проталкивания предпотока]]
* [[Алгоритм "поднять-в-начало"]]
* [[Теорема о декомпозиции]]
* [[Теорема о декомпозиционном барьере]]
* [[Циркуляция потока]]
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex>

== Задача о потоке минимальной стоимости ==
* [[Поток минимальной стоимости]]
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
* [[Венгерский алгоритм решения задачи о назначениях]]

= Четвертый семестр =

== Основные определения. Простые комбинаторные свойства слов ==
* [[Основные определения, связанные со строками]]
* [[Период и бордер, их связь]]
* [[Слово Фибоначчи]]
* [[Слово Туэ-Морса]]
* [[Декомпозиция Линдона]]<tex>^\star</tex>
* [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex>
* [[Алгоритм Крочемора]]<tex>^\star</tex>
* [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex>
* [[Алгоритм Манакера]]<tex>^\star</tex>

== [[Поиск подстроки в строке]] ==
=== Точный поиск ===
* [[Наивный алгоритм поиска подстроки в строке]]
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
* [[Префикс-функция]]
* [[Алгоритм Кнута-Морриса-Пратта]]
* [[Автомат Кнута-Морриса-Пратта]]
* [[Z-функция]]
* [[Бор]]
* [[Алгоритм Ахо-Корасик]]
* [[Суффиксный автомат]]
* [[Алгоритм Бойера-Мура]]
* [[Алгоритм Апостолико-Крочемора]]<tex>^\star</tex>
* [[Алгоритм Колусси]]<tex>^\star</tex>
* [[Алгоритм Райта]]<tex>^\star</tex>
* [[Алгоритм Shift-And]]<tex>^\star</tex>
* [[Двусторонний алгоритм]]<tex>^\star</tex>
* [[Турбо-алгоритм Бойера-Мура]]<tex>^\star</tex>

=== Нечёткий поиск ===
* [[Алгоритм Ландау-Вишкина (k несовпадений)]]<tex>^\star</tex>
* [[Алгоритм Ландау-Вишкина (k различий)]]<tex>^\star</tex>

== Суффиксное дерево ==
* [[Суффиксный бор]]
* [[Сжатое суффиксное дерево]]
* [[Алгоритм Укконена]]
* [[Алгоритм МакКрейта]]<tex>^\star</tex>
* [[Алгоритм Фарача]]<tex>^\star</tex>

== Суффиксный массив ==
* [[Суффиксный массив]]
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
* [[Алгоритм Касаи и др.]]
* [[Алгоритм Карккайнена-Сандерса]]
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
* [[Количество подпалиндромов в строке]]<tex>^\star</tex>

== Задача о наименьшем общем предке ==
* [[Сведение задачи LCA к задаче RMQ]]
* [[Сведение задачи RMQ к задаче LCA]]
* [[Метод двоичного подъема]]
* [[Решение RMQ с помощью разреженной таблицы]]
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
* [[Алгоритм Хьюи]]
* [[Heavy-light декомпозиция]]
* [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>
* [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex>
* [[Link-Cut Tree]]<tex>^\star</tex>
* [[Rake-Compress деревья]]<tex>^\star</tex>

== Матроиды ==
=== Основные факты теории матроидов ===
* [[Определение матроида]]
* [[Примеры матроидов]]
* [[Прямая сумма матроидов]]
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
* [[Теорема о базах]]
* [[Аксиоматизация матроида базами]]
* [[Теорема о циклах]]
* [[Аксиоматизация матроида циклами]]
* [[Ранговая функция, полумодулярность]]
* [[Аксиоматизация матроида рангами]]
* [[Двойственный матроид]]
* [[Оператор замыкания для матроидов]]
* [[Покрытия, закрытые множества]]
* [[Матроид Вамоса]]<tex>^\star</tex>

=== Пересечение матроидов ===
* [[Пересечение матроидов, определение, примеры]]
* [[Граф замен]]
* [[Алгоритм построения базы в пересечении матроидов]]

=== Объединение матроидов ===
* [[Объединение матроидов, проверка множества на независимость]]
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]
* [[Алгоритм построения базы в объединении матроидов]]

== Теория расписаний ==
=== Общая теория ===
* [[Классификация задач]]
* [[Методы решения задач теории расписаний]]
* [[Правило Лаулера]]

=== Задачи с одним станком ===
* [[1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]
* [[1sumwu|<tex> 1 \mid\mid \sum w_i U_i </tex>]]
* [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]]
* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]
* [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]
* [[1ripi1sumf|<tex>1 \mid r_i, p_i = 1 \mid \sum f_i</tex>]]
* [[1ripipsumwu|<tex> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>]]
* [[1ripmtnsumwc|<tex>1 \mid r_i, pmtn \mid \sum w_{i}C_{i}</tex>]]
* [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]
* [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]]

=== Специальные случаи задач для двух станков ===
* [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]
* [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]
* [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]]
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
* [[J2ni2Cmax|<tex>J2 \mid n_{i} \leqslant 2 \mid C_{max}</tex>]]
* [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]]

=== Задачи для произвольного числа станков ===
* [[Flow shop]]
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]
* [[PSumCi|<tex>P \mid \mid \sum C_{i}</tex>]]
* [[Pintreepi1Lmax|<tex>P \mid intree, p_{i} = 1 \mid L_{max}</tex>]]
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
* [[Ppi1sumwu|<tex>P \mid p_i=1 \mid \sum w_i U_i</tex>]]
* [[Ppi1riintegerLmax|<tex>P \mid p_i=1; r_i - integer \mid L_{max}</tex>]]
* [[RSumCi|<tex>R \mid \mid \sum C_i</tex>]]
* [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]]
* [[QpmtnSumCi|<tex> Q \mid pmtn \mid \sum C_i </tex>]]
* [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]]
* [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
* [[Opij1di|<tex>O \mid p_{ij} = 1, d_i \mid - </tex>]]
* [[Opij1sumwu|<tex> O \mid p_{i,j} = 1 \mid \sum w_{i} U_{i} </tex>]]
* [[Opij1SumTi|<tex> O \mid p_{i,j} = 1 \mid \sum T_{i} </tex>]]
* [[Opij1Cmax|<tex> O \mid p_{ij} = 1 \mid C_{max} </tex>]]
* [[Opij1Sumwc|<tex> O \mid p_{ij} = 1 \mid \sum w_i C_i </tex>]]