Modeling of a special form of the precedence constraint

Question

There exists a scheduling problem in which some tasks should be processed on some resources. Additionally, each task needs to be assigned to a specific position on each resource. Let the decision variable $x_{j,p,m}$ take the value $1$ if task $j$ is being assigned to position $p$ on the resource $m$, otherwise $0$. Also, one of the limitations on the model is a precedence constraint that defines as a precedence graph $G(V, E)$ in which tasks are nodes and relations are edges. ($(i \rightarrow j)$ means task $i$ should be processed before task $j$). As the problem is large-scale it is separated into two models. The following constraints are some of the parts of the first model.

\begin{align} \sum_{p,m} x_{j,p,m} = 1 && \forall j \in J && (1)\\ \sum_{j} x_{j,p,m} \leq 1 && \forall p \in P, m \in M && (2)\\ \end{align}

The first ensures assigning each task to each position, and the second for occupying positions. The above constraints have integrality property and we are willing to keep that.

I was wondering if, is there any precedence constraint that follows this integrality property? If NO, is there any form that being as tight as possible?

Answer 1

One option is to enforce the precedence via constraints on the start and completion times. Let $s_{j,m}$ be the start of job $j$ on machine $m$ with delay $d$ that finishes at time $c$. Let $x_{j,m} \geq x_{j,*,m}$. We have constraints like: $$ c_{j,m} \geq s_{j,m} + d_{j,m}x_{j,m} $$ We can group (e.g. max) those into per-job start times: $$ c_{j} \geq c_{j,*} $$ Then we can enforce precedence like so: $$ s_{k} \geq c_{j} $$ It's also common to define a binary variable $x_{j,j',m}$ where $j$ happens before $j'$. If you utilize this approach you can simply constrain certain of those values to be 1. If you have travel/setup times, meaning that $j$ must immediately precede $j'$, then this won't work for precedence, and you'll be back to constraining completion times.

Answer 2

I can think of something similar to @Robpratt suggestion in another problem

$s_i+d_ix_{i,p,m} \le s_j + M(2-x_{i,p,m}-x_{j,p',m}) \ \ \forall p,p': p \le p'$
where $s,d $ are start times and duration(this is given) for tasks $i,j$ on resource $m$