I'm studying an MIP model with a scheduling problem and I'm wondering if the space constraint is correct.

If there is space in the factory at that time, the block can be processed, where

  • $i$ is the block number

  • $S_i$, $C_i$ and $P_i$ are the strat time, completion time and processing time of block $i$ respectively

  • $y_{i,j,f}=\begin{cases}1\quad\text{if}\,i\,\text{process before}\,j\,\text{at factory}\,f\\0\quad\text{otherwise}\end{cases}$

  • $y_{i,f}=\begin{cases}1\quad\text{if}\,i\,\text{process at factory}\,f\\0\quad\text{otherwise}\end{cases}$

  • $M$ is a big number

  • $sp_i$ is the required space of block $i$

  • $c_{f,t}$ is the available space of factory $f$ at time $t$

\begin{align}S_i -M(1-y_{i,j,f}) &\le S_j\quad\forall i,j,f\\S_i + P_i &= C_i\quad \forall i\end{align}

The space constraint is $$sp_i \cdot y_{i,f} \le c_{f,t}\quad\forall i,j\quad\text{and}\quad t=S_i,\cdots,C_i.$$

  • 1
    $\begingroup$ Welcome to OR.SE. Would you say please, what exactly do you mean by "space constrain"? What the scheduling problem you have faced and are going to solve using MIP? It sounds like a material handling problem instead of the detailed schedule problem. $\endgroup$
    – A.Omidi
    Jun 1, 2020 at 12:08
  • $\begingroup$ Space constraint refers to the space where blocks can be operated. The block assembly plant is dealing with a problem. $\endgroup$
    – boroboro
    Jun 2, 2020 at 1:07
  • 1
    $\begingroup$ Thanks. Would you see some layout optimization model? I hope this link would be useful. $\endgroup$
    – A.Omidi
    Jun 2, 2020 at 5:08

1 Answer 1


No, your space constraint is incorrect. There are multiple problems, including the fact that the range of the index $t$ depends on variables $S_i$ and $C_i$. Note that your current space constraint would not stop two jobs from using the same capacity simultaneously. (Your precedence constraint forces one job to start before another, but does not force the second job to wait until the first job has completed.) Also, your precedence constraint should be $\le$, not $\lt$.

  • $\begingroup$ Thanks for you, $\endgroup$
    – boroboro
    Jun 2, 2020 at 1:04
  • $\begingroup$ May I ask one more question? Can index t be modeled without dependence on S and C? $\endgroup$
    – boroboro
    Jun 2, 2020 at 1:06
  • $\begingroup$ Assuming $c_{f,t}$ is a parameter, what you can do is create one constraint for each $t$ in the planning horizon. That constraint sums up the space utilization of all blocks $i$ such that $y_{i,f}=1$ and $S_i \le t \le C_i$, and forces the total not to exceed $c_{f,t}$. The left side can be linearized, although it's a bit complicated. Similar questions about linearizing conditional expressions have been asked and answered on this site. $\endgroup$
    – prubin
    Jun 2, 2020 at 15:20
  • $\begingroup$ Thank you. Thank you very much $\endgroup$
    – boroboro
    Jun 3, 2020 at 1:20
  • $\begingroup$ I've been thinking about it for a few days, but I have no idea. If you don't mind, could you express it in a formula? $\endgroup$
    – boroboro
    Jun 8, 2020 at 11:45

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.