RpmtnCmax — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 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>
  

Версия 06:35, 1 сентября 2022

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

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

[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] верно, если работа завершена.

Теперь оптимальное расписание должно удовлетворять следующим условиям:

  1. [math] \sum\limits_{j=1}^m \dfrac {t_{ij} } {p_{ij}} = 1, \quad i = 1,\ldots, n[/math]
  2. [math] \sum\limits_{j=1}^m t_{ij} \leqslant C_{max}, \quad i = 1,\ldots, n[/math]
  3. [math] \sum\limits_{i=1}^n t_{ij} \leqslant C_{max}, \quad j = 1,\ldots, m[/math]
  4. [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] за полиномиальное время.

См. также

Примечания

  1. Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 15-17

Источники информации

  • Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 137-139 стр. — ISBN 978-3-540-69515-8