# Modeling of a special form of the precedence constraint

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?

• I don't understand your question. Are you asking how to add precedence constraints to the model? Commented Jun 8, 2023 at 11:03
• @Brannon, yes of course. Commented Jun 8, 2023 at 11:52
• You have start time variables? Are those start times resource-dependent? Are the job-delays resource-dependent? Commented Jun 8, 2023 at 12:51
• And I assume that you don't have travel/setup times between jobs? Commented Jun 8, 2023 at 12:58

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.
$$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$$