Какой алгоритм может решить эту проблему программирования ограничений?

Question

Мне нужно решить проблему аффектации работы, и я бы хотел найти эффективные алгоритмы для решения этой проблемы.

Предположим, что есть некоторые работники, которые могут выполнять несколько задач. У нас также есть набор задач, которые необходимо выполнять каждую неделю. Каждая задача занимает некоторое время. Каждая задача должна быть взята кем-то. Каждый рабочий должен работать от N до P часов в неделю.

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

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

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

Алгоритм должен быть справедливым (если можно определить это слово), так что, например, я мог бы добавить ограничение типа «попытаться удовлетворить хотя бы одно желание на каждого человека». Я не уверен, что эта проблема может быть решена описанными здесь методами иерархии ограничений: Constraint Herarchies. На самом деле я не уверен, что «справедливость» и желания могут быть выражены допустимыми ограничениями для этой категории алгоритмов.

Есть ли эксперт по программированию с ограничениями, чтобы дать мне несколько советов? Нужно ли мне разрабатывать новое колесо с некоторыми эвристиками вместо использования эффективных алгоритмов CP?

Спасибо!

Answer 1

Ваша проблема достаточно сложна, что для общего решения, вероятно, потребуется сформулировать как проблему linear-integer. Если, с другой стороны, вы можете смягчить определенные требования, вы сможете использовать более простой подход. Например, bipartite matching позволит вам планировать несколько сотрудников для нескольких заданий и может даже обрабатывать предпочтения, но не сможет обеспечить общие ограничения «справедливости». См. это related SO question. Vertex colouring имеет эффективные алгоритмы для обеспечения ограничений разделения работы.

Другие плакаты упомянули simplex и job shop scheduling. Simplex - алгоритм оптимизации - он пересекает пространство решения, стремясь максимизировать некоторую целевую функцию. Сформулировать целевую функцию можно, конечно, сделать, но нетривиально. Классическое планирование магазина заданий, например двухстороннее сопоставление, может моделировать некоторые аспекты вашей проблемы, но не все. Например, ограничений на приоритет нет. Существуют расширенные версии, которые могут обрабатывать некоторые ограничения, например, устанавливать временные ограничения для задач.

Если вы заинтересованы в существующих реализациях, библиотека Python networkx имеет реализацию this matching algorithm. Пример программы составления расписания с открытым исходным кодом, которая может представлять интерес, - Tablix.

Answer 2

Это звучит так: job shop scheduling.

Answer 3

Я выполнил расписание, которое можно рассматривать как форму программирования ограничений. У вас есть жесткие (неприкосновенные) ограничения и мягкие ограничения (например, интервальные настройки).

Линейное целочисленное программирование обычно становится бесполезным после более чем 30 переменных, и это также можно сказать о симплексе.

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

Эвристические алгоритмы были использованы simmulated annealing, genetic algorithms, metaheuristic алгоритмы и похожи, но в конце концов, лучший результат были обеспечены «интеллектуальным» домен настроен greedy search алгоритм.

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

Отличным инструментом для исследования с открытым исходным кодом является исследование HeuristicLab.

Answer 4

Я согласен с тем, что было предложено здесь. Тем не менее, MIP (проблемы с смешанным целым программированием) очень большого размера (далеко за пределами 30 переменных!) Практически решены в настоящее время благодаря коммерческим кодам (Xpress, Cplex, Gurobi) или открытым исходным кодам (Coin-Or/Cbc). Кроме того, привлекательные языки моделирования, такие как OPL Studio, GAMS, AMPL, Flop ... позволяют легко писать математические модели вместо использования API.

Вы можете воспользоваться сервером NEOS (http://neos.mcs.anl.gov/neos/solvers/index.html), чтобы попробовать самые разные различные варианты MIP. Вы отправляете свою модель в формате AMPL. Хотя AMPL поставляется в виде бесплатной ограниченной версии, NEOS может обрабатывать неограниченные экземпляры.

Языки моделирования существуют также для CP (COMET/OPL Studio) и локального поиска (COMET).

Не стесняйтесь связаться со мной через мой веб-сайт www.rostudel.com («контакт» страницы)

Дэвид