RSumCi

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

[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} \left( p_{ij} + \sum\limits_{q=1}^{i-1} p_{qj} \right) = n_j \cdot p_{1j} + (n_j - 1) \cdot 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] с помощью алгоритма поиска максимального потока минимальной стоимости. Поместим в левую долю графа работы, в правую долю — пары из станка и коэффициента и проведем соответствующие ребра пропускной способности [math]1[/math] и стоимости [math]k \cdot 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]

Целевя функция текущей задачи совпадает со стомостью максимального потока в построенной сети, так как у ребер между долями пропускная способность 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]

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

Время выполнения алгоритма поиска максимального потока минимальной стоймости равно [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].

См. также

• Поток минимальной стоимости
• Методы решения задач теории расписаний
• [math]P \mid \mid \sum C_i[/math]
• [math]Q \mid \mid \sum C_i[/math]