2
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

Yes, your proposal suffices. But the published second constraint is stronger, yielding a tighter formulation. You can think of it as a lifting obtained by using the first constraint.

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$
    – A.Omidi
    Commented Apr 4, 2021 at 8:42
  • $\begingroup$ @A.Omidi it looks like you have $i$ and $j$ reversed, but that idea also works. Not sure which will perform better. $\endgroup$
    – RobPratt
    Commented Apr 4, 2021 at 13:12
  • $\begingroup$ RobPratt, Thank you for your answer. @A.Omidi I can't answer your question, but this version of the constraint is used e. g. in [2] on page 54. Maybe that helps for your research. [2] Artigues, Christian; Demassey, Sophie; Neron, Emmanuel (Hg.) (2008): Resource-constrained project scheduling. Models, algorithms, extensions and applications. London, Hoboken, NJ: ISTE; Wiley $\endgroup$ Commented Apr 4, 2021 at 14:12
  • $\begingroup$ NoThanks93330, thanks for the mentioned reference. @RobPratt, thank you for your answer. $\endgroup$
    – A.Omidi
    Commented Apr 4, 2021 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.