Resource constraint with MIP model

Question

My question is how to model a resource constraint with MIP model (how should I modify it?)

A factory is making blocks. If there is space left at that time, the block can be assembled. (If the factory has space, it can do multiple tasks at the same time.)

I'm asking this question because I don't know how to formulate it even though I've been thinking about it after getting feedback in the comments from prubin to my previous question: Space constraint in scheduling problem.

Here are my notations:

Index

• $i,j$ is the block number

• $f$ is factory number

• $t$ is time

Parameters

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

• $sp_i$ is required area for each block

• $c_f$ is available space of factory f

• $P_i$ is procees time of each block

• $M$ is a big number

Variables

• $S_i$, $C_i$ the start time, completion 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}$

• $s_{i,f,t}=\begin{cases}1\quad\text{if}\,i\,\text{start at factory }\,f\text{ at time t }\quad\\0\quad\text{otherwise}\end{cases}$

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

Constraints

$$ \sum_{f=1}\sum_{t=1} (y_{i,f} \cdot s_{i,f,t}) =1\quad\forall i \quad (1)$$

$$ \sum_{f=1}\sum_{t=1}(t \cdot s_{i,f,t}) = S_i \quad \forall i \quad (2)$$

$$ S_i+p_i = C_{i}\quad\quad \forall i \quad (3)$$

$$ S_i-M(1-y_{i,j,f}) \le S_{j} \quad\quad \forall i,j,f \quad (4)$$

I think this part is the problem because $t$ depends on variables $S_i$,$C_i$

I'm not sure why Problems running when running with gurobi. $$ \sum_{t=S_i}^{C_i} s2_{i,f,t} = p_{i}\quad\forall f\quad (5)$$

$$ \sum_{i} sp_i \cdot s2_{i,f,t} \le c_{f}\quad\forall f,t\quad (6)$$

thanks for your reading

Answer 1

I think this inequality is a problem:

$$ \sum_{t=S_i}^{C_i} s2_{i,f,t} = p_{i}\quad\forall f\quad .$$

The index of your summation cannot depend on variables. You should therefore delete it. Then you can do the following to repair your model:

Add a variable to end the job: $c_{i,f,t}=\begin{cases}1\quad\text{if}\,i\,\text{start at factory }\,f\text{ at time t }\quad\\0\quad\text{otherwise}\end{cases}$

add these inequality

$$ \sum_{t}t \cdot c_{i,f,t} = C_i \quad \forall i,f \tag7$$

and

$$ s2_{i,f,t} \ge s_{i,f,t} \forall i,f,t \tag8$$

As the s2 variables are used to indicate, that the job i is taken processed at time t at machine f, and s indicated the start of the job, we know that when the job starts, it also needs to take place.

$$ s2_{i,f,t} \ge s2_{i,f,t-1} - c_{i,f,t-1} \forall i,f,t \tag9$$

This inequality tell us, that if we were processing job i at f during time t-1 we also process it at time t, unless time t-1 was also the completion time.

This model is not nice, but i think it works and is a starting point. You might want to look into machine scheduling and resource constraint project scheduling literature for better ideas.