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
- Each shift must have at least: two drivers, one doctor and three medics.
- 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.
Best Answer
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.