Monday, September 14, 2009

Scheduling question

>I thought it would be easy, and I could not find how to do it.
>Assume I have an ordered set of decisions x[100].
>I would like to express in OML these requirements:

> All these decisions should be equal to 1 (positive decisions), except for a subset where the
> decisions should be 0 (negative decisions).

>All the negative decisions should be adjacent in the ordered set of decisions.
>For example, all negative decisions could be from slots {13,14,15,16,17,18,19}.
>On the contrary, the set {5,6,7,13,14,15} could not be a valid set of negative
>decisions as they are not all adjacent (missing 8 to 12).

>Could such constraints be expressed in OML?

This problem is often seen in scheduling of machines where they can not be turned on more than a number of times. There are well-known standard formulations for this. E.g.

binary variable turnon[t];  
turnon[t] >= x[t]-x[t-1];
Sum[t, turnon[t]] <= 1;

The binary variable may be relaxed to a continuous variable between [0,1] to improve performance.