Hi!
I've got a friend who is a nurse and she constantly complains about the stupid schedules she (and her colleagues) have to work by.
So, being a programmer, I thought, hey, how hard could it be? I still remember a lecture about it 15 years ago so, maybe it's a nice hobby project and I can gain some skills in the field of optimization. So I got myself Eiben and Smith's Introduction to Evolutionary Computing and took to the couch..

Guess what, it /can/ be hard. And I'm still in the middle of figuring how to do it. This is how far I got:

I think I'm pretty clear on how to do the fitness evaluation, the criteria are easy to understand, some being logical (a nurse cannot be assigned twice to the same shift), others legal (how much rest shifts after x day/night shifts) and some are soft (equal work distribution over time and over all nurses, "I like weekend/night/morning shifts", "I'm not talking to that b****" and other personal preferences).

However, I'm pretty stuck on how to do the representation and the operators. First I thought a simple bit string would do but there most operators will create a bunch of logically impossible schedules.

Right now I'm thinking about some sort of structure with a "growth" function, that is, a function that gets the genotype and produces the phenotype by mapping the set of different genotypes into the set of logically and legally possible phenotypes (schedules).

Here's my idea:
I've got a table with s rows, one for each shift, ordered chronologically.. Each row contains an ordered sequence (that is one permutation) of all nurses, 26 in my case.
The growth function traverses the rows in chronological order and, in each row, selects the first n legally available nurses (6 for day shifts, 2 for night shifts) in the sequence. The result, of course depends on the call-order of the nurses in any particular shift:

Given:
S1: N1,N2,N3,N4,N5,N6,N7,N8,N9,N10,N12,...,N26
S2: N1,N2,N3,N4,N5,N6,N7,N8,N9,N10,N12,...,N26 (just to show how the grower would deal with it)
S3: N17,N1,N2,N24,N18,N26,N5,N13,N19,N21,...(more realistic permutation)

The grower would produce:
S1= N1,N2,N3,N4,N5,N6
S2= N7,N8,N9,N10,N11,N12
S3= N17,N24 (night shift)

Would that be an acceptable representation and growth algorithm or am I overdesigning it? One problem is that many possible permutations will map to the same schedule. Does that wastage matter? Can it be avoided? Are there any standard representations that would be more efficient?

As for the operators, I think mutation is easy. I can think of five different ones:
1) Pick a shift and shoot up the permutation. This has the advantage that there's a chance for each possible permutation to actually happen. Problem is, if it happens in the wrong place, it doesn't much good, does it?
2) Pick two shifts and exchange them. No problem but limits the set of permutations to at most the set in the initial population. The advantage is that a particular permutation could find a spot where it could do more good.
3) Pick a shift, pick two nurses and exchange their positions. Would create variety but slowly.
4) Pick a shift and switch the first n nurses with the last 26-n ones, n being chosen randomly.
5) Pick two shifts and replace the second shift permutation with a copy of the first one. Doesn't create variety but allows a good permutation to multiply.

However, I'm a bit at a loss of which one or which ones would be good in my case. Are there commonly well regarded operators for this kind of representation? Are any one having a particular beneficial or detrimental effect on the solution quality? Could I use more than one mutation operator?

As for procreation, I'm not sure at all which way to do this.
I could do it "horizontally", that is, switch bits of the schedule, like combining the first three weeks of one parent with the last two of the other. but I could also do it vertically, by recombining each permutation using one of the standard permutation recombinators.
The first one is probably the conventional one, but it will lose permutations rather quickly, won't it?
The second one will generate lots of new permutations but I don't see how this recombination is different from just a big mutation. I think that the recombinator ought to do what animal breeders expect it to do too, that is, create children that inherit favorable traits. I can't picture the second one doing this.

Any thoughts?

(FWIW I haven't made any commitments at all, so I'm not under pressure. It's really a fun project.)

Lots of Greetings and thanks for your patience!
Volker