Изменения

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

<tex> \sum\limits_{i=1}^{n_j} \left(p_ij + \sum\limits_{q=1}^{i-1} p_qj\right) = n_j p_{1j} + (n_j - 1) p_{2j} + \dots + 2 p_{(n_j-1)j} + p_{n_jj} </tex>

Сведем задачу к назначению каждой работы <tex> i </tex> позиции с конца <tex> k </tex> на станке <tex> j </tex> с помощью задачи алгоритма [[Поток минимальной стоимости | mincost-maxflowпоиска максимального потока минимальной стоимости]]. Поместим в левую долю графа работы, в правую долю — пары из станка и коэффициента и проведем соответствующие ребра пропускной способности <tex>1</tex> и стоимости <tex>k \cdot p_{ij}</tex>, соответствующие вкладу работы в целевую функцию, если она окажется в позиции <tex> k </tex> с конца на станке <tex> j </tex>. Проведем из стока в левую долю ребра стоимости <tex>0</tex> и пропускной способности <tex>1</tex>, из правой доли в сток — также ребра стоимости <tex> 0 </tex> и пропускной способности <tex>1</tex>. Максимальный поток минимальной стоймости в построенной сети будет ответом на исходную задачу.

# Целевые функции задачи mincost-maxflow и Целевя функция текущей задачи совпадаютсовпадает со стомостью максимального потока в построенной сети, так как у ребер между долями пропускная способность 1, а у дополнительных ребер из истока и в сток нулевая стоимость, и они не могут внести вклад в целевую функцию.

Время выполнения mincost-maxflow алгоритма поиска максимального потока минимальной стоймости равно <tex> \mathcal{O}(V \cdot E^2) </tex>. Количество вершин в получаемой сети равно <tex> \mathcal{O}(m \cdot n) </tex>. Количество ребер в сети равно <tex> \mathcal{O}(m \cdot n^2) </tex>. СледственноСледовательно, ассимптотика алгоритма равна <tex> \mathcal{O}(m^3 \cdot n^5) </tex>.