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

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

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

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

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

Update: Хотя ИРЭ-и-проклятия имеют хороший старт, я должен представить себе, что есть более декларативный способ выразить эти ограничения, используя структуру, а не должно кодировать их индивидуальны для каждого человека. Кто-нибудь более знакомый с MSF, который может помочь в этой конструкции?

источник

2009-09-08 Larsenal

Что вы хотите оптимизировать? Сколько людей нужно? –

В конце концов, да. Первоначально я просто хочу создать приемлемое решение. Надеюсь, когда я получу эти простые ограничения, я могу расширить его, чтобы соблюдать более конкретные предпочтения отдельных людей. – Larsenal

Я понимаю, что вы пытаетесь сделать это с помощью подхода, основанного на ограничении, поэтому я не предлагаю это в качестве ответа, но только для информации вы также можете найти двухсторонний подход к интересному альтернативному подходу. См. Например: http: //stackoverflow.com/questions/1221990/hungarian-algorithm-and-multiple-factors/1222263#1222263 –

Если у вас есть 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

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

источник

2009-09-08 17:16:16

Простите, что я не знаком с терминологией, но что будет примером целевой функции? – Larsenal

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

Спасибо за понимание. Как только я получу шанс попробовать это, я вернусь к этому вопросу, чтобы получить ответ. – Larsenal

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

ответ

Смежные вопросы