Как смоделировать простую задачу планирования с помощью MS Solver Foundation?

У меня есть следующая простая проблема, которую я хотел бы использовать для экспериментов с MS Solver Foundation:

У меня есть график, по которому мне нужно иметь 2 рабочих в день в течение 30 дней. Мне нужно соблюдать следующие ограничения:

  • Люди не должны работать два дня подряд.
  • Если не применяется специальное исключение, люди должны работать только один раз в неделю.
  • Некоторые люди могут работать только по выходным.
  • Некоторые люди могут работать только в будние дни.

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

Обновление: хотя у ire-and-curses хорошее начало, я должен представить, что существует более декларативный способ выразить эти ограничения с помощью фреймворка, а не кодировать их индивидуально для каждого человека. Кто-нибудь, более знакомый с MSF, может помочь с этой конструкцией?


constraints model scheduling ms-solver-foundation
person Larsenal    schedule 08.09.2009    source источник
comment
Что вы хотите оптимизировать? Требуемое количество людей?   -  person Daniel Brückner    schedule 08.09.2009
comment
В конце концов, да. Изначально я просто хочу сгенерировать возможное решение. Надеюсь, как только я установлю эти простые ограничения, я смогу расширить их, чтобы учесть более конкретные предпочтения отдельных людей.   -  person Larsenal    schedule 08.09.2009
comment
Я понимаю, что вы пытаетесь сделать это с помощью подхода, основанного на ограничениях, поэтому я предлагаю это не в качестве ответа, а просто для информации: вы также можете найти интересный альтернативный подход с помощью двустороннего сопоставления. См., Например: stackoverflow.com/questions/ 1221990 /   -  person ire_and_curses    schedule 08.09.2009

Ответы (1)


arrow_upward
1
arrow_downward

Если у вас есть n человек, вам нужно будет определить 30n двоичные целочисленные параметры, каждый из которых указывает, работает человек в определенный день или нет.

P<xx>D<yy> == 1 => Person <xx> works on day <yy>
P<xx>D<yy> == 0 => Person <xx> does not work on day <yy>

Тогда вам нужны ограничения, чтобы не работать два дня подряд. Это будет 29n ограничений.

P<xx>D<yy> + P<xx>D<yy+1> <= 1

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

P<xx>D00 + P<xx>D01 + P<xx>D02 + P<xx>D03 + P<xx>D04 + P<xx>D05 + P<xx>D06 <= 1

Последняя неделя будет следующей.

P<xx>D28 + P<xx>D29 <= 1

Это приведет к другим 5n ограничениям. Затем добавьте ограничения только для будних дней

P<xx>D05 + P<xx>D06 == 0
P<xx>D12 + P<xx>D13 == 0
P<xx>D19 + P<xx>D20 == 0
P<xx>D26 + P<xx>D27 == 0

и только по выходным

P<xx>D00 + P<xx>D01 + P<xx>D02 + P<xx>D03 + P<xx>D04 == 0
P<xx>D07 + P<xx>D08 + P<xx>D09 + P<xx>D10 + P<xx>D11 == 0
P<xx>D14 + P<xx>D15 + P<xx>D16 + P<xx>D17 + P<xx>D18 == 0
P<xx>D21 + P<xx>D22 + P<xx>D23 + P<xx>D24 + P<xx>D25 == 0
P<xx>D28 + P<xx>D29 == 0

и, наконец, добавить целевую функцию.

person Daniel Brückner    schedule 08.09.2009
comment
Простите, что я незнаком с терминологией, но каков будет пример целевой функции? - person Larsenal; 08.09.2009
comment
Функция traget представляет цель, которую вы хотите оптимизировать. Я бы привел пример, но не мог придумать содержательного. Возможно, максимизируйте количество людей, работающих в течение нулевых дней, и, следовательно, минимизируйте количество людей, необходимых для выполнения работы. Но я не уверен, как это можно выразить в SolverFoundation, потому что я узнал об этом всего час назад. - person Daniel Brückner; 08.09.2009
comment
Спасибо за понимание. Как только у меня будет возможность попробовать это, я вернусь к этому вопросу, чтобы дать ответ. - person Larsenal; 08.09.2009