Alternative way to restrict an employee to work on multiple jobs

Question

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.

Answer 1

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.

Answer 2

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 $