Ppi1sumwu — различия между версиями
Анна (обсуждение | вклад) |
Анна (обсуждение | вклад) |
||
Строка 45: | Строка 45: | ||
б). Пусть <tex>k^* < k</tex>. Тогда все работы из <tex>S_t \cup \{k\}</tex> могут быть выполнены в срок, так как <tex>S_t</tex> и <tex>k</tex> принадлежат <tex>S^*</tex>. Более того, все работы из множества <tex>\{j \in S_t | j < k\}</tex> могут быть выполнены без опозданий. Таким образом, мы снова приходим к тому, что множество <tex>S_t \cup \{k^*\}</tex> не содержит работ со штрафами, что является противоречием. | б). Пусть <tex>k^* < k</tex>. Тогда все работы из <tex>S_t \cup \{k\}</tex> могут быть выполнены в срок, так как <tex>S_t</tex> и <tex>k</tex> принадлежат <tex>S^*</tex>. Более того, все работы из множества <tex>\{j \in S_t | j < k\}</tex> могут быть выполнены без опозданий. Таким образом, мы снова приходим к тому, что множество <tex>S_t \cup \{k^*\}</tex> не содержит работ со штрафами, что является противоречием. | ||
}} | }} | ||
+ | |||
+ | == Источники информации == | ||
+ | * Peter Brucker Scheduling Algorithms, fifth edition, Springer {{---}} с. 119-120 ISBN 978-3-540-69515-8 | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Теория расписаний]] | [[Категория: Теория расписаний]] |
Версия 13:02, 6 мая 2016
Задача: |
Дано | одинаковых станков, на которых нужно выполнить работ. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания — ожидается, что до этого времени она будет закончена, и штраф , который нужно будет выплатить в случае, если работа была закончена после . Необходимо минимизировать суммарный штраф, который придется выплатить.
Описание алгоритма
Оптимальное расписание для этой задачи будем задавать множеством работ
Чтобы построить множество , будем добавлять работы в порядке неуменьшения их времен окончания, и как только некоторая работа опаздывает, удалим из работу с минимальным значением и поставим на ее место.
Пусть есть работы с временами окончания . Будем называть простоем временной интервал, в который на машине ничего не обрабатывается. Тогда следующий алгоритм вычислит оптимальное множество .
for to : if опаздывает, и все более ранние простои заполнены: найти if : заменить на в else: добавить в и поставить на место самого раннего простоя
Таким образом, работы, не попавшие в
, будут иметь минимальное значение .Доказательство корректности
Теорема: |
Вышеописанный алгоритм корректен и строит оптимальное множество работ . |
Доказательство: |
Пусть
Покажем, что в Будем говорить
то |
Источники информации
- Peter Brucker Scheduling Algorithms, fifth edition, Springer — с. 119-120 ISBN 978-3-540-69515-8