views:

284

answers:

1

I have the following simple problem that I'd like to use to experiment with MS Solver Foundation:

I have a schedule where I need to have 2 workers per day for 30 days. I need to honor the following constraints:

  • No people should work two days in a row.
  • Unless a special exception is applied, people should only work once per week.
  • Some people can only work weekends.
  • Some people can only work weekdays.

I plan to use C# to populate the model, but I need help getting started with the modeling. I'm not sure how to setup the decisions, parameters and constraints to address this type of problem.

Update: While ire-and-curses has a good start, I have to imagine that there's a more declarative way to express those constraints using the framework rather than have to code them individually for every person. Anyone more familiar with MSF that can help with this construction?

A: 

If you have n people, you will have to define 30n binary integer parameters each indicating if a person works on a specific day or not.

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

Then you need constraints to prevent working on two days in row. This will be 29n constraints.

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

Then you need constraints to work only once per week. This will be the following for the first week and similar for the next three weeks.

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

The last week will just be the following.

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

This will yield another 5n constraints. Then add constraints for weekdays only

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

and weekends only

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

and finally add a target function.

Daniel Brückner
Pardon my lack of familiarity of the terminology, but what would be an example of a target function?
Larsenal
The traget function represents the goal you want to optimize. I would have given an example, but I could not come up with a meaningful one. Maybe maximize the number of people working for zero days and hence minimize the number of people required to fullfil the work. But I am not sure how this can be expressed in SolverFoundation because I heared about it just an hour ago.
Daniel Brückner
Thanks for the insight. Once I get a chance to try this out, I'll return to this question to award an answer.
Larsenal