I know how to linearize nonoverlapping constraint for two intervals. For example, [l1,u1] and [l2,u2]. Nonoverlapping means that they do not have intersection, so I can use the following logical constraint:
Then I introduce a binary variable s and a big M to linearize it to:
However, if there are more than two intervals, for example, 3 intervals. Then there will be 6 possibilities:
I don't how many binary variables I need to introduce in order to linearize these constraints. More generally, for n intervals, there will be n! possibilities. Is there a way to linearize the nonoverlapping constraint for all n intervals other than list out all possibilities? Furthermore, it will be even more difficult if I allow some intervals to overlap with each other. It is quite commonly encountered in scheduling problems: there are n operations to be performed, at most m(m<n) of them are allowed to be performed simultaneously. How do I linearize such a constraint? asked 09 Oct '16, 04:28 Sulivan Cheung 
You need only the second and third constraints out of four in your bigM 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 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

I see that your question is tagged "constraintprogramming", 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 nonoverlapping 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... 