Изменения

При сведении текущей задачи теории расписаний <tex> S </tex> к какой-то другой <tex> S' </tex> (не обязательно задаче теории расписаний) необходимо доказать два пункта:# Допустимость расписания, построенного с помощью задачи <tex> P S' </tex>, или существование способа его трансформации в допустимоебез нарушения оптимальности.# Следствие того, что если мы оптимизируем <tex> S' </tex>, мы также оптимизируем ответ для <tex> S </tex> (обратное в общем случае неверно).'''Примечание — если ''': если требуется полиномиальное время для решения задачи, требуется, чтобы сведение к другой задаче и трансформация расписания в допустимое также происходили должны происходить за полиномиальное время.=== Примеры ======= 1 | intree | Sum(w_i C_i) ====Предположим, что мы уже умеем решать задачу <tex> S' = 1 \mid outtree \mid \sum w_i C_i </tex>. Сведем нашу задачу <tex> S </tex> к ней следующим образом:* Развернем все ребра, теперь если работа <tex> i </tex> зависела от работы <tex> j </tex>, работа <tex> j </tex> будет зависеть от <tex> i </tex>.* Заменим все стоимости <tex> w_i </tex> на противоположные <tex> w'_i = - w_i</tex>.Утверждается, что решив соответствующую задачу <tex> S' </tex> и развернув полученное расписание, мы получим ответ для текущей задачи.# Полученное расписание будет допустимым, так как расписание для <tex> S' </tex> было допустимым, и в нем никакие две работы не пересекались и не прерывались. Развернув, мы не могли нарушить это свойство. Также из-за того, что мы развернули расписание, мы добились того, что все работы выполняются в правильном порядке (в расписании для <tex> S' </tex> из-за того, что расписание было развернуто, порядок был нарушен для всех работ). Таким образом, получили что расписание — допустимое.# Пусть с помощью задачи <tex> S' </tex> мы получили последовательность работ <tex> 1 \dots n </tex> (не теряя общности, занумеруем их от 1 до n). Распишем по определению значение целевой функции для <tex> S </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' </tex> также минимизирует <tex> S </tex>, ч.т.д.==== R || Sum(C_i) ====

С помощью этого метода решаются:* Задачи класса [[Классификация задач|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}= O 1</tex> можно свести к задаче на одном станке:*:[[Fpij1sumwu| p_ij<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| Sum(<tex> 1 \mid intree \mid \sum w_i C_i) ====</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} = P | pmtn | C_max ==\max {\left( \max\limits_{i=1 \cdots n} p_i,~ \dfrac1m \sum\limits_{i=1}^n p_i \right)} </tex>.

=== Примеры ===Этот способ часто подходит для задач, в которых надо минимизировать <tex>C_{max} </tex> (если мы умеем решать соответствующую задачу существования расписания), реже для <tex> \sum w_i U_i </tex>. Важно помнить, что если требуется полиномиальное по <tex> n </tex> решение, оно не должно зависеть от логарифма ответа, но иногда ответ ограничен полиномом от <tex>n</tex>, и мы можем применить этот метод. Примером решения задач подобным методом служит следующая задача:==== O [[QpmtnriLmax| p_ij = 1<tex> Q \mid pmtn, d_i | - ====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> наблюдается глобальный минимум». ===Правильно === 1 При доказательстве оптимательности применима стратегия '''аргумент замены''' (англ. ''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>. Отношение «более похоже» должно быть [[Отношение порядка | prec отношением частичного строгого порядка]]. Часто в качестве него можно выбрать отношение «длина наибольшего общего префикса решения <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| f_max <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