Изменения

При сведении текущей задачи теории расписаний <tex> S </tex> к какой-то другой <tex> 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><ref>P. Brucker. Scheduling Algorithms (2006), 5th edition, p. 73 </ref>. Сведем нашу задачу <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>. Распишем по определению значение целевой функции для <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>, ч.т.д.

С помощью этого метода решаются:* Задачи класса [[Классификация задач|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} == R 1, r_i \mid C_{max} </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 161</ref>* Задачи класса [[Классификация задач|| Sum(C_i) ===Flow Shop]] при условии <tex>p_{ij}=1</tex> можно свести к задаче на одном станке:В этой задаче дано *:[[Fpij1sumwu|<tex> n F \mid p_{ij} = 1 \mid \sum w_i U_i </tex> работ и ]]* Часто в задачах, в которых допускаются прерывания, оптимальный ответ совпадает с соответствующими задачами без прерываний:*:<tex> m P \mid pmtn \mid \sum w_i C_i </tex> машин<ref>Peter Brucker «Scheduling Algorithms», fifth edition, причем для каждой машины длительность выполнения на ней Springer — с. 121</ref>*:[[Flow shop|<tex>iF2 \mid pmtn \mid C_{max} </tex>-й работы своя и равна ]]* Ряд задач можно свести к задаче поиска максимального потока:*:<tex> p_Q \mid pmtn, r_i\mid L_{ijmax} </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> j </tex>== Построение расписания по нижней оценке ==Этот метод обычно применим к задачам, пусть на ней выполняется в которых целевая функция — <tex>n_jC_{max}</tex> работ. Тогда вклад этой машины Обычно построение расписания по нижней оценке происходит в целевую функцию (не теряя общности, пронумеруем работы два этапа:# Построение некоторого набора нижних ограничений на этой машине от произвольное расписание для задачи <tex>1 S </tex> до <tex>n_j</tex>) рассчитывается как:. # Построение произвольного допустимого расписания, достигающего максимального ограничения из построенного набора.

С помощью этого метода решаются следующие задачи:* <tex> P \summid pmtn \limits_mid C_{i=1max}^{n_j} (p_ij + </tex> <ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 108</ref>* [[RpmtnCmax|<tex> R \summid pmtn \limits_mid C_{q=1max}^</tex>]]* [[Opij1Cmax|<tex> O \mid p_{i-1ij} p_qj) = n_j p_{1j} + (n_j - 1) p_\mid C_{2jmax} + </tex>]]* [[QpmtnCmax|<tex> Q \dots + 2 p_{(n_j-1)j} + p_mid pmtn \mid C_{n_jjmax} </tex>]]

ЗаметимНиже будет рассмотрен частный пример решения задачи подобным образом:=== P | pmtn | C_max ==={{Задача|definition = Имеется <tex>m</tex> однородных машин, что в каждом работающих параллельно, и <tex>n</tex> работ, которые могут быть прерваны и продолжены позже. Необходимо минимизировать время выполнения всех работ}} Найдем набор ограничений на значение <tex> C_{max} </tex> для произвольного допустимого расписания <tex> S </tex> : # В допустимом расписании перед каждой работой окажется коэффициент выполнение всех работ не может завершиться раньше одной из них, поэтому <tex> k C_{max} \geqslant p_i </tex>.# Если все станки работали время <tex> C_{max} </tex>, означающий, что соответствующая работа выпллняется на них могло выполниться не больше <tex> k C_{max} \cdot m </tex>-й с конца. Понятноработы, что в различных расписаниях то есть <tex> k \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 \cdots n} p_i,~ \dfrac1m \sum\limits_{i=1}^np_i \right)} </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>1C_{max} </tex>часть на следующую машину. Найдем в этой сети максимальный поток минимальной стоимости. УтверждаетсяБлагодаря первому ограничению никакая работа не будет выполняться одновременно на двух станках, что если ребро <tex> i \to (jа благодаря второму — не останется работы, k) </tex> насыщено потоком, то работа <tex> i </tex> в оптимальном расписании должна стоять на машине <tex> j </tex> в позиции <tex> k </tex> с концакоторую мы не сможем выполнить.

# Целевые функции задачи mincost-maxflow и текущей задачи совпадают, так как у ребер между долями пропускная способность 1, а у дополнительных ребер из истока и в сток нулевая стоимость, и они не могут внести вклад в целевую функцию.# Расписание, построенное == Бинарный поиск по вышепредставленному способу действительно будет допустимым.ответу ==## Благодаря ограничениям на поток, входящий в левую долю, каждая работа будет назначена только один раз.## Благодаря ограничениям на поток, выходящий из правой доли, на каждую позицию будет назначено не более одной работы.## Докажем, что не возникает ситуации такой, что существует такая позиция <tex> l </tex>Этот способ часто подходит для задач, что в этой позиции с конца стоит какая-то работа, а в позиции которых надо минимизировать <tex> l - 1 C_{max} </tex> с конца — нет (это противоречит определению <tex>l</tex>-й с конца работыесли мы умеем решать соответствующую задачу существования расписания). Такая ситуация означает, что ребро реже для <tex> i \to (j, l) sum w_i U_i </tex> оказалось насышено потоком, а ребро <tex>i \to (j, l - 1) </tex> — не насыщено. Но стоимость ребра <tex> i \to (jВажно помнить, l - 1) что если требуется полиномиальное по </tex> меньше стоимости ребра <tex> i \to (j, l) n </tex>решение, поэтому можем переместить поток с ребра <tex> i \to (jоно не должно зависеть от логарифма ответа, l) </tex> на ребро но иногда ответ ограничен полиномом от <tex> i \to (j, l - 1) n</tex>, не нарушив свойства потока и улучшив целевую функцию, что противоречит оптимальности ответа для mincost-maxflow. Следовательно, такой позиции не возникнет и расписание будет допустимыммы можем применить этот метод.

==== O | p_ij=1 | Sum(w_i C_i) ====Докажем, что оптимальный ответ для <tex> S </tex> равен оптимальному ответу к задаче <tex>S' = P \mid p_i=m, pmtn \mid \sum w_i C_i </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[[QpmtnriLmax|</tex> цветов, из теории графов известно, что это можно сделать.## Назначим выполнение единичного элемента работы <tex>i</tex> в момент времени <tex>t</tex> на машине <tex>k</tex>, если соответствующее ребро раскрашено в цвет <tex>k</tex>.## После данного преобразования мы не изменим значение целевой функции (так как мы переставляем только элементы работ, выполняющихся в один и тот же момент времени). Также расписание станет допустимым для <tex> S </tex>, так как по определению реберной раскраски, не будет ни одной работы, два единичных блока которых выполняется на одной машине и во все моменты времени не окажется того, что на одну машину назначено две работы.Чтобы непосредственно решить эту задачу, воспользуемся теоремой о том, что для задачи <tex> P Q \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 r_i \mid p_{ij}=1 \mid C_L_{max}</tex>, чтобы получить допустимое расписание, можно не строить раскраску графа, а просто циклически сдвигать последовательности работ внутри каждого блока, что позволяет достичь асимптотики <tex> O(m n) </tex>.]]

Метод сведения задачи к задаче на параллельных машинах также работает для некоторых других open-shop задач. == Построение Жадное построение расписания по нижней оценке ==Этот метод обычно применим к задачамДля решения задач теории расписаний часто применяется [[Определение матроида|теория матроидо]]в, а в которых целевая функция — <tex> C_{max}</tex>. Построим какойчастности — [[Теорема Радо-то набор нижних ограничений Эдмондса (жадный алгоритм)|жадный алгоритм]]: алгоритм решения задач путем выбора локально оптимальных решений на произвольное расписание для задачи <tex> S </tex> и возьмем из них максимальноекаждом этапе алгоритма. Затем построим произвольное допустимое расписаниеЕстественно, достигающее этой оценкидалеко не все оптимизационные задачи можно решать жадно — для этого сначала необходимо доказать оптимальность жадного выбора.

* [[Правило Лаулера|<tex> P 1 \mid pmtn prec \mid C_f_{max}</tex>]]* [[1outtreesumwc|<tex> R 1 \mid pmtn outtree \mid C_{max}\sum w_i C_i </tex>]]* [[1pi1sumwu|<tex> O 1 \mid p_{ij}p_i =1 \mid C_{max}</tex> === Примеры ======= P | pmtn | C_max ====# В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому <tex> T \ge p_i </tex>.# Если все станки работали время <tex> T </tex>, на них могло выполниться не больше <tex> Tm </tex> работы, то есть <tex> \sum\limits_i p_i \le Tm w_i U_i </tex> и <tex> T \ge \frac1m \sum\limits_i p_i </tex>.]]# Тогда * [[1sumu|<tex> T_{min} = 1 \max {(mid \max\limits_i p_i, \frac1m mid \sum\limits_i p_i)} </tex>.Построим расписание, подходящее под эту границу: будем по очереди заполнять машины работами в произвольном порядке, и если очередная работа не помещается на текущей машине полностью, перенесем ее выходящую за <tex> T_{min} </tex> часть на следующую машину. Благодаря первому ограничению никакая работа не будет выполняться одновременно на двух станках, а благодаря второму — не останется работы, которую мы не сможем выполнить. ==== O | p_ij=1 | C_max ====# В допустимом расписании на каждом станке надо обработать каждую работу, поэтому <tex> T \ge n </tex>.# В допустимом расписании каждую работу нужно обработать на всех станках, причем ее нельзя обрабатывать на двух станках одновременно, поэтому <tex> T \ge m </tex>.# Тогда <tex> T_{min} = \max {(m, n)} </tex>Оптимальное расписание получается циклическими сдвигами последовательности <tex> 1 \dots n </tex> и выглядит следующим образом:* Для <tex> n < m U_i </tex>: '''0 1 2 ... n-1 n n+1 ... m-1 m''' '''M_1''' 1 2 3 ... n-1 n - ... - - '''M_2''' - 1 2 ... n-2 n-1 n ... - - '''.''' ... ... ... ... ... ... ... ... ... ... '''M_m-1''' - - - ... ... ... ... ... n - '''M_m''' - - - ... ... ... ... ... n-1 n* Для <tex> n \ge m </tex>: '''0 1 2 ... 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> \sum w_i U_i </tex>. Важно помнить, что если требуется полиномиальное по <tex> n </tex> решение, оно не должно зависеть от логарифма ответа, но иногда ответ ограничен полиномом от <tex>n</tex> (в частности, в <tex> \sum U_i </tex>), и мы можем применить этот метод.=== Примеры ======= O | p_ij = 1| Sum(U_i) ====Перенумеруем работы по возрастанию их дедлайнов, то есть <tex> d_1 \le d_2 \le \dots d_n </tex>.{{Утверждение|statement=Если мы можем выполнить <tex> k </tex> каких-то работ, мы можем выполнить <tex> k </tex> последних работ.|proof=Действительно, если в допустимом расписании все периоды выполнения <tex> t_{iq} </tex> работы <tex> i </tex> заменить на периоды выполнения работы <tex> j > i </tex>, оно останется допустимым, так как <tex> t_{iq} \le d_i \le d_j </tex>.}}Таким образом, будем брать последние <tex> k </tex> работ и пытаться составить из них допустимое расписание (для этого известен полиномиальный алгоритм за <tex> O(mn) </tex><ref>P. Brucker. Scheduling Algorithms (2006), 5th edition, p. 163 </ref>). Получили решение за <tex> O(mn\log n ) </tex>. == Жадное построение расписания =={{Определение|definition='''Жадный алгоритм''' — алгоритм, в котором локальные оптимизации решения достигают глобального оптимума.}} Естественно, далеко не все оптимизационные задачи можно решать жадно — для этого сначала необходимо доказать Обычно оптимальность жадного выбора. Обычно это делают доказывают двумя способами:

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

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

Если такой способ найден, получаем, что какой-то последовательностью модификаций <tex> O \to O_t' \to \dots \to O_1' \to S </tex> получим <tex> f(S) \le leqslant f(O_1') \le leqslant \dots \le leqslant f(O_t') \le 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> используется отношение «время последнего прерывания больше или количество прерываний меньше».  === Примеры ======= 1 | prec | f_max ====Дано множество работ <tex> J </tex> размера <tex> n </tex>, для которых заданы отношения предшествования, нужно минимизировать <tex> f_{max} = \max\limits_i f_i(C_i) </tex>, где <tex> f_i</tex> — монотонно неубывают по времени завершения работы <tex> i </tex>. Приведем алгоритм(''Lawler's algorithm'') решения за <tex> O(n^2) </tex> и докажем его оптимальность:# Пусть <tex> U \subseteq J </tex> — множество еще не назначенных работ. Пусть <tex> p(U) = \sum\limits_{i \in U} p_i </tex>.# Назначим работу <tex> j \in U </tex>, у которой нет потомков в <tex> U </tex> и с минимальным значением <tex> f_j(p(U)) </tex> последней работой в <tex> U </tex>. {{Теорема|statement=Предложенный алгоритм оптимален.|proof=Не теряя общности, пронумеруем работы в расписании, построенном нашим алгоритмом, от <tex> 1 </tex> до <tex> n </tex>. Пусть <tex> \pi(1) \dots \pi(n) </tex> — оптимальная последовательность работ такая, что наибольший общий суффикс их расписаний — максимален (пусть они впервые различаются в позиции <tex> r </tex>). Получили, следующую ситуацию:

pi: Отношение «более похоже» должно быть [[Отношение порядка | отношением частичного строгого порядка]].Часто в качестве него можно выбрать отношение «длина наибольшего общего префикса решения <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> используется отношение «время последнего прерывания больше или количество прерываний меньше»... r-1 k .... j r r+1 ... n

Докажем, что можно привести это расписание к оптимальному расписанию с большим общим суффиксом== См. Заметим, что если выполнить работу r-1 прямо перед r, расписание все еще будет допустимым (несмотря на еще не доказанную оптимальность, наш алгоритм строит только допустимые расписания, а в построенном нами расписании r-1 стояло прямо перед r)также. По оптимальному расписанию j выполняется непосредственно перед r. Таким образом, у работ j и r нет ни одного потомка в можестве работ 1, 2.. r-2, r-1. По построенной нашим алгоритмом последовательности 1..n мы получаем, что ==* [[Правило Лаулера]]* [[Flow shop]]* [[Opi1sumu|<tex> f_{r-1}(\sumO \limits_mid p_{iij}^{r-= 1} p_i) \le f_j(mid \sum\limits_{i}^{r-1}) U_i</tex> (иначе мы бы поставили последней на тот момент работу j, а не r). Сдвинем в последовательности <tex> \pi </tex> работы k .. j влево на одну позицию, а работу r-1 поместим перед r. Так как после сдвига влево, <tex>f_k \dots f_j </tex> не могли увеличиться, максимум так же не мог увеличиться. Следовательно, оптимальная последовательность <tex> \pi </tex> имела не самый длинный общий суффикс, что противоречит её выбору.}}]]

== Источники информации ==* Peter Brucker «Scheduling Algorithms», fifth edition, Springer ISBN 978-3-540-69515-8 [[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]