|
|
| Строка 1: |
Строка 1: |
| − | {| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
| |
| − | |+
| |
| − | |-align="center"
| |
| − | |'''НЕТ ВОЙНЕ'''
| |
| − | |-style="font-size: 16px;"
| |
| − | |
| |
| − | 24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
| |
| − |
| |
| − | Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
| |
| − |
| |
| − | Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
| |
| − |
| |
| − | Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
| |
| − |
| |
| − | ''Антивоенный комитет России''
| |
| − | |-style="font-size: 16px;"
| |
| − | |Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
| |
| − | |-style="font-size: 16px;"
| |
| − | |[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
| |
| − | |}
| |
| − |
| |
| | <tex dpi = "200">O \mid p_{ij} = 1 \mid C_{max}</tex> | | <tex dpi = "200">O \mid p_{ij} = 1 \mid C_{max}</tex> |
| | {{Задача | | {{Задача |
Текущая версия на 19:26, 4 сентября 2022
[math]O \mid p_{ij} = 1 \mid C_{max}[/math]
| Задача: |
| Дано [math]m[/math] одинаковых станков, которые работают параллельно и [math]n[/math] работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно 1. Необходимо минимизировать время выполнения всех работ. |
Алгоритм
Описание алгоритма
Минимальное значение [math] C_{max} [/math] упирается в следующие ограничения:
- В допустимом расписании на каждом станке надо обработать каждую работу, поэтому [math] C_{max} \geqslant n [/math].
- В допустимом расписании каждую работу нужно обработать на всех станках, причем ее нельзя обрабатывать на двух станках одновременно, поэтому [math] C_{max} \geqslant m [/math].
Тогда [math] C_{max} = \max{(m, n)} [/math].
В случае [math] n \geqslant m [/math] оптимальное расписание строится циклическими сдвигами последовательности [math] 1 \dots n [/math] и выглядит следующим образом:
|
|
[math]\textbf1[/math] |
[math]\textbf2[/math] |
[math]\textbf3[/math] |
[math]\bf{\cdots}[/math] |
[math]\textbf{n - 1}[/math] |
[math]\textbf{n}[/math]
|
| [math]\bf{M_1}[/math]
|
[math]1[/math] |
[math]2[/math] |
[math]3[/math] |
[math]\cdots[/math] |
[math]n - 1[/math] |
[math]n[/math]
|
| [math]\bf{M_2}[/math]
|
[math]n[/math] |
[math]1[/math] |
[math]2[/math] |
[math]\cdots[/math] |
[math]n - 2[/math] |
[math]n - 1[/math]
|
| [math]\bf{M_3}[/math]
|
[math]n - 1[/math] |
[math]n[/math] |
[math]1[/math] |
[math]\cdots[/math] |
[math]n - 3[/math] |
[math]n - 2[/math]
|
| [math]\bf{\vdots}[/math]
|
[math]\vdots[/math] |
[math]\vdots[/math] |
[math]\vdots[/math] |
[math]\ddots[/math] |
[math]\vdots[/math] |
[math]\vdots[/math]
|
| [math]\bf{M_m}[/math]
|
[math]n - m + 2[/math] |
[math]n - m + 3[/math] |
[math]n - m + 4[/math] |
[math]\cdots[/math] |
[math]n - m[/math] |
[math]n - m + 1[/math]
|
Если же [math] n \lt m [/math], добавим [math] m - n [/math] фиктивных работ с номерами [math] n + 1 \dots m [/math], построим расписание способом выше и удалим из полученного расписания фиктивные работы.
Оценка сложности алгоритма
Минимальное значение [math] C_{max} [/math] вычисляется за [math] \mathcal{O}(1) [/math] времени.
Построение расписания сводится к заполнению матрицы размером [math] m \times \max{(m, n)} [/math] и выполняется за [math] \mathcal{O}(m \dot (m + n)) [/math] времени.
См. также.
