Планирование SWI Prolog CLP (FD)

Question

Я решаю задачу планирования в SWI Prolog с использованием библиотеки CLPFD.Так как я впервые решаю что-то более серьезное, чем это было, я, вероятно, нуждаюсь в хороших советах от более опытных пользователей.Позвольте мне кратко описать домен / задачу.

Домен

У меня есть «календарь» на месяц.Каждый день есть 2 на весь день, 2 на всю ночь (12 часов службы).Также есть только пн-пт на 10 рабочих на 8 часов (кратковременное обслуживание).

Доменные ограничения, очевидно:

1. Нет последовательных услуг (ни дня посленочь и наоборот, без короткого дневного обслуживания после ночи)
2. На работника можно подавать до 2 последовательных ночных услуг подряд
3. Каждый работник имеет ограниченное количество часов в месяц
4. Доступно 19 рабочих

Мой подход следующий:

Переменные

Для каждого поля в календаре у меня определена переменная:

• DxD_y, где x - номер дня, а y - 1 или 2 для длинного дня службы
• DxN_y, где x - номердень и y - 1 или 2 для службы длинных ночей
• DxA_y, где x - номер дня, а y - 0 .. 9 для службы коротких дней
• SUM_x где x - рабочий номер (1..19), обозначающий сумму часов для рабочего

Каждый сотрудникПеременная D имеет домен 1..19.Чтобы упростить его на данный момент, SUM_X #=< 200 для каждого X.

Ограничения

• all_distinct() для каждой переменной в тот же день - каждый работник может обслуживать только одну услугу /день
• global_cardinality() для подсчета количества вхождений для каждого номера 1..19 для списка с короткими и длинными сервисами - это определяет переменные LSUM_X и SSUM_X - количество вхождений работника Xв L ong или S краткосрочных услугах
• SUM_X #= 12*LSUM_X + 8*SSUM_X для каждого работника
• DxN_y #\= Dx+1D_z - чтобы избежать долгого дневного обслуживания после ночной
  • связкианалогичные ограничения, подобные приведенному выше, охватывают все ограничения домена
• DxNy #= Dx+1Ny #==> DxNy #\= Dx+2Ny - чтобы избежать трех последовательных ночных служб, существуют ограничения для каждой комбинации x и y

Примечания

Все переменные и ограничения прямо указаны в сценарии pl.Я не использую предикаты пролога для генерации ограничения - потому что у меня есть модель в приложении .NET (внешний интерфейс), и я могу легко сгенерировать все содержимое из кода .NET в код пролога.

Я думаю, что мойподход в целом хорош.Запуск планировщика на небольшом примере работает хорошо (7 дней, 4 длинных службы, 1 короткая служба, 8 рабочих).Кроме того, мне удалось получить некоторые достоверные результаты в полномасштабном случае - 30 дней, 19 рабочих, 4 длинных и 10 коротких услуг в день.

Однако я не полностью удовлетворен текущим состоянием.Позвольте мне объяснить, почему.

Вопросы

1. Я прочитал несколько статей о задачах моделирования планирования, и некоторые из них используют немного другой подход - вводить только логические переменные для каждой комбинации моей переменной (поле календаря) и рабочий, чтобы указать, назначен ли работник определенному календарному полю.Это лучший подход?
2. Если вы подсчитаете общий лимит количества рабочих мест и общее количество часов в календаре, вы обнаружите, что рабочие не используются на 100%. Но решатель создает решение, скорее всего, так: utilize the first worker for 100% and then grab the next one. Таким образом, суммы в решении выглядят как [200,200,200...200,160,140,80,50,0,]. Я был бы рад, если рабочие будут более или менее одинаково использованы. Есть ли какой-нибудь простой / эффективный способ, как этого добиться? Я считал, что определение - это как определение различий между работниками и его минимизация, но для меня это звучит очень сложно, и я боюсь, что мне понадобятся целые годы, чтобы это вычислить. Я использую labeling([random_variable(29)], Vars), но он только переупорядочивает переменные, поэтому эти пробелы все еще существуют, только в другом порядке. Возможно, я хочу, чтобы процедура labeling принимала значения в каком-то другом порядке, нежели up или down (каким-то псевдослучайным образом).
3. Как мне заказать ограничения? Я думаю, что порядок ограничений имеет значение в отношении эффективности маркировки.
4. Как отладить / оптимизировать производительность маркировки? Я надеялся, что решение этого типа задачи займет несколько секунд или максимум пару минут в случае очень жестких условий для сумм. Например, маркировка с помощью опции bisect заняла много лет.

При необходимости я могу предоставить еще несколько примеров кода.

Answer 1

Это много вопросов, позвольте мне попытаться ответить на некоторые из них.

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

Обычно это делается, когда используется решатель MILP (Смешанное целочисленное линейное программирование), где понятия более высокого уровня (такие как alldifferent и т. Д.) Должны быть выражены в виде линейных неравенств. Такие формулировки обычно требуют большого количества логических переменных. Ограничительное программирование здесь более гибкое и предлагает больше вариантов моделирования, но, к сожалению, простого ответа нет, это зависит от проблемы. Выбор переменных влияет как на то, как трудно выразить свои проблемы, так и на эффективность, которую они решают.

Таким образом, суммы в решении выглядят как [200,200,200 ... 200,160,140,80,50,0,]. Я был бы рад, если рабочие будут более или менее одинаково использованы. Есть ли какой-нибудь простой / эффективный способ, как этого добиться?

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

?- length(Xs,5), Xs#::0..9, sum(Xs)#=20, labeling(Xs).
Xs = [0, 0, 2, 9, 9]

тогда простое сведение к минимуму максимального числа элементов списка даст вам (в сочетании с суммированием) сбалансированное решение:

?- length(Xs,5), Xs#::0..9, sum(Xs)#=20, Cost#=max(Xs), minimize(labeling(Xs),Cost).
Xs = [4, 4, 4, 4, 4]
Cost = 4

Вы также можете минимизировать разницу между минимальным и максимальным:

?- length(Xs,5), Xs#::0..9, sum(Xs)#=20, Cost#=max(Xs)-min(Xs), minimize(labeling(Xs),Cost).
Xs = [4, 4, 4, 4, 4]
Cost = 0

или даже сумма квадратов. [Извините, мои примеры приведены для ECLiPSe , а не для SWI / clpfd, но должны показать общую идею.]

Как мне заказать ограничения? Я думаю, что порядок ограничений имеет значение в отношении эффективности маркировки.

Не беспокойся об этом. Хотя это может иметь некоторое влияние, оно слишком непредсказуемо и слишком сильно зависит от деталей реализации, чтобы давать какие-либо общие рекомендации. Это действительно работа разработчика решателя.

Как отладить / оптимизировать производительность маркировки?

Для реалистичных задач вам часто потребуется (а) эвристика маркировки для конкретной проблемы и (б) некоторая разновидность неполного поиска. Визуализация дерева поиска или хода поиска может помочь с настройкой эвристики. Вы можете найти некоторое обсуждение этих вопросов в главе 6 этого онлайн-курса .