# Alternative way to restrict an employee to work on multiple jobs

Suppose I have a set of employee $$E$$ and set of jobs $$J$$ in a given time horizon $$T$$. I would like to make sure that no employee works on multiple jobs where each job $$e\in E$$ takes a certain amount of time presented as $$\delta_e$$.

Let $$X_{ejt}$$ be a binary variables stating if employee $$e$$ starts working on job $$j$$ at time $$t$$. Then, I can write;

$$M(X_{ejt}-1) \geq \sum_{i \in J \setminus \{ j\}} \sum_{t^* : t \leq t^* < t + \delta_j} X_{eit^*}, \quad \forall e \in E, j \in J, t \in T$$

where the constraint ensures that employee $$e$$ cannot work on another job until their current job is completed.

My question is that if there is a better way to accomplish this with a more effective constraint without leaning on a big-M constraint. When I say efficient, I mean it should work better during the B$$\&$$B process.

• Does $X_{ejt}=1$ mean employee $e$ is working on job $j$ at time $t$ or that $e$ begins job $j$ at time $t?$ If the former, your constraint is incorrect, because it blocks $j$ from starting a new job until $\delta_e$ time units after the current time rather than after the time $e$ started $j.$ Also, the summation on the right would need to exclude $i=j.$
– prubin
Jan 13, 2023 at 16:43
• Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking.
– Community Bot
Jan 13, 2023 at 16:46

Works better is an empirical question. Only experimentation will tell.

First, note that your "big M" may in fact not be all that big. $$M=\vert J \vert-1$$ is sufficiently large to do the job.

That said, one way to avoid $$M$$ involves adding new variables $$Y_{ejt}\ge 0$$ and more constraints. It makes the model larger (generally not desirable) but may or may not make the bounds tighter. The additional constraints are $$Y_{ejt} \ge \sum_{\tau=t-\delta_j + 1}^t X_{ej\tau}\quad \forall e,j,t$$ (with suitable adjustments to the lower limit of summation to skip negative times) and $$\sum_{j\in J}Y_{ejt} \le 1\quad \forall e,t.$$ The first new constraint forces $$Y_{ejt} \ge 1$$ if $$e$$ starts $$j$$ before time $$t$$ but close enough that $$j$$ would still be in progress at time $$t.$$ In other words, you will get $$Y_{ejt}=1$$ if $$e$$ is doing $$j$$ at $$t.$$ The second constraint says that any employee at any time can be doing at most one job.

Choose M as an upper bound, $$U$$ of number jobs an employee $$e$$ can be assigned over time horizon $$T$$, then
$$\sum_{j \in \{J-j\}}\sum_{t\le t^* \le t+\delta_j}x_{e,j,t^*} \le U(1-x_{e,j,t}) \ \ \forall e \in E \ \ \forall j \in J$$

If you want to avoid use of U or M then

$$\sum_j x_{e,j,t} \le 1 \ \ \forall t \ \ \forall e$$ (1)

$$\delta_j x_{e,j,t} \le \sum_{\tau = t}^{t+\delta_j-1}(x_{e,j,\tau}) + C \le \delta_j \ \ \forall C \in \{0,1,...\delta_j-1 \} \ \ \forall t \ \ \forall e \ \ \forall j$$ (2)

OR: Alternate to cons (2)

$$\delta_jx_{e,j,t-1} - \sum_{k=1}^{t-1} x_{e,j,k} \le \delta_j x_{e,j,t}$$ (3)

$$\sum_{k=1}^{t-1}x_{e,j,k} - \delta_jx_{e,j,t-1} \le \delta_j (1-x_{e,j,t})$$ (4)

$$\forall t \in \{2,...T\} \ \ \forall j \ \ \forall e$$

• I think your last constraint is incorrect.
– prubin
Jan 13, 2023 at 18:23
• yes realized its like a moving thing, t,t+1,t+2.. so added that $\delta_t$ Jan 13, 2023 at 18:27
• I still don't understand your last constraint. Suppose that $x_{ejt}=1.$ Then for every $\delta_t$ in the correct range, you have $\delta_j \le 1 + \delta_t \le \delta_j ,$ which means $1 + \delta_t = \delta_j$ for a variety of values of $\delta_t,$ which can't be true.
– prubin
Jan 13, 2023 at 21:56
• I get $\delta_t$ with $t$ as index was creating confusion. Its like when $x_ejt =1$ for a time $t$ then all $x$s through $t+\delta_j$ are forced to be 1, summing upto $\delta_j$. So to avoid the model to continue to make time slots beyond duration as time $t$ loops on the lhs, $C$ acts as a counter. Jan 13, 2023 at 22:37
• Suppose employ $e$ starts job $j,$ which has duration 2 time units $(\delta_j=2),$ at time $t$ $(x_{ejt}=1).$ Your revised last constraint seems to say $2\cdot 1 = x_{e,j,t}+x_{e,j,t+1}+x_{e,j,t+2}+C=2$ for $C\in \lbrace 0, 1 \rbrace.$ That cannot hold for both $C=0$ and $C=1.$ Also, the middle expression only looks at $x_{e,j,\cdot},$ indicators for when $e$ might start $j$. The constraint needs to prevent $e$ from starting other jobs $j^\prime \neq j$ while $e$ is working on $j.$
– prubin
Jan 14, 2023 at 4:10