# How does the RCPSP's precedence constraint work?

In [1] the authors define the RCPSP (resource-constrained project scheduling problem) as follows:

minimize $$\sum_{t} t x_{n t}$$ subject to $$\begin{array}{c} \sum_{t} x_{j t}=1, \quad j \in J, \\ \sum_{s=t}^{T} x_{i s}+\sum_{s=0}^{t+d_{i j}-1} x_{j s} \leq 1, \quad(i, j) \in L, t=0, \ldots, T, \\ x_{j t} \geq 0, \quad j \in J, t=0, \ldots, T, \\ x_{j t} \text { integer, } \quad j \in J, t=0, \ldots, T \\ \sum_{j} r_{j k}\left(\sum_{s=t-p_{j}+1}^{t} x_{j s}\right) \leq R_{k}, k \in R, t=0, \ldots, T . \end{array}$$

What I do not understand here is the second constraint, which is the precedence constraint. Why do we need the sum $$\sum_{s=t}^{T} x_{i s}$$ and cannot just use $$x_{i t}$$ instead? Would'nt $$x_{i t}+\sum_{s=0}^{t+d_{i j}-1} x_{j s} \leq 1, \quad(i, j) \in L, t=0, \ldots, T \\$$ be enough to be sure that if the predecessor starts at time t the successor j cannot start at any time before $$t+d_{i j}$$, when $$d_{i j}$$ is the enforced time lag between the predecessor i and succesor j (which equals the duration of the predecessor if we have strict finish-start precedence constraints)?

[1] Möhring, Rolf H.; Schulz, Andreas S.; Stork, Frederik; Uetz, Marc (2003): Solving Project Scheduling Problems by Minimum Cut Computations. In: Management Science 49 (3), S. 330–350. DOI: 10.1287/mnsc.49.3.330.12737.

• Many thanks for your suggestion. would you say please, if the following constraints are replaced instead of the second constraints, is there any reasonable change in the complexity of the model? $\sum_{t\in \mathcal{T}} t\cdot x_{(i,t)} - \sum_{t \in \mathcal{T}} t\cdot x_{(j,t)} \geq p_{j} \,\,\, \quad \forall (i,j) \in L_{(i,j)}$ Where $p_j$ is the processing time of job $j$. Apr 4 at 8:42
• @A.Omidi it looks like you have $i$ and $j$ reversed, but that idea also works. Not sure which will perform better. Apr 4 at 13:12