1sumwu — различия между версиями
Dominica (обсуждение | вклад) (→Псевдокод) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 2 промежуточные версии 2 участников) | |||
Строка 113: | Строка 113: | ||
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 26 - 28 | * P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 26 - 28 | ||
− | [[Категория: | + | [[Категория: Алгоритмы и структуры данных]] |
[[Категория: Теория расписаний]] | [[Категория: Теория расписаний]] |
Текущая версия на 19:17, 4 сентября 2022
Задача: |
Есть один станок и | работ. Для каждой работы заданы время выполнения дедлайн и стоимость выполнения этой работы . Необходимо минимизировать .
Содержание
Наивное решение
В общем случае, когда времена выполнения работ
могут быть сколь угодно большими или, например, дробными, данная задача может быть решена с помощью перебора.Будем перебирать все перестановки чисел от
до , обозначающих номера заданий. При получении очередной перестановки просто будем пытаться выполнять задания в указанном порядке. Если значение , полученное при данном расположении заданий, лучше, чем предыдущие результаты, то обновляем ответ.Данное решение будет работать за
.Перебор с битовыми масками
Далее широко будет использоваться следующий факт:
Лемма: |
Пусть все работы отсортированы в порядке неубывания дедлайнов .
Тогда существует оптимальное расписание вида , такое, что — номера работ, которые успеют выполниться вовремя, а — номера просроченных работ. |
Доказательство: |
Пусть у нас есть некоторое оптимальное раписание . Получим необходимое нам расписание путем переставления некоторых работ.
|
Наше решение будет построено на переборе всех битовых масок. При построении решения мы будем опираться на доказанную лемму.
Если бит, соответствующий заданию с номером
равен , то это задание должно быть записано в список заданий, которые, возможно, успеют выполниться. Далее мы сортируем задания из этого списка по времени неубывания дедлайнов, а те задания, что не попали в этот список, должны быть отправлены в конец расписания в любом порядке. Далее проверяем полученное возможное расписание на корректность, и, в случае успеха, обновляем ответ.Перебор всех масок может быть произведен за
, и на пересчет ответа. Таким образом, это решение будет работать за .Псевдополиномиальное решение
В ситуации, когда времена выполнения работ динамическое программирование.
целочисленные, а значение не очень большое, то для решения данной задачи можно применитьОписание алгоритма
Обозначим
. Для всех и будем рассчитывать — значение целевой функции , при условии, что были рассмотрены первые работ и общее время выполнения тех из них, что будут закончены вовремя, не превышает времени .- Если и работа успевает выполниться вовремя в расписании, соответствующем , то , иначе .
- Если , то , поскольку все работы с номерами , законченные позже, чем , будут выполнены с опозданием.
Отсюда, получим соотношение:
В качестве начальных условий следует взять
при и при .Ответом на задачу будет
.Псевдокод
Приведенный ниже алгоритм вычисляет
для и .- За обозначим самое большое из времен выполнения заданий.
- Значения будем хранить в массиве .
- В массиве хранятся стоимости выполнения работ, в — дедлайны, а в — продолжительности выполнения.
functionint int int int int for int сортируем работы по неубыванию времен дедлайнов for to for to for to for to for to if else for to return
Для того, чтобы найти само расписание, по доказанной выше лемме, нам достаточно найти множество работ
, которые будут выполнены с опозданием. Это может быть сделано следующим способом:functionint int int int set<int> int set<int> for downto if else return
Согласно лемме, само расписание будет состоять из работ, не попавших в
, отсортированных по неубыванию и работ из , записанных в конец в любом порядке.Время работы
В функции
пересчет динамики происходит за , а функция восстанавливает список просроченных работ за . Дальнейшее восстановление расписания происходит в худшем случае за . Отсюда видно, что время работы приведенного выше алгоритма — .См. также
Источники информации
- P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 26 - 28