1p1sumu — различия между версиями
Веда (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 4 промежуточные версии 3 участников) | |||
Строка 7: | Строка 7: | ||
==Алгоритм== | ==Алгоритм== | ||
− | Чтобы получить оптимальное расписание, будем строить максимальное множество <tex>S</tex> тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из <tex>S</tex>, упорядоченных по неубыванию дедлайнов. Во время сортировки стоит учитывать, что дедлайны могут значительно превосходить количество задач. В таком случае необходимо предварительно пересчитать дедлайны по формуле <tex>d_i = \min\{d_i, n\}</tex> (в оптимальном расписании мы | + | |
+ | ===Описание алгоритма=== | ||
+ | Чтобы получить оптимальное расписание, будем строить максимальное множество <tex>S</tex> тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из <tex>S</tex>, упорядоченных по неубыванию дедлайнов. Во время сортировки стоит учитывать, что дедлайны могут значительно превосходить количество задач. В таком случае необходимо предварительно пересчитать дедлайны по формуле <tex>d_i = \min\{d_i, n\}</tex> (в оптимальном расписании мы выполняем все работы до времени <tex>time=n</tex>). Для упорядочивания дедлайнов будем использовать [[Карманная сортировка|карманную сортировку]]. | ||
===Псевдокод=== | ===Псевдокод=== | ||
− | schedule(d: '''int[n]'''): '''int | + | '''function''' schedule(d: '''int[n]'''): '''list<int>''' |
− | '''int | + | '''list<int>''' S = <tex>\varnothing</tex> |
'''int''' time = 0 | '''int''' time = 0 | ||
'''for''' i = 1 '''to''' n '''do''' | '''for''' i = 1 '''to''' n '''do''' | ||
Строка 19: | Строка 21: | ||
'''if''' time < d[i] | '''if''' time < d[i] | ||
S = S <tex>\cup</tex> {i} | S = S <tex>\cup</tex> {i} | ||
− | time | + | time += 1 |
− | + | '''return''' S | |
− | Во избежание лишнего копирования массивов, мы можем делать проход по массиву блоков(bucket'ов) и для каждого блока проходить по спискам работ внутри него. Начальное значение <tex> time = 0</tex>. После рассмотрения очередной работы мы будем добавлять ее в расписание и увеличивать <tex> time</tex> на 1. Тогда, если значение <tex> time</tex> становится равным номеру блока, то мы переходим к следующему блоку, а нерассмотренные задачи помечаем как просроченные и выполняем в конце. | + | Во избежание лишнего копирования массивов, мы можем делать проход по массиву блоков (bucket'ов) и для каждого блока проходить по спискам работ внутри него. Начальное значение <tex> time = 0</tex>. После рассмотрения очередной работы мы будем добавлять ее в расписание и увеличивать <tex> time</tex> на <tex>1</tex>. Тогда, если значение <tex> time</tex> становится равным номеру блока, то мы переходим к следующему блоку, а нерассмотренные задачи помечаем как просроченные и выполняем в конце. Работы с <tex>d_i = 0</tex> заранее отметим как просроченные. |
− | ==Время работы== | + | ===Время работы=== |
Cортировку работ по неубыванию дедлайнов осуществляем с помощью карманной сортировки за <tex>O(n)</tex>, а значит и весь алгоритм будет работать за <tex>O(n)</tex>. | Cортировку работ по неубыванию дедлайнов осуществляем с помощью карманной сортировки за <tex>O(n)</tex>, а значит и весь алгоритм будет работать за <tex>O(n)</tex>. | ||
− | ==Корректность и оптимальность== | + | ===Корректность и оптимальность=== |
В результате выполнения данного алгоритма будет получено корректное расписание, в котором каждая работа встречается не более одного раза. Вначале расписания будут стоять все работы, которые мы успеваем выполнить до дедлайна. Остальные работы дописываются в конец в произвольном порядке. | В результате выполнения данного алгоритма будет получено корректное расписание, в котором каждая работа встречается не более одного раза. Вначале расписания будут стоять все работы, которые мы успеваем выполнить до дедлайна. Остальные работы дописываются в конец в произвольном порядке. | ||
Текущая версия на 19:15, 4 сентября 2022
Задача: |
Дан один станок и | работ, для которых заданы их дедлайны , а все времена выполнения на этом станке . Нужно успеть выполнить как можно больше работ.
Содержание
Алгоритм
Описание алгоритма
Чтобы получить оптимальное расписание, будем строить максимальное множество карманную сортировку.
тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из , упорядоченных по неубыванию дедлайнов. Во время сортировки стоит учитывать, что дедлайны могут значительно превосходить количество задач. В таком случае необходимо предварительно пересчитать дедлайны по формуле (в оптимальном расписании мы выполняем все работы до времени ). Для упорядочивания дедлайнов будем использоватьПсевдокод
function schedule(d: int[n]): list<int> list<int> S =int time = 0 for i = 1 to n do d[i] = min(d[i], n) Сортиуем d for i = 1 to n do if time < d[i] S = S {i} time += 1 return S
Во избежание лишнего копирования массивов, мы можем делать проход по массиву блоков (bucket'ов) и для каждого блока проходить по спискам работ внутри него. Начальное значение
. После рассмотрения очередной работы мы будем добавлять ее в расписание и увеличивать на . Тогда, если значение становится равным номеру блока, то мы переходим к следующему блоку, а нерассмотренные задачи помечаем как просроченные и выполняем в конце. Работы с заранее отметим как просроченные.Время работы
Cортировку работ по неубыванию дедлайнов осуществляем с помощью карманной сортировки за
, а значит и весь алгоритм будет работать за .Корректность и оптимальность
В результате выполнения данного алгоритма будет получено корректное расписание, в котором каждая работа встречается не более одного раза. Вначале расписания будут стоять все работы, которые мы успеваем выполнить до дедлайна. Остальные работы дописываются в конец в произвольном порядке.
Оптимальность полученного расписания доказывается аналогично .
См. также
Источники информации
- Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 86 стр. — ISBN 978-3-540-69515-8