RSumCi

[math]R \mid \mid \sum C_i[/math]

Задача:

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

Алгоритм

Описание алгоритма

Рассмотрим произвольное допустимое расписание для этой задачи. Рассмотрим какую-то станок [math] j [/math], пусть на нем выполняется [math]n_j[/math] работ. Тогда вклад этого станка в целевую функцию (не теряя общности, пронумеруем работы на этом станке от [math]1 [/math] до [math]n_j[/math]) рассчитывается как:

[math] \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} [/math]

Заметим, что в каждом допустимом расписании перед каждой работой окажется коэффициент [math] k [/math], означающий, что соответствующая работа выпллняется [math] k [/math]-й с конца. Понятно, что в различных расписаниях [math] k [/math] может принимать значения от [math]1[/math] до [math]n[/math].

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

Утверждение:

Eсли ребро [math] i \to (j, k) [/math] насыщено потоком, то работа [math] i [/math] в оптимальном расписании должна стоять на станке [math] j [/math] в позиции [math] k [/math] с конца.

[math]\triangleright[/math]

Целевые функции задачи mincost-maxflow и текущей задачи совпадают, так как у ребер между долями пропускная способность 1, а у дополнительных ребер из истока и в сток нулевая стоимость, и они не могут внести вклад в целевую функцию. Расписание, построенное по вышепредставленному способу действительно будет допустимым. Благодаря ограничениям на поток, входящий в левую долю, каждая работа будет назначена только один раз. Благодаря ограничениям на поток, выходящий из правой доли, на каждую позицию будет назначено не более одной работы. Докажем, что не возникает ситуации такой, что существует такая позиция [math] l [/math], что в этой позиции с конца стоит какая-то работа, а в позиции [math] l - 1 [/math] с конца — нет (это противоречит определению [math]l[/math]-й с конца работы). Такая ситуация означает, что ребро [math] i \to (j, l) [/math] оказалось насышено потоком, а ребро [math]i \to (j, l - 1) [/math] — не насыщено. Но стоимость ребра [math] i \to (j, l - 1) [/math] меньше стоимости ребра [math] i \to (j, l) [/math], поэтому можем переместить поток с ребра [math] i \to (j, l) [/math] на ребро [math] i \to (j, l - 1) [/math], не нарушив свойства потока и улучшив целевую функцию, что противоречит оптимальности ответа для mincost-maxflow. Следовательно, такой позиции не возникнет и расписание будет допустимым.

[math]\triangleleft[/math]

Время выполнения

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

См. также

• Поток минимальной стоимости
• Методы решения задач теории расписаний