1
$\begingroup$

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?

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

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks for sharing your idea. Actually, the first approach is based on the interval variables like what you pointed out, but in the first phase we do not want to incorporate such the variables. For the second, it seems to be a good start point, but as I mentioned the sequence of tasks is based on the position and coupling the new variables as you mentioned can causes some difficulties on the running time. Do you have any idea to apply this precedence on the position instead of tasks? $\endgroup$
    – A.Omidi
    Jun 8, 2023 at 18:41
  • $\begingroup$ By "position" you mean the order in the machine assignments? And how do you run without interval variables? Do your tasks all take the same amount of time? $\endgroup$
    – Brannon
    Jun 9, 2023 at 19:11
  • $\begingroup$ for the first part, yes. For the second the internals will define in the second phase. $\endgroup$
    – A.Omidi
    Jun 9, 2023 at 19:53
0
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ Dear @Sutanu, thanks for your suggestion. As I mentioned in my comments, the interval variables are applied in the second phase. The first phase is just based on assigning variables, and the gain here is the integrality property. I will change the question a bit to clarify what I want asap. Thanks once again. $\endgroup$
    – A.Omidi
    Jul 9, 2023 at 5:54

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.