[SciPy-User] Turnover Optimization

[Lorenzo Isella]

Dear All,
I hope this is not too off-topic.
I am working on a problem that, without too much details, resembles the
time allocation of work shifts.
Let us say that you have a sequence of N contiguous time slots (let us
assume for now that all the slots have the same duration delta).
I also have a set of individuals {x_i} which I need to assign to each
time slot with the following conditions

(1) at each time slot 2 different individuals x_i and x_j, i!=j, must be
at work
(2) if x_i works at the m-th time slot, then he cannot work at the m+1th
slot
(3) each x_i must work a number k_i of time slots such that \sum_i
k_i=N.

There may be other other (almost endless) rules one may want to add:
certain time slots may be unaccessible for an individual or certain
coupling x_i,x_j may be forbidden, but you get the idea.

How to tackle this problem? I would like to know first of all if, for a
given set of boundary there is a solution and if not, what is the
solution 'closest' (here I may need to introduce a concept of distance
or a penalty function) to the given constraints.
Should I try to evolve the system starting from a random allocation of
the time slots and rooting out at each generations those allocations
which do not respect the constraints? Can the problem be solved exactly
in some cases? Also having an idea of the degeneracy of the possible
solutions would be good.
Any suggestion is appreciated.
Best Regard

Lorenzo

P.S.: it goes without saying that it would be an added bonus to have an
algorithm that allows for the easy implementation of extra
rules/variations of the existing rules (e.g. three people at work
simultaneously and so on)