Search code examples
modelconstraintsschedulingms-solver-foundation

How to model simple scheduling problem using MS Solver Foundation?

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?

Solution

  • 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.