[SciPy-User] Turnover Optimization

[nicky van foreest]

Hi Lorenzo,

This appears to me to be a typical scheduling problem. You might
consult one of the books of Pinedo, or Peter Brucker, to see whether
it has been solved.

> (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

You might as well (it seems to me at least) say that once x_i works at
the m-th time, he also works at the m+1 th time. Then you have to
compensate in the restrictions such that the occupation for each slot
is 4, and such that the sum of the allocated slots for each worker is
2N.

> (3) each x_i must work a number k_i of time slots such that \sum_i
> k_i=N.

I am pretty sure your problem is hard, np-complete or something the
like. I tried to tackle a similar problem, but I could only solve
small instances, 40 workers or so, and I had to use a good IP solver
for this, in my case, gurobi.

I can send you some code I used for my problem (in pulp), but then
send me a private mail to prevent clutter on this mailing list.

bye

Nicky