1679
правок
Изменения
→R || Sum(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> i </tex> на какую-то позицию <tex> k </tex> на машине <tex> j </tex>
Сведем задачу к задаче mincost-maxflow. Поместим в левую долю графа работы, в правую долю — пары из машины и позиции работы и проведем соответствующие ребра пропускной способности <tex>1</tex> и стоимости <tex>\frac{p_{i}}{v_{ij}}</tex>, соответствующие времени выполнения работы <tex>i</tex> на машине <tex>j</tex>. Проведем из стока в левую долю ребра стоимости <tex>0</tex> и пропускной способности <tex>1</tex>, из правой доли в сток — ребра пропускной способности <tex>n</tex> и стоимости <tex> 0 </tex>. Найдем в этой сети максимальный поток минимальной стоимости,
==== O | p_ij=1 | Sum(w_i C_i) ====
