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

1p1sumu

2016-06-08T11:15:37Z

85.114.2.247: /* Алгоритм */

<tex dpi = "200" >1 \mid p_i=1\mid \sum U_i</tex>

{{Шаблон:Задача
|definition =
Дан один станок и <tex>n</tex> работ, для которых заданы их дедлайны <tex>d_i</tex>, а все времена выполнения на этом станке <tex>p_i = 1</tex>. Нужно успеть выполнить как можно больше работ.
}}

==Алгоритм==
Чтобы получить оптимальное расписание, будем строить максимальное множество <tex>S</tex> тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из <tex>S</tex>, упорядоченных по неубыванию дедлайнов.
Будем добавлять в <tex>S</tex> работы в порядке неубывания значений <tex>d_j</tex>, если успеваем их выполнить.

Отсортировать работы так, чтобы <tex>d_1 \leqslant d_2 \leqslant \dots \leqslant d_n</tex>
<tex>S = \varnothing</tex>
<tex>time = 0</tex>
'''for''' i = 1 '''to''' n '''do'''
<tex>d_i = \min\{d_i, n\}</tex>
'''for''' i = 1 '''to''' n '''do'''
'''if''' <tex>time < d_i</tex>
<tex>S = S \cup \{ i \}</tex>
<tex>time</tex> <code>+=</code> <tex>1</tex>

Cортировку работ по неубыванию дедлайнов осуществляем с помощью сортировки подсчетом за <tex>O(n)</tex>, а значит и весь алгоритм будет работать за <tex>O(n)</tex>.
Во время сортировки стоит учитывать, что дедлайны могут значительно превосходить количество задач. В таком случае необходимо предварительно пересчитать дедлайны по формуле <tex>d_i = \min\{d_i, n\}</tex> (в оптимальном расписании мы не выполняем работы позже времени <tex>t=n</tex>).

В результате выполнения данного алгоритма будет получено корректное расписание, в котором каждая работа встречается не более одного раза. Оптимальность полученного расписания доказывается аналогично [[1sumwu|<tex>1 \mid \mid \sum w_{i}U_{i}</tex>]].

== См. также ==
* [[Классификация задач]]
* [[1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]
* [[1sumwu|<tex>1 \mid \mid \sum w_{i}U_{i}</tex>]]

==Источники информации==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 86 стр. {{---}} ISBN 978-3-540-69515-8

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

1p1sumu

2016-06-08T11:05:48Z

85.114.2.247:

<tex dpi = "200" >1 \mid p_i=1\mid \sum U_i</tex>

{{Шаблон:Задача
|definition =
Дан один станок и <tex>n</tex> работ, для которых заданы их дедлайны <tex>d_i</tex>, а все времена выполнения на этом станке <tex>p_i = 1</tex>. Нужно успеть выполнить как можно больше работ.
}}

==Алгоритм==
Чтобы получить оптимальное расписание, будем строить максимальное множество <tex>S</tex> тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из <tex>S</tex>, упорядоченных по неубыванию дедлайнов.
Будем добавлять в <tex>S</tex> работы в порядке неубывания значений <tex>d_j</tex>, если успеваем их выполнить.

Отсортировать работы так, чтобы <tex>d_1 \leqslant d_2 \leqslant \dots \leqslant d_n</tex>
<tex>S = \varnothing</tex>
<tex>time = 0</tex>
'''for''' i = 1 '''to''' n '''do'''
'''if''' <tex>time < d_i</tex>
<tex>S = S \cup \{ i \}</tex>
<tex>time</tex> <code>+=</code> <tex>1</tex>

Cортировку работ по неубыванию дедлайнов осуществляем с помощью сортировки подсчетом за <tex>O(n)</tex>, а значит и весь алгоритм будет работать за <tex>O(n)</tex>.

В результате выполнения данного алгоритма будет получено корректное расписание, в котором каждая работа встречается не более одного раза. Оптимальность полученного расписания доказывается аналогично [[1sumwu|<tex>1 \mid \mid \sum w_{i}U_{i}</tex>]].

== См. также ==
* [[Классификация задач]]
* [[1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]
* [[1sumwu|<tex>1 \mid \mid \sum w_{i}U_{i}</tex>]]

==Источники информации==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 86 стр. {{---}} ISBN 978-3-540-69515-8

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

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

2016-06-08T10:59:07Z

85.114.2.247:

== Сведение к другой задаче ==
При сведении текущей задачи теории расписаний <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>
* [[RpmtnCmax|<tex> R \mid pmtn \mid C_{max}</tex>]]
* [[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

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

RpmtnCmax

2016-06-08T10:55:46Z

85.114.2.247:

<tex dpi = "200" >R \mid pmtn \mid C_{max}</tex>

{{Задача
|definition =
Имеется <tex>m</tex> машин, работающих параллельно. Есть <tex>n</tex> работ, причем для каждого станка длительность выполнения на нем <tex>i</tex>-й работы составляет <tex> p_{ij} </tex>. Работа может быть прервана и продолжена позже.

Необходимо составить такое расписание, чтобы значение <tex>C_{max} = \max\limits_{i=1\ldots n} C_i</tex> было минимальным.}}

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

Будет строить расписание по нижней оценке.

Вычислим для каждой работы время <tex>t_{ij}</tex>, которое работа <tex>i</tex> будет выполняться на <tex>j</tex>-ом станке в оптимальном расписании.

Пусть <tex>\dfrac {t_{ij} } {p_{ij}} </tex> {{---}} часть времени, которое работа <tex>i</tex> будет выполняться на <tex>j</tex>-ом станке. Тогда <tex> \sum\limits_{j=1}^m \dfrac {t_{ij} } {p_{ij}} = 1</tex> верно, если работа завершена.

Теперь оптимальное расписание должно удовлетворять следующим условиям:
# <tex> \sum\limits_{j=1}^m \dfrac {t_{ij} } {p_{ij}} = 1, \quad i = 1,\ldots, n</tex>
# <tex> \sum\limits_{j=1}^m t_{ij} \leqslant C_{max}, \quad i = 1,\ldots, n</tex>
# <tex> \sum\limits_{i=1}^n t_{ij} \leqslant C_{max}, \quad j = 1,\ldots, m</tex>
# <tex> t_{ij} \geqslant 0, \quad i = 1,\ldots, n; j = 1,\ldots, m</tex>

Обозначим нижнюю оценку как <tex>LB = \max\{\max\limits_{i=1}^n \sum\limits_{j=1}^m t_{ij}, \sum\limits_{i=1}^n t_{ij}\} </tex>.

Можем получить ответ на задачу за <tex>O(n)</tex>. Расписание, удовлетворяющее этой оценке строится аналогично <tex>O \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 15-17</ref> за полиномиальное время.

== См. также ==
* [[Классификация задач]]
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]

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

==Источники информации==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 137-139 стр. {{---}} ISBN 978-3-540-69515-8

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

RpmtnCmax

2016-06-08T10:50:56Z

85.114.2.247:

<tex dpi = "200" >R \mid pmtn \mid C_{max}</tex>

{{Задача
|definition =
Имеется <tex>m</tex> машин, работающих параллельно. Есть <tex>n</tex> работ, причем для каждого станка длительность выполнения на нем <tex>i</tex>-й работы составляет <tex> p_{ij} </tex>. Работа может быть прервана и продолжена позже.

Необходимо составить такое расписание, чтобы значение <tex>C_{max} = \max\limits_{i=1\ldots n} C_i</tex> было минимальным.}}

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

Будет строить расписание по нижней оценке.

Вычислим для каждой работы время <tex>t_{ij}</tex>, которое работа <tex>i</tex> будет выполняться на <tex>j</tex>-ом станке в оптимальном расписании.

Пусть <tex>t_{ij}/p_{ij}</tex> {{---}} часть времени, которое работа <tex>i</tex> будет выполняться на <tex>j</tex>-ом станке. Тогда <tex> \sum\limits_{j=1}^m t_{ij}/p_{ij} = 1</tex> верно, если работа завершена.

Теперь оптимальное расписание должно удовлетворять следующим условиям:
# <tex> \sum\limits_{j=1}^m t_{ij}/p_{ij} = 1, \quad i = 1,\ldots, n</tex>
# <tex> \sum\limits_{j=1}^m t_{ij} \leqslant C_{max}, \quad i = 1,\ldots, n</tex>
# <tex> \sum\limits_{i=1}^n t_{ij} \leqslant C_{max}, \quad j = 1,\ldots, m</tex>
# <tex> t_{ij} \geqslant 0, \quad i = 1,\ldots, n; j = 1,\ldots, m</tex>

Обозначим нижнюю оценку как <tex>LB = \max\{\max\limits_{i=1}^n \sum\limits_{j=1}^m t_{ij}, \sum\limits_{i=1}^n t_{ij}\} </tex>.

Можем получить ответ на задачу за <tex>O(n)</tex>. Расписание, удовлетворяющее этой оценке строится аналогично <tex>O \mid pmtn \mid C_{max}</tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 15-17</ref> за полиномиальное время.

== См. также ==
* [[Классификация задач]]
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]

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

==Источники информации==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 137-139 стр. {{---}} ISBN 978-3-540-69515-8

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