Scheduling Algorithm for Maintining Two Dimensional Constraint

Question

I have been tasked to do a scheduling program in my company. Basically given N employee you should schedule them shift for the month. I tried to do this via brute force and ordered priority of constraint. However, I am having problem when trying to maintain vertical and horizontal constraints.

Vertical constraints, all person should have equal number of shift per month. (e.g. They should be within the average number of day shift, night shift, rest day, early shift) However, there is also a day horizontal constraint that the number of shift per day should be equal daily.

I tried searching the internet and I usually read answer on using Genetic Algorithm. In my study of Genetic Algorithm, it seems the algorithm is not that suitable in my case. Does anybody know how to solve such problem?

Additional Illustration based on Enigmativity's comment: Basically there are 4 shifts,

The Y's are the employee shift total for the month which needs to be evenly distributed per employee. (ie each employee should have equal (or just difference by one) amount of shift type for the month) - Vertical constraint.

The X's are the daily total for all employee, basically each shift should also be evenly distributed for weedays and for weekends. - Horizontal constaint

Also, there are other constraint like desired shifts and adjacent shifts. But I tried to simplify it with just these even out rules for now.

--------------------------------------------------------------------------------
| Employee | 1  | 2  | 3  | 4  | + + + | 28 | 29 | 30 | 31 | S1 | S2 | S3 | S4 |
--------------------------------------------------------------------------------
| EmpA     | S3 | S4 | S1 | S2 | + + + | S3 | S4 | S1 | S2 | Y  | Y  | Y  | Y  |
--------------------------------------------------------------------------------
| EmpB     | S1 | S3 | S4 | S1 | + + + | S2 | S3 | S4 | S1 | Y  | Y  | Y  | Y  |
--------------------------------------------------------------------------------
| EmpC     | S2 | S1 | S3 | S4 | + + + | S1 | S2 | S3 | S4 | Y  | Y  | Y  | Y  |
--------------------------------------------------------------------------------
| EmpD     | S2 | S2 | S2 | S3 | + + + | S4 | S1 | S2 | S3 | Y  | Y  | Y  | Y  |
--------------------------------------------------------------------------------
| S1       | X  | X  | X  | X  | + + + | X  | X  | X  | X  |    |    |    |    |
--------------------------------------------------------------------------------
| S2       | X  | X  | X  | X  | + + + | X  | X  | X  | X  |    |    |    |    |
-------------------------------------------------------------------------------
| S3       | X  | X  | X  | X  | + + + | X  | X  | X  | X  |    |    |    |    |
--------------------------------------------------------------------------------
| S4       | X  | X  | X  | X  | + + + | X  | X  | X  | X  |    |    |    |    |
--------------------------------------------------------------------------------

Answer 1

I am currently working on a nurse scheduling problem that sounds very similar to yours. The objective is to schedule a shift (or day off) for each nurse on each day so that they both work the right number shifts (40hr work week) and meet the baseline shift requirements per day (3 nurses monday, 2 tuesday, etc.). This is a well know problem and, like any other scheduling problems, it is NP-Hard.

I agree with your comment that genetic algorithms are not well suited for this task (or for any task imo). There are far better approaches to solving this problem and they have been studied and well documented in the constraint programming and operation research fields.

My advice would be to take a mathematical programming language to model your problem and encode it as a constraint programming problem or a mixed integer linear program (MILP). There are a number of languages that let you encode these problems at a high level, the best known one would probably be AMPL. You can search for a nurse scheduling example's for that language that would probably help a lot. The AMPL language can compile easily into a MILP which can then be passed off to a solver like GLPK or CPLEX. Also, if you are in academia or have a fairly decent budget for this problem you should consider getting IBM's ILOG CPLEX package and coding your problem in their supported Optimization Programming Language (OPL). This is the language/solver that I am using and I am very happy with it.

Keep in mind this is and extremely difficult problem from a computational standpoint and I would make sure you are familiar with the difficulty before you put out any cost estimates for the project.

Edit: Since you upgraded your question let me upgrade my answer, here is working OPL code to solve your problem. I'll use OPL because I don't know AMPL but the two languages are very similar, you could easily translate.

using CPLEX;

int nbShifts = ...;
int nbDays = ...;
int nbEmpl = ...;

range sRng = 1..nbShifts; // for indexing                                                           
range dRng = 1..nbDays;
range eRng = 1..nbEmpl;

int shiftsWorked[eRng] = ...;  // number of shifts each employee works                              
int shiftsRequired[dRng][sRng] = ...;  // number of shift s required on day d                       

dvar int Assignments[eRng][dRng][sRng] in 0..1; // boolean matrix, 1=working 0=not working          

subject to  {

  // work at most 1 shift per day                                                                   
  forall(e in eRng, d in dRng)
    (sum(s in sRng) Assignments[e][d][s]) <= 1;

  // "vertical" constraint                                                                          
  forall(d in dRng, s in sRng)
    shiftsRequired[d][s] == (sum(e in eRng) Assignments[e][d][s]);

  // "horizontal" constraint                                                                        
  forall(e in eRng)
    (sum(d in dRng, s in sRng) Assignments[e][d][s]) == shiftsWorked[e];

}

// to print out A, in nicer format                                                                    
execute {
  write("\n");
  var flag;
  for (var e=1; e <= nbEmpl; e++) {
    for (var d=1; d <= nbDays; d++) {
      flag=0;
      for (var s=1; s <= nbShifts; s++) {
        if (Assignments[e][d][s] == 1) {
          flag=1;
          write(" S",s);
        }
        if (s == nbShifts && flag==0) write(" __");
      }
    }
    write("\n");
  }

}

You could run this code with a .dat file like this:

nbShifts = 4;
nbDays = 7;
nbEmpl = 4;
shiftsWorked = [ 5 5 5 5 ];
shiftsRequired = [[3 0 0 1] [1 1 0 0] [0 0 1 1] [1 1 1 1] [0 0 0 0] [1 0 0 3] [0 2 2 0]];

And get the following output in less than a second:

 S1 __ S3 S4 __ S4 S3
 S1 __ S4 S3 __ S4 S3
 S1 S2 __ S2 __ S4 S2
 S4 S1 __ S1 __ S1 S2

I wish someone would have told me this when I started my problem ;)

Answer 2

Have you taken a look at Drools Planner (open source ASL, Java)? There's a nurse rostering example (= employee shift rostering), very similar to what you're doing and it's riddled with constraints.