Best model for precedence constraints within scheduling problem

Question

Suppose I'm modeling a problem where I want to compute the start time bucket for some jobs. All time buckets have equal duration. There are some additional constraints involved but I also have to model some precedence constraints for certain jobs.
Due to the rest of the model I have to use binary variables $s_{jt}$ that are 1 if job $j\in J$ starts in time bucket $t\in T$. Suppose I furthermore have a set $P$ of tuples of jobs $(j_1, j_2)\in P\subset J\times J$ for which the second has to start after the first is finished. Each job $j$ has duration $d_j$, i.e the number of time buckets that are needed to finish the job.

My question is how to model the precedence constraint using the above variables (plus maybe some additional ones) in the most efficient and/or effective way. Meaning I'm interested in the smallest formulation but also in the formulation that gives the tightest bound, respectively the fastest solving times when solved with a MIP solver.

Answer 1

Can you change the meaning of your variables? A classic trick when you have a lot of precedences is to use the by formulation.

Let $s'_{jt}$ be 1 if job $j$ starts by time $t$ (i.e. at time $t$ or before). In that case, your precedence constraint can be formulated as $$s'_{j_2,t} \leq s'_{j_1,t-d_1}$$

Notice that you can do a change of variables ($s_{j,1}=s'_{j,1}$ and $s_{j,t} =s'_{j,t}-s'_{j,t-1}$) to write the remaining constraints with these new variables. You also need to add constraints $s'_{j,t}\leq s'_{j,t+1}$.

This usually provide a very tight bound, specially if the number of precedence constraints is very large and the additional constraints are just a few (see [1]).

Answer 2

A straightforward formulation that suffices is to impose conflict constraints of the form $$s_{j_1,t_1}+s_{j_2,t_2}\le 1$$ if $t_1+d_1>t_2$, but you can strengthen that to $$\sum_{t\ge t_1}s_{j_1,t}+\sum_{t\le t_2}s_{j_2,t}\le 1.$$

Answer 3

May I suggest CP-SAT modeling. See this incomplete section. And a few examples:

• Complex jobshop in C++
• Single Machine Weighted tardiness in C++
• RCPSP in Python
• Gate scheduling in Python
• Single machine scheduling with setup and release date in Python

Answer 4

The smallest formulation will be with these constraints:

$$\sum_{t}t\cdot s_{j_1,t} + p_{j_1}\leq \sum_{t}t\cdot s_{j_2,t},\quad \forall (j_1,j_2)\in P$$

However, much stronger LP relaxation will be with constraints

$$\sum_{t'\leq t}s_{j_1,t'}\geq \sum_{t'\leq t+p_{j_1}}s_{j_2,t'},\quad \forall (j_1,j_2)\in P, \forall t$$

(or its equivalent form suggested by @Borelian, which produces a much sparser matrix).

Having to handle precedence constraints usually makes a scheduling problem much more complicated when solved by MIP approaches. So a CP approach can be more efficient, as suggested by @Laurent.