3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think your problem is at its core machine scheduling or a resource constraint project scheduling problem. Can you maybe try to explain in more detail what your problem is? I understand it like this: There are jobs J (you call them blocks?) with a space requirement and processing time, Factories F that have an amount of available space, each factory can process one job at a time that fits in the space requirement. Our objective is to minimize the makespan. Is that correct, are there more rules? $\endgroup$ – Luke599999 Jun 15 at 7:17
  • $\begingroup$ Yes, There are jobs that called block Multiple blocks can be processed simultaneously if there is space in the factory. I made other constraints. Space constraints could not be resolved. $\endgroup$ – boroboro Jun 15 at 7:28
  • $\begingroup$ @boroboro, welcome to OR.SE. Would you have any force to use you mentioned MIP model? $\endgroup$ – A.Omidi Jun 15 at 12:27
  • $\begingroup$ @A.Omidi Are you asking if I can use Gurobi? (I'm not good at English, so I'm asking again.) $\endgroup$ – boroboro Jun 16 at 6:13
  • 1
    $\begingroup$ @boroboro, I mean you could try using an alternative formulation instead of you mentioned. But for now, you accept the answer and I suppose you are in the right way. :) $\endgroup$ – A.Omidi Jun 16 at 13:54
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks for your answering , i dont understand this part. could you explain me ? $$ s2_{i,f,t} = s_{i,f,t} \forall i,f,t $$ $$ s2_{i,f,t} \ge s2_{i,f,t-1} - c_{i,f,t-1} \forall i,f,t$$ $\endgroup$ – boroboro Jun 15 at 13:15
  • $\begingroup$ I corrected an error and added an explanation $\endgroup$ – Luke599999 Jun 15 at 19:04
  • $\begingroup$ I'm sorry to keep asking you questions. and i forgot to mention the work initiated cannot be stopped. so i had added constraint (5) i think constraint if i use constraint (8) (9) the work could be stopped. $\endgroup$ – boroboro Jun 16 at 2:15
  • 1
    $\begingroup$ I undersand !! :) I'll organize what you said and revise the text, so could you take a look at the whole thing? $\endgroup$ – boroboro Jun 16 at 6:36
  • 1
    $\begingroup$ I think, it is not in the spirit of the site to change the question after it has been answered. I think it would be better, to ask a new question with the new model. Or to post the complete model as an answer to your own question. $\endgroup$ – Luke599999 Jun 16 at 7:05

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.