24
правки
Изменения
Конспект создан
<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>.
==См. также==
* [[Поток минимальной стоимости]]
* [[Методы решения задач теории расписаний]]
{{Задача
|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>.
==См. также==
* [[Поток минимальной стоимости]]
* [[Методы решения задач теории расписаний]]
