Лучшее распределение работы (метод наименьших квадратов) в Ruby

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

Пример:

[TaskA, 4 hours], [TaskB, 8 hours], [TaskC, 10 hours]

Я бы хотел привязать эти задачи к конкретным датам. Например, чтобы распределить их в течение 2 дней, я мог бы разделить их как:

Day 1: TaskA, TaskB | Day 2: TaskC
Day 1: TaskA | Day 2: TaskB, TaskC

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

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

Я реализовал алгоритм для выполнения этого расчета, и он работает правильно, но очень медленно (10+ минут для 50 задач за 14 дней). Я просматриваю список задач и для каждой либо кладу ее в текущую «корзину», либо перемещаю в другую «корзину» (день). Затем я выбираю лучшее решение. Я также заранее обрезаю деревья рекурсии, используя текущее минимальное значение. Это сократило время с 30+ до 10+ минут, но все равно слишком медленно.

Я использую Ruby, но алгоритм на любом языке, который я могу портировать, будет в порядке.


ruby optimization algorithm least-squares
person Pasta    schedule 31.01.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Если я правильно понял ваш вопрос, у вас проблема с линейным программированием или целочисленным программированием. Если это так, вы можете получить оптимальное решение, используя гем, такой как opl.

Позволять:

HTt: количество часов, необходимых для выполнения задачи t.

HDd: количество часов, доступных для работы в день d.

Затем мы определяем переменные, значения которых необходимо определить:

xtd: количество часов, потраченных на задачу t в день d.

У нас есть три набора ограничений:

Каждое задание должно быть выполнено:

Σdxtd = HTt для каждой задачи t

На каждый день может быть назначено не более HDtd часов работы d:

Σtxtd ‹= HDd для каждого дня d

Переменные должны быть неотрицательными:

xtd >= 0 для каждой задачи t и дня d

Наконец, мы определяем цель, которая должна быть максимизирована или минимизирована:

z = Σtdatdxtd

где atd — заданные коэффициенты для каждой пары t,d (например, единичная прибыль или затраты).

Проблема программирования состоит в том, чтобы выбрать значения переменных, которые максимизируют целевое значение z при заданных ограничениях. Это линейная программа, если переменным можно присвоить дробные значения (например, потратить 1,27458 часов на задачу t в день d). Если переменным могут быть присвоены только целочисленные значения, это целочисленная программа. Если некоторые переменные могут иметь дробное значение, а другие должны иметь целочисленное значение, это программа со смешанным целым числом. Из этих трех задач линейные программы решить проще всего.

Если вам просто нужны выполнимые решения* — любое решение, удовлетворяющее всем ограничениям, — просто установите z = 0 и решите (хотя решение тривиально, если это линейная программа).

Предположим, вы хотите назначать задачи получасовыми блоками, и цель состоит в том, чтобы свести к минимуму максимальное количество часов, отработанных в любой заданный день. Это будет целочисленная программа с переменными, представляющими собой количество получасовых блоков задачи t, которые должны быть выполнены в день d, и целью будет минимизация z с дополнительным набором ограничений:

z >= Σtxtd для каждого дня d

Конечно, HTt и HDd будут изменены с часов на количество получасовых блоков.

person Cary Swoveland    schedule 31.01.2015