Алгоритм минимизации общего опоздания

Question

Я пытаюсь реализовать точный алгоритм минимизации общего опоздания для одной машины. Я искал в Интернете, чтобы понять, как я могу реализовать это с помощью динамического программирования. Я прочитал статью Лоулера, который предложил алгоритм PSEUDOPOLYNOMIAL еще в 77 году. Однако все еще не смог отобразить его в коде java или c #.

Не могли бы вы помочь мне дать некоторые рекомендации, как эффективно реализовать этот точный алгоритм?

Edit-1: @bcat: не совсем. Мне нужно реализовать это для нашего программного обеспечения. :( до сих пор я не могу найти какие-либо рекомендации, как его реализовать. Жадный легко реализовать, но результат планирования не так впечатляет.

С уважением,

Xiaon

Answer 1

Вы могли указать точные характеристики вашей конкретной проблемы, а также пределы для различных переменных и общие характеристики входных данных.

Без этого я предполагаю, что вы используете это определение:

Вы хотите минимизировать общее опоздание в одной задаче планирования машины с n независимыми заданиями, у каждого из которых есть время обработки и срок выполнения.

То, что вы хотите сделать, это подобрать подмножество заданий, чтобы они не перекрывались (доступно только одно устройство), и вы также можете выбрать порядок, в котором вы их выполняете, с соблюдением сроков исполнения.

Полагаю, первый шаг - сортировка по срокам. Похоже, что сортировать их по-другому не выгодно.

Далее осталось выбрать подмножество. Вот где динамическое программирование приходит на помощь. Я постараюсь описать состояние и рекурсивные отношения.

Состояние:

[current time][current job] = maximum number of jobs done

Отношение:

Вы либо обрабатываете текущее задание и звоните

f(current time + processing_time_of[current job],current job +1)

или вы пропустите процесс и позвоните

f(current time,current job +1)

наконец вы берете минимум этих двух значений, возвращаемых этими вызовами, и сохраняете его в состоянии

[current time][current job]

И вы начинаете рекурсию в момент 0 и задание 0.

Кстати, у жадного, кажется, все хорошо, проверьте это:

http://www.springerlink.com/content/f780526553631475/

Answer 2

Для одной машины расписание Longest Processing Time (также известное как алгоритм уменьшения времени) является оптимальным, если вы заранее знаете все задания и можете отсортировать их от самых длинных к самым коротким (поэтому все, что вам нужно сделать, это отсортировать).

Как уже упоминалось, вы не указали никакой информации о своей проблеме планирования, поэтому трудно справиться с этим (поскольку не существует универсально оптимального и эффективного планировщика).

Answer 3

Может быть, Раздел планирования работы из хранилища алгоритма Stony Brook может помочь вам.