4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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.$ $\endgroup$
    – prubin
    Jan 13 at 16:43
  • 1
    $\begingroup$ 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. $\endgroup$
    – Community Bot
    Jan 13 at 16:46

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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 $

$\endgroup$
8
  • $\begingroup$ I think your last constraint is incorrect. $\endgroup$
    – prubin
    Jan 13 at 18:23
  • $\begingroup$ yes realized its like a moving thing, t,t+1,t+2.. so added that $ \delta_t$ $\endgroup$ Jan 13 at 18:27
  • $\begingroup$ 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. $\endgroup$
    – prubin
    Jan 13 at 21:56
  • $\begingroup$ 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. $\endgroup$ Jan 13 at 22:37
  • $\begingroup$ 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.$ $\endgroup$
    – prubin
    Jan 14 at 4:10

Your Answer

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

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