|
|
| Строка 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" >R \mid pmtn \mid C_{max}</tex> | | <tex dpi = "200" >R \mid pmtn \mid C_{max}</tex> |
| | | | |
Текущая версия на 19:40, 4 сентября 2022
[math]R \mid pmtn \mid C_{max}[/math]
| Задача: |
| Имеется [math]m[/math] машин, работающих параллельно. Есть [math]n[/math] работ, причем для каждого станка длительность выполнения на нем [math]i[/math]-й работы составляет [math] p_{ij} [/math]. Работа может быть прервана и продолжена позже.
Необходимо составить такое расписание, чтобы значение [math]C_{max} = \max\limits_{i=1\ldots n} C_i[/math] было минимальным. |
Алгоритм
Будет строить расписание по нижней оценке.
Вычислим для каждой работы время [math]t_{ij}[/math], которое работа [math]i[/math] будет выполняться на [math]j[/math]-ом станке в оптимальном расписании.
Пусть [math]\dfrac {t_{ij} } {p_{ij}} [/math] — часть времени, которое работа [math]i[/math] будет выполняться на [math]j[/math]-ом станке. Тогда [math] \sum\limits_{j=1}^m \dfrac {t_{ij} } {p_{ij}} = 1[/math] верно, если работа завершена.
Теперь оптимальное расписание должно удовлетворять следующим условиям:
- [math] \sum\limits_{j=1}^m \dfrac {t_{ij} } {p_{ij}} = 1, \quad i = 1,\ldots, n[/math]
- [math] \sum\limits_{j=1}^m t_{ij} \leqslant C_{max}, \quad i = 1,\ldots, n[/math]
- [math] \sum\limits_{i=1}^n t_{ij} \leqslant C_{max}, \quad j = 1,\ldots, m[/math]
- [math] t_{ij} \geqslant 0, \quad i = 1,\ldots, n; j = 1,\ldots, m[/math]
Обозначим нижнюю оценку как [math]LB = \max\{\max\limits_{i=1}^n \sum\limits_{j=1}^m t_{ij}, \sum\limits_{i=1}^n t_{ij}\} [/math].
Можем получить ответ на задачу за [math]O(n)[/math]. Расписание, удовлетворяющее этой оценке строится аналогично [math]O \mid pmtn \mid C_{max}[/math] [1] за полиномиальное время.
См. также
Примечания
- ↑ Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 15-17
Источники информации
- Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 137-139 стр. — ISBN 978-3-540-69515-8
