Better constraint formulation involving binary variables?

51 Views Asked by At

I have a binary variable $z_{jmt}$ that is $1$ iff job $j$ is assigned to machine $m$ at time $t$.

The constraint: Job $j$ can only be assigned to one and only one machine.

What I have done so far is:

$$z_{jmt}+z_{jm't'}\leq1,$$ for all $j$, for all $m'\ne m$, for all $t$ and for all $t'$.

I think this formulation is correct but it is "bad" because it involves many constraints: $\mathcal{O}(JM^2T^2)$ constraints where $J$ is the number of jobs, $M$ is the number of machines and $T$ is the number of time intervals.

Can we do a better formulation ?

1

There are 1 best solutions below

3
On BEST ANSWER

One machine ever: $$\sum_{m\in M}\sum_{t\in T} z_{jmt} \le 1 \quad \text{for all $j\in J$}$$

One machine at a time: $$\sum_{m\in M} z_{jmt} \le 1 \quad \text{for all $j\in J$ and $t\in T$}$$

Edit: Based on your clarification in the comments, introduce a binary decision variable $y_{jm}$ that indicates whether job $j$ is ever assigned to machine $m$. Then include (in addition to the "one machine at a time" constraints) the following constraints: \begin{align} z_{jmt} &\le y_{jm} &&\text{for all $j$, $m$, $t$} \\ \sum_m y_{jm} &\le 1 &&\text{for all $j$} \\ y_{jm} &\in \{0,1\} &&\text{for all $j$, $m$} \end{align}