Какой алгоритм можно использовать для оптимального распределения задач?

Question

[Орхан Гасанлы]

Добрый день, коллеги!
Вопрос к сожалению, вчера был удален по причине тэг спама, потому публикую его заново.
Итак, прежде чем задать вопрос расскажу задачу, которую необходимо решить.
Есть n работ, которые нужно оптимально распределить между сотрудниками. Притом есть другие входные параметры, которые накладывают доп. ограничения.
Например, каждый сотрудник может выполнить min & max количество работ в день. Соответственно, при распределении работ нужно это учесть. Также есть рабочий график сотрудника (например, 8 часовой рабочий день + 1 час время на обед). Есть также другие входные параметры, которые могут накладывать доп. ограничения. Например, время необходимое, чтобы достичь места проведения конкретной работы.
Нечто похожее используется в либе jsprit (Java) для решения задачи коммивояжера (принцип ruin and recreate).
Соответственно, вопросы:
- какой алгоритм можно использовать для оптимального распределения задач?
- какие алгоритмы оптимизации лучше подойдут для решения этой задачи? Например, simulated annealing, ruin and recreate и др.

Некий псевдокод:

void optimize(List<Work> works, List<Empolyee> employees, Setting setting) {
	
}

Setting {
	int minWorksNum;
	int maxWorksNum;
	int workSchedule;
	int lunchTime;
}

Empolyee {
	List<Work> works;
}

Work {
	int arrivalTime;
	int workTime;
        int priority;
}

К слову, нашел интересные либы, которые потенциально могут помочь решить данную задачу. Буду их пробовать.
Либа - https://github.com/cicirello/Chips-n-Salsa
Примеры - https://github.com/cicirello/chips-n-salsa-examples
Еще одна либа - https://github.com/nsadawi/simulated-annealing

Comments

[dollar]

Какой критерий оптимальности?

[Сергей Сергей]

dollar, время же.

[Орхан Гасанлы]

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

[hint000]

Задача про N рюкзаков (с дополнительными ограничениями)? (вес = время выполнения задачи)
https://ru.wikipedia.org/wiki/Список_задач_о_рюкзаке - Мультипликативный рюкзак

[Орхан Гасанлы]

hint000, благодарю за ссылку. Изучу статью

[tzlom]

Сначала начните с полной постановки задачи, включая размерности. Для 10 человек можно и перебором, для миллиона наврядли найдется единственное решение.
Посмотрите в сторону линейного или квадратического программирования (на самом деле это матан) бесплатных солверов найдется под любой мейнстримный язык

[Орхан Гасанлы]

tzlom, благодарю за ответ.
насчет размерности - речь идет об 200-500 сотрудниках максимум. Количество работ для каждого сотрудника может варьировать, так как на это влияет и расстояние. которое они должно преодолеть до следующей точки проведения работы и лимиты, которые могут быть заданы (minWorksNum, maxWorksNum)
А вот, насчет полной постановки задачи, готов ответить на любой интересующий вопрос

бесплатных солверов найдется под любой мейнстримный язык

Вроде бы я нашел одну либу, которая может решить подобные задачи:
https://github.com/cicirello/Chips-n-Salsa
Правда, пока не имел чести с ней поработать. Буду разбираться дальше.
Еще раз спасибо

Answer 1

[Орхан Гасанлы]

В качестве решения данной задачи была выбрана библиотека OptaPlanner.
https://www.optaplanner.org/
Позволяет решать проблемы оптимизации