ansaurus

Question

Scheduling Algorithm for Maintining Two Dimensional Constraint

Answer 1

+1 A:

As the comments suggest, this is a schedule for machinery - for humans, we need more input. Also, this "Genetic Algorithm" is a little too high level for this task. You can do this with arrays/objects, iteration, configuration settings, and recursion.

What language are you using?

cinqoTimo 2010-10-15 01:21:42

I am actually using c#.

Nassign 2010-10-15 07:15:42

Answer 2

+1 A:

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 ;)

anonymous_21321 2010-10-15 01:30:04

ansaurus

tags:

views:

answers:

Scheduling Algorithm for Maintining Two Dimensional Constraint

related questions