| НЕТ ВОЙНЕ
|
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
Антивоенный комитет России
|
| Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
|
| meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.
|
[math]J2 \mid n_i \leqslant 2 \mid C_{max}[/math]
| Задача: |
Рассмотрим задачу:
- Дано [math]n[/math] работ и [math]2[/math] станка.
- Для каждой работы известно её время выполнения на каждом станке [math]p_{ij}[/math].
- Для каждой работы известна последовательность [math]O_{i1}, \ O_{i2} \ \ldots \ O_{ik}[/math] станков — порядок, в котором нужно выполнить работу.
- В каждой последовательности [math]O_{i}[/math] не более двух элементов.
Требуется минимизировать время окончания выполнения всех работ. |
Описание алгоритма
[math]M_{1}[/math] — первый станок. [math]M_{2}[/math] — второй станок.
Разобьем все работы на четыре множества:
- [math]I_{1}[/math] — множество всех работ, которые должны выполниться только на [math]M_{1}[/math].
- [math]I_{2}[/math] — множество всех работ, которые должны выполниться только на [math]M_{2}[/math].
- [math]I_{12}[/math] — множество всех работ, которые должны выполниться сначала на [math]M_{1}[/math] затем на [math]M_{2}[/math].
- [math]I_{21}[/math] — множество всех работ, которые должны выполниться сначала на [math]M_{2}[/math] затем на [math]M_{1}[/math].
Решим задачу [math]F2 \mid \mid C_{max}[/math] для [math]I_{12}[/math] и для [math]I_{21}[/math] независимо. Получим расписание [math]S_{12}[/math] и [math]S_{21}[/math].
Тогда оптимальное расписание для нашей задачи будет следующим:
- Расписание [math]M_{1}[/math]: сначала [math]I_{12}[/math] в соответсвии с расписанием [math]S_{12}[/math]. Затем [math]I_{1}[/math] в произвольном порядке. Затем [math]I_{21}[/math] в соответсвии с [math]S_{21}[/math].
- Расписание [math]M_{2}[/math]: сначала [math]I_{21}[/math] в соответсвии с расписанием [math]S_{21}[/math]. Затем [math]I_{2}[/math] в произвольном порядке. Затем [math]I_{12}[/math] в соответсвии с [math]S_{12}[/math].
Примечание: во время выполнения [math]I_{21}[/math] на [math]M_{1}[/math] или [math]I_{12}[/math] на [math]M_{2}[/math] могут возникнуть простои
из-за того, что работа ещё не выполнилась на предыдущем станке.
Доказательство корректности алгоритма
[math]T_{j}(x)[/math] — время выполнения множества работ [math]x[/math] на станке [math]j[/math].
[math]G_{j}[/math] — множество всех работ, которые нужно сделать хотя бы раз на [math]j[/math]-м станке, то есть [math]G_{1} = I_{1} \cup I_{12} \cup I_{21}[/math].
| Лемма: |
Расписание, построенное данным алгоритмом, обладает следующим свойством: один из станков работает без простоев. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Рассмотрим два случая:
- [math]T_{1}(I_{12}) + T_{1}(I_{1}) \geqslant T_{2}(I_{21}) [/math].
Тогда [math]M_{1}[/math] работает без прерываний, т.к к моменту завершения выполнения [math]I_{1}[/math] на [math] M_{1} [/math] все работы [math]I_{21}[/math] выполнены на [math]M_{2}[/math].
- [math]T_{1}(I_{12}) + T_{1}(I_{1}) \lt T_{2}(I_{21}) [/math].
Тогда [math]M_{2}[/math] работает без прерываний, т.к к моменту завершения выполнения [math]I_{2}[/math] на [math] M_{2} [/math] все работы [math]I_{12}[/math] выполнены на [math]M_{1}[/math] .
|
| [math]\triangleleft[/math] |
| Теорема: |
Расписание, построенное данным алгоритмом, является корректным и оптимальным. |
| Доказательство: |
| [math]\triangleright[/math] |
 Рис. 1 — Расположение работ. В серой области могут быть прерывания. Корректность алгоритма очевидна.
Докажем оптимальность.
Пусть, для опеределенности [math]M_{1}[/math] работает без прерываний.
Рассмотрим станок на котором достигается [math]C_{max}[/math] .
- Если это [math]M_{1}[/math], то оптимальность очевидна [math](C_{max} \geqslant \sum\limits_{i \in G_{1}} p_{i1})[/math].
- Иначе [math]C_{max}[/math] достигается на [math]M_{2}[/math].
Тогда либо [math]M_{2}[/math] работает без прерываний и оптимальность очевидна.
Или есть прерывания.
Тогда целевая функция равна ответу задачи [math]F2 \mid \mid C_{max}[/math] для работ [math]I_{21}[/math], который оптимален. |
| [math]\triangleleft[/math] |
Сложность алгоритма
Время работы алгоритма равно времени работы алгоритма [math]F2 \mid \mid C_{max}[/math], то есть [math]O(n\log n)[/math].
Источники информации
- Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 179 — 180 стр. — ISBN 978-3-540-69515-8
