Эффективное планирование заданий с уменьшением прибыли на нескольких машинах

Задача: Рассмотрим задачу планирования n заданий на M машинах, где каждое задание i имеет время обработки pi и приносит прибыль gi( t), если завершено к моменту времени t. Все задания освобождаются в момент времени 0. Все gi(t) являются невозрастающими функциями. Для простоты можно предположить, что машины не являются вытесняющими.

Для M=1 и линейно убывающей функции прибыли. эту задачу можно решить за O(n) с помощью жадного алгоритма. Но для общих функций он NP-полный.

Меня интересует общий случай. Пожалуйста, дайте мне любую ссылку на документы или ресурсные материалы по проблеме. Я искал в Интернете, но не нашел ничего интересного для M>1, хотя есть предыдущая работа по аппроксимации оценок для M=1.

Обратите внимание, что я не ожидаю, что вы решите эту проблему, а просто нуждаетесь в предыдущей работе над подобными проблемами, если таковые имеются. И если у вас есть какие-либо идеи, которые могут помочь, пожалуйста, не стесняйтесь делиться ими.

Я хочу знать, какие границы известны для этой задачи с m машинами и n заданиями с одинаковыми датами выпуска и общими невозрастающими функциями прибыли. Я нашел бумагу в этом направлении

http://arxiv.org/pdf/1008.4889v1.pdf

Они дали приближение O (1), когда все задания имеют одинаковое время выпуска. Я хочу найти подобную литературу по проблеме и какие идеи они использовали для решения проблемы.


job-scheduling algorithm maximize np-complete approximate
person v78    schedule 29.09.2015    source источник

Ответы (1)


arrow_upward
2
arrow_downward

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

gi(t0+pi)/pi

на первой пустой машине (я прогоняю все еще не запланированные задания, t0 — это время, когда первая машина пуста).

Затем это решение можно улучшить с помощью метаэвристики, такой как Simulated Annealing. Решение можно представить в виде кортежа последовательностей заданий (по одной последовательности заданий для каждой машины). Важным моментом является то, какие «ходы» разрешены для изменения решения. Может быть, для этой проблемы можно найти уже хорошие решения с двумя основными ходами:

  • Возьмите одно задание с одной машины и найдите новое место для его вставки.
  • Поменяйте местами два задания в последовательности заданий машин.
person coproc    schedule 02.10.2015
comment
Можете ли вы доказать какую-либо границу решения, упомянутого выше. Я имею в виду, да, ваш метод выглядит многообещающе (и, я думаю, будет работать довольно быстро), но может ли не быть гарантий по временной сложности и тому, насколько хорош конечный результат по сравнению с оптимальным решением. Я ищу более доказуемые границы проблемы. - person v78; 02.10.2015
comment
@ cc2, возможно, для данного начального решения (которое не зависит от улучшения с помощью метаэвристики) можно дать оценку, но я не могу сказать. Для метаэвристики, конечно, можно контролировать время выполнения, но нельзя дать никаких ограничений. Это больше практично: тщательно продуманный метаэвристический подход может быть очень успешным на практике. - person coproc; 02.10.2015
comment
Это хороший инженерный подход, но он искал наилучшие доказуемые границы, известные для общего случая задачи. - person v78; 02.10.2015