1679
правок
Изменения
→Сведение к другой задаче
При сведении текущей задачи теории расписаний <tex> S </tex> к какой-то другой <tex> S' </tex>(не обязательно задаче теории расписаний) необходимо доказать два пункта:
# Допустимость расписания, построенного с помощью задачи <tex> S' </tex>, или существование способа его трансформации в допустимое без нарушения оптимальности.
# Следствие того, что если мы оптимизируем <tex> S' </tex>, мы также оптимизируем ответ для <tex> S </tex> (обратное в общем случае неверно).
Примечание — если требуется полиномиальное время для решения задачи, требуется, чтобы сведение к другой задаче и трансформация расписания в допустимое также происходили за полиномиальное время.
* Задачи класса Open Shop при условии <tex>p_{ij}=1</tex>, сводятся к задачам равной длительности на параллельных станках.
* Задачи класса Flow Shop при условии <tex>p_{ij}=1</tex>, сводятся к задаче на одном станке.
* Часто в задачах, в которых допускаются прерывания, оптимальный ответ совпадает с соответствующими задачами без прерываний:
** <tex> P \mid pmtn \mid \sum w_i C_i </tex>
** <tex> F2 \mid pmtn \mid C_{max} </tex>
=== Примеры ===
==== 1 | intree | Sum(w_i C_i) ====
==== R || Sum(C_i) ====
В этой задаче дано <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>. Найдем в этой сети максимальный поток минимальной стоимости. Утверждается, что если ребро <tex> i \to (j, k) </tex> насыщено потоком, то работа <tex> i </tex> в оптимальном расписании должна стоять на машине станке <tex> j </tex> в позиции <tex> k </tex> с конца.
# Целевые функции задачи mincost-maxflow и текущей задачи совпадают, так как у ребер между долями пропускная способность 1, а у дополнительных ребер из истока и в сток нулевая стоимость, и они не могут внести вклад в целевую функцию.
Докажем, что оптимальный ответ для <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</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 n) </tex>. Метод сведения задачи к задаче на параллельных машинах также работает для некоторых других open-shop задач.
== Построение расписания по нижней оценке ==
