Блог

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

Домен

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

Очевидно, что ограничения домена:

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

Мой подход заключается в следующем:

Переменные

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

• DxD_y где x — номер дня и y равно 1 или 2 для службы долгого дня
• DxN_y где x — номер дня и y равно 1 или 2 для службы long night
• 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 — количество вхождений worker X в L ong или S hort services
• SUM_X #= 12*LSUM_X 8*SSUM_X для каждого работника
• DxN_y #= Dx 1D_z — чтобы избежать долгого дневного обслуживания после ночного
  • набор аналогичных ограничений, подобных приведенному выше, для покрытия всех ограничений домена
• DxNy #= Dx 1Ny #==> DxNy #= Dx 2Ny — чтобы избежать трех последовательных ночных служб, существуют ограничения для каждой комбинации x и y

Примечания

Все переменные и ограничения указаны непосредственно в сценарии pl. Я не использую предикаты prolog для создания ограничений — потому что у меня есть модель в приложении .NET (интерфейс), и я могу легко сгенерировать все материалы из .ЧИСТЫЙ код в код prolog.

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

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

Вопросы

1. Я прочитал несколько статей о проблемах моделирования планирования, и в некоторых из них используется немного другой подход — вводятся только логические переменные для каждой комбинации моей переменной (поле календаря) и worker, чтобы отметить, назначен ли worker определенному полю календаря. Это лучший подход?
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 помощью опции заняла целую вечность.

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

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

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

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

Таким образом, суммы в решении выглядят как [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 этого онлайн-курса.