[SciPy-User] Turnover Optimization

nicky van foreest vanforeest@gmail....
Wed Jul 28 13:27:54 CDT 2010

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

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



More information about the SciPy-User mailing list