Good evening! I am studying scheduling problems and I have some difficulties understanding constraints of potentials:

Let be $t_j$ the time when a task $j$ starts, and $t_i$ the time when a task $i$ starts. I'm assuming that $a_{ij}$ is the length of the task $i$ but I'm not sure. Why is a "constraint of potential" mathematically expressed by:

$$t_j-t_i \le a_{ij}$$

Shouldn't it be the reverse, $t_j-t_i \ge a_{ij}$? If we know that the length of task $i$ is $a_{ij}$, isn't it impossible to do something in less that the necessary allocated time?


I suspect there's some misunderstanding about the definition/meaning of $a_{ij}$. The time to complete task $i$ depends only on $i$ (not on $j$), so it wouldn't make sense to use notation like $a_{ij}$ for the length of task $i$: we'd instead expect to see only the index $i$, but not $j$, appear in that notation.

I suspect you'll probably need to go back to your textbook or other source on scheduling and look for a precise definition of the notation that it uses. If your textbook doesn't define its notation, look for a better textbook.

As far as the constraint $t_j - t_i \le a_{ij}$, that is expressing that $t_j$ should start at most $a_{ij}$ seconds after $t_i$ starts. So, it'd make more sense for $a_{ij}$ to be a permissible delay that expresses the maximum time you can wait to start task $j$, once task $i$ has been started.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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