Эффективные рабочие места планирования с снижением прибыли на нескольких машинах

Question

Проблема: Рассмотрим задачу планирования русских рабочих мест на машинах M, где каждая работа у меня есть время обработки р _я и дает прибыль г _я (Т), если завершено к моменту t. Все задания высвобождаются в момент времени 0. Все g _i (t) являются не увеличивающимися функциями. Для простоты можно предположить, что машины не являются превентивными.

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

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

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

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

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

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

Answer 1

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

г _я (т + р _я)/р _я

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

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

• Возьмите одно задание с одной машины и найдите новое место для его вставки.
• Обмен двумя заданиями в последовательности заданий машин.