1

I'm writing a application that will decide the scheduling plan for a few dozen people according to their occupation (role) and availability (week day and hours).

I've used a excel spreadsheet to help solve this problem, I was then able to devise a logical and decision based approach to assign these people to shifts and roles, following a few set of constraints.

When I was about to write this into code, I was suggested to try Microsoft Solver. I've read a while about it's capabilities but I'm unfamiliar with some terminology encountered.

Well, suffice it to say that I never used Microsoft Solver and I do not even know if the following scheduling problem can be solved with it or not. So far I've found very few examples about scheduling problems and even those are simple by comparison.

So my question is, can Microsoft Solver solve the following scheduling problem?


Scheduling problem

Assign people to shifts for an entire week based on their availability and what role they are qualified to fill following a few set of constraints and goals.

Structure

  • Weeks are composed of seven days.
  • Days are composed of shifts (dawn, morning, afternoon and night sifts are the most common). Shifts are specified in this way:
    • Dawn: 00:00 AM -> 08:00 AM
    • Morning: 08:00 AM -> 12:00 AM
    • Afternoon: 01:00 PM -> 07:00 PM
    • Night: 07:00 PM -> 00:00 AM
  • There are some weekdays which might not have any shifts while others can have one, two or more.
  • Each person has a weekly availability following the same week day / shift structure.
    • Example: Peter is only available on Monday night's (Monday 07:00 PM -> 00:00 AM).
  • Sometimes people have two or more days on which they are available and would like their schedule to rotate through these.
    • Example: Kyle is only available on Wednesday night's and Thursday morning's, also he would like to rotate them. One week Wednesday another week Thursday.
  • Each person has a set of roles he or she can fill (one or more).
    • Driver
    • Medic
    • Doctor

Goals

  1. Each shift must have at least: two drivers, one doctor and three medics.
  2. Every person with availability must be assigned to a shift, it does not matter if one shift has three drivers while another only has two.

Constraints

  • A person can only fill one role per shift.
  • A person can only be assigned to a shift if he or she has availability to perform it.
  • A person can only be assigned to a role if he or she is qualified to perform it.
  • A person can only be assigned to one shift per week, unless when the organization is understaffed (by understaffed means we need more people to fill shifts to meet goal #1). If thats the case one additional condition applies when assigning people to shifts after the first one.
    • A person assigned to a second shift in the same week must be the person that hasn't performed a second shift for the longest time, while still meeting the person's availability and role capability.

Moderator note: Could not find the appropriate tags.

  • 3
    This is a discrete, not a continous problem, so the "Evolutionary Algorithm" approach of the Solver might work much better than the linear simplex algorithm for this case. But why don't you just start with a simplified version with your problem, try to make a solver model and try it out? If that works, try to extend the model step-by-step. – Doc Brown Jun 26 '14 at 6:45
  • 1
    This reminds me of Integer Linear Programming which I searched a few days ago. This problem is NP-complete in generic form. – InformedA Jun 26 '14 at 7:18
  • "A person can only be assigned to one shift per week," - so as long as the organization is not understaffed, the persons in your example only work 8 hours per week at maximum? Really? – Doc Brown Jun 26 '14 at 7:43
  • @DocBrown: Yes, the organization is made up of volunteers, therefore 8 hours per week is quite normal. – Fábio Antunes Jun 26 '14 at 12:32
  • @DocBrown: How would a evolutionary algorithm solve this problem and how could one apply it? Could you possibly provide insight about it on your answer. – Fábio Antunes Jun 26 '14 at 12:54
5

If Solver is appropriate depends primarily on how you build your model for the given problem, and if the problem size stays within the boundaries of the solver. According to this site, the limit for Excel Solver is 200 decision variables and 100 constraints (they are also promoting their premium solver product for bigger problem sizes). But when you use Microsoft Solver Foundation directly from C#, and not the Excel add-in, the limits are much higher, depending on the Solver variant at least 5000 constraint terms.

Some ideas how to build a model:

  • you may create a model involving a 0-1-matrix with one row per "person" and 28 columns "shifts of the week" (assumed there are 4 shifts per day). The roles could be added by extending the matrix value interval from 0-1 to 0-3, (0=not assigned, 1-3 assigned for a specific role) so without additional decision variables.

  • or you assume that each person takes at maximum 3 shifts per week (even in the "understaffed" case), you may build your model in a different way, using the columns for indexes from 0 to 28, pointing to "first shift of the week, second shift, third shift" (0="not assigned"). Adding the roles to this second model may involve 3 additional matrix columns for the roles of the first/second/third shift.

Then you have to build your constraints accordingly. For example the constraint "minimum needed roles per shift" will result in at least 3 x 28 solver constraints (3 per shift, summing up the number of "roles" assigned for that shift and telling the solver how many persons are expected at minimum for that role). Each of the four constraints you listed above for the persons will need at least one corresponding solver constraint,

I hope you got the idea of how to estimate the problem size from the above. On that estimation, decide for yourself if these limits are sufficient to solve your problem, and which solver variant you need.

  • Excel solver is really not the end point. The end point would be a CSharp application that would generate and attempt to solve such model based on data provided. However before that I would surely try it with Excel to determine how feasible it is. I will attempt to break it down based on your modeling ideas. – Fábio Antunes Jun 26 '14 at 12:52
  • @FábioAntunes: FWIW, here is an example of a similar (but probably simpler) type of problem, attacked by using the solver foundation: codeproject.com/Tips/744558/… – Doc Brown Jun 26 '14 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.