Sunday, April 8, 2012

Precedence constraints

I often see precedence constraints for time indexed scheduling models formulated as:


Here x(j,t)=1 if job j starts in t (and 0 otherwise). p(i) are the processing times and P is the set of precedence relations.

I would probably write this as:

imageWe add a few variables here but save hopefully some nonzero elements. In addition we may reuse s(j) in other parts of the model.

Now I encountered a formulation like:


I thought about this a little while but I don’t think there is any special advantage to this formulation. (Consider that sum(t,x(i,t))=1).