Ppi1sumwu — различия между версиями
Анна (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 2 промежуточные версии 2 участников) | |||
Строка 9: | Строка 9: | ||
=== Псевдокод === | === Псевдокод === | ||
− | Пусть есть работы <tex>1 \ldots n</tex> с временами окончания <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. Будем называть ''простоем '' временной интервал, в который на машине ничего не обрабатывается. Для определения работ, не укладывающихся в срок, заведем счетчик времени <tex>t</tex>, который будем модифицировать так, как показано ниже. Тогда работа <tex>j</tex> опаздывает, если <tex>\left | + | Пусть есть работы <tex>1 \ldots n</tex> с временами окончания <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. Будем называть ''простоем '' временной интервал, в который на машине ничего не обрабатывается. Для определения работ, не укладывающихся в срок, заведем счетчик времени <tex>t</tex>, который будем модифицировать так, как показано ниже. Тогда работа <tex>j</tex> опаздывает, если <tex>\left\lfloor \dfrac{t}{m} \right\rfloor + p_j > d_j</tex>, где <tex>p_j = 1</tex>. Следующий алгоритм вычислит оптимальное множество <tex>S</tex>. |
<tex>S = \varnothing</tex> | <tex>S = \varnothing</tex> |
Текущая версия на 19:21, 4 сентября 2022
Задача: |
Дано | одинаковых станков, на которых нужно выполнить работ. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания — ожидается, что до этого времени она будет закончена, и штраф , который нужно будет выплатить в случае, если работа была закончена после . Необходимо минимизировать суммарный штраф, который придется выплатить.
Описание алгоритма
Идея
Оптимальное расписание для этой задачи будем задавать множеством работ
, которые будут выполнены в срок. Работы, которые не войдут в , то есть завершатся с опозданием, могут быть выполнены в конце в любом порядке. Чтобы построить множество , будем добавлять работы в порядке неуменьшения их времен окончания, и как только некоторая работа опаздывает, удалим из работу с минимальным значением и поставим на ее место.Псевдокод
Пусть есть работы
с временами окончания . Будем называть простоем временной интервал, в который на машине ничего не обрабатывается. Для определения работ, не укладывающихся в срок, заведем счетчик времени , который будем модифицировать так, как показано ниже. Тогда работа опаздывает, если , где . Следующий алгоритм вычислит оптимальное множество .for to if опаздывает, и все более ранние простои заполнены найти if заменить на в else добавить в и поставить на место самого раннего простоя
Таким образом, работы, не попавшие в
, будут иметь минимальное значение .Асимптотика
Данный алгоритм может быть реализован за время приоритетной очереди и для множества использовать любую структуру данных, у которой операции поиска и добавления элемента не хуже, чем .
, например, если хранить значения , которые принадлежат , вДоказательство корректности
Теорема: |
Вышеописанный алгоритм корректен и строит оптимальное множество работ . |
Доказательство: |
Пусть
Покажем, что в работа может быть заменена работой без увеличения значения целевой функции. Рассмотрим два случая:
|
См. также
Источники информации
- Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 119-120 ISBN 978-3-540-69515-8