3
$\begingroup$

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.$$

$\endgroup$
  • 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 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 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 at 5:08
4
$\begingroup$

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$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for you, $\endgroup$ – boroboro Jun 2 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 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 at 15:20
  • $\begingroup$ Thank you. Thank you very much $\endgroup$ – boroboro Jun 3 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 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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