Ppi1sumwu
НЕТ ВОЙНЕ |
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Задача: |
Дано | одинаковых станков, на которых нужно выполнить работ. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания — ожидается, что до этого времени она будет закончена, и штраф , который нужно будет выплатить в случае, если работа была закончена после . Необходимо минимизировать суммарный штраф, который придется выплатить.
Описание алгоритма
Идея
Оптимальное расписание для этой задачи будем задавать множеством работ
, которые будут выполнены в срок. Работы, которые не войдут в , то есть завершатся с опозданием, могут быть выполнены в конце в любом порядке. Чтобы построить множество , будем добавлять работы в порядке неуменьшения их времен окончания, и как только некоторая работа опаздывает, удалим из работу с минимальным значением и поставим на ее место.Псевдокод
Пусть есть работы
с временами окончания . Будем называть простоем временной интервал, в который на машине ничего не обрабатывается. Для определения работ, не укладывающихся в срок, заведем счетчик времени , который будем модифицировать так, как показано ниже. Тогда работа опаздывает, если , где . Следующий алгоритм вычислит оптимальное множество .for to if опаздывает, и все более ранние простои заполнены найти if заменить на в else добавить в и поставить на место самого раннего простоя
Таким образом, работы, не попавшие в
, будут иметь минимальное значение .Асимптотика
Данный алгоритм может быть реализован за время приоритетной очереди и для множества использовать любую структуру данных, у которой операции поиска и добавления элемента не хуже, чем .
, например, если хранить значения , которые принадлежат , вДоказательство корректности
Теорема: |
Вышеописанный алгоритм корректен и строит оптимальное множество работ . |
Доказательство: |
Пусть
Покажем, что в работа может быть заменена работой без увеличения значения целевой функции. Рассмотрим два случая:
|
См. также
Источники информации
- Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 119-120 ISBN 978-3-540-69515-8