Monday, January 26, 2009

Scheduling: limits on number of periods active.

How to model that an employe must work at least as 5 successive periods  and at most as 8 successive periods with mathprog.

There are a few ways to model this, and without knowing more about the model it is difficult to give definite advise, but here is a suggestion of a possible formulation taken from a machine scheduling model I developed a little while ago:

param MAXT := 25;
param MIN := 5;
param MAX := 8;
set T := {1..MAXT};

var x{T}, binary;
var SwitchOn{T}, binary;
var SwitchOff{T}, binary;

switch1{t in T: t > 1}: x[t]-x[t-1] = SwitchOn[t]-SwitchOff[t];
switch2{t in T}: SwitchOn[t]+SwitchOff[t] <= 1;

init1: x[1] = 0;
init2: SwitchOn[1] = 0;
init3: SwitchOff[1] = 0;

minimum{t in T}: sum{i in 1..MIN:t+i-1<=MAXT} x[t+i-1] >= MIN*SwitchOn[t];
maximum{t in T:t+MAX<=MAXT}: x[t+MAX] <= 1-SwitchOn[t];

I ignored the details about what to do with the boundaries. The last condition adds also an implied restriction on when the machine can be turned on again (after 8 periods), so it may be better to model this as:

maximum{t in T:t+MAX<=MAXT}: sum{i in 1..MAX+1:t+i-1<=MAXT} x[t+i-1] <= MAX + 1 - SwitchOn[t];

For multiple persons j we would need x[j,t], SwitchOn[j,t], SwitchOff[j,t]. A different way would be to organize x[j,t,len] where t is the start time and len is the length of occupation (len=5,6,7,8). This approach has more integer variables but may solve fast depending on the situation.