How to linearize non-overlapping constraints for multiple intervals ? (in scheduling problems)

 0 I know how to linearize non-overlapping constraint for two intervals. For example, [l1,u1] and [l2,u2]. Non-overlapping means that they do not have intersection, so I can use the following logical constraint: u10; l2-u1+M*(1-s)>0; l1-u2-M*(1-s)<0.  However, if there are more than two intervals, for example, 3 intervals. Then there will be 6 possibilities: u1

 1 You need only the second and third constraints out of four in your big-M formulation for two intervals. For $$n$$ intervals, you need only $$n \choose 2$$ binary variables and twice that many constraints, with one variable and two constraints per pair of intervals. You can omit these for the pairs that you allow to overlap. To allow at most $$m$$ jobs (intervals) to overlap at a time, you can introduce additional binary variables and constraints to assign the jobs to $$m$$ machines and impose the nonoverlapping constraints on the jobs assigned to each machine. answered 09 Oct '16, 11:16 Rob Pratt 1.2k●2●6 accept rate: 28% Dear Rob, Thank you very much for you answer. I've figured out your answers to my first two questions. However, I'm still not quite clear on the last question. Consider such a case: You have n jobs, n machines (rather than m), each job assigned to a machine. However, only m jobs can be performed simultaneously. (10 Oct '16, 00:51) Sulivan Cheung If you already have $$n$$ real machines and want to enforce that at most $$m < n$$ are active simultaneously, you can introduce $$m$$ virtual machines just for that purpose. Alternatively, if the set of possible start times is finite, you can introduce a binary variable $$x_{i,t}$$ for each job $$i$$ and start time $$t$$ and then impose a cardinality constraint $$\sum_i \sum_{t':t' \le t < t'+d_i} x_{i,t'} \le m$$ for each $$t$$, where $$d_i$$ is the duration of job $$i$$. (10 Oct '16, 10:52) Rob Pratt
 0 I see that your question is tagged "constraint-programming", and indeed constraint programming (CP) makes sense if you are solving this type of scheduling problem. In CP you do not need to linearize your non-overlapping constraints as there exist predefined constraints for that. For example in CP Optimizer (available inside CPLEX Optimization Studio), you would just add a constraint noOverlap([x1,...,xn]) where xi are interval variables. answered 13 Dec '16, 11:31 Philippe Lab... 62●3 accept rate: 9%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: