Изменения

Заметим, что в каждом допустимом расписании перед каждой работой окажется коэффициент <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>\frac{k p_{i}}{v_{ij}}</tex>, соответствующие времени выполнения вкладу работы в целевую функцию, если она окажется в позиции <tex>ik </tex> с конца на машине <tex>j</tex>. Проведем из стока в левую долю ребра стоимости <tex>0</tex> и пропускной способности <tex>1</tex>, из правой доли в сток — также ребра пропускной способности стоимости <tex>n0 </tex> и стоимости пропускной способности <tex> 0 1</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 </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. Следовательно, такой позиции не возникнет и расписание будет допустимым.