0
$\begingroup$

I am working on an integer programming model for a flowshop problem with different number of parallel machines.

I have to schedule $i=1,..,n$ jobs in $j=1,..,m$ activities where each $j$ activity has a $M_{j}$ number of parallel machines.

Jobs have to go through each activity, but not through each machine.

Objective is to maximize the weights ($wi$) attributed to one of the activities ($h^*$) in a predefined time window $F$:

$$ Max \quad \sum\limits_{i=1}^{n} w_i.pp_{ih^*}$$ where $pp_{ih^*}$ is the process time within the given time window.

Positive integer variables:

  • $xij$ is the variable for the start period of job $i$ in activity $j$.
  • $xijh$ is the variable for the start period of job $i$ in activity $j$ machine $h$. It is $0$ in case job $i$ is not processed by the machine.

Binary variables:

  • $yijh$ is 1 if job $i$ is processed by machine $h$ in activity $j$. $0$ otherwise.
  • $wikjh$ is 1 if job $i$ is processed before job $k$ by machine $h$ in activity $j$. $0$ otherwise.

Constants:

  • $pij$ is the duration of job $i$ in activity $j$.
  • $M$ is a constant (a big number).

Constraints:

To define $pp_{ih^*}$: $$pp_{ij} \leq F - x_{ij} \qquad \forall i;\quad j=h^*$$ (1) $$pp_{ij} \leq p_{ij} \qquad \forall i;\quad j=h^*$$ (2)

Each job has to be processed in each machine: $$\sum\limits_{h=1}^{M_{j}} y_{ij_{h}}=1 \qquad \forall i; \quad \forall j$$ (3)

Each job has to be processed in machine $j$ before $j+1$: $$ x_{ij}+p_{ij}\leq x_{i(j+1)} \qquad \forall i; \quad \forall j\leq (m-1)$$ (4)

Same $j_{h}$ machine can not process 2 jobs at same time: $$\sum\limits_{h=1}^{M_{j}} x_{ij_{h}}+p_{ij} \leq \sum\limits_{h=1}^{M_{j}}x_{kj_{h}}+M(1-\sum\limits_{h=1}^{M_{j}}w_{ikj_{h}}) \quad \forall i<n;\quad \forall k>i; \quad \forall j; \quad \forall h\leq M_{j}$$ (5)

$$\sum\limits_{h=1}^{M_{j}}x_{kj_{h}}+p_{kj} \leq \sum\limits_{h=1}^{M_{j}}x_{ij_{h}}+M.\sum\limits_{h=1}^{M_{j}}w_{ikj_{h}} \qquad \forall i<n;\quad \forall k>i; \quad \forall j; \quad \forall h\leq M_{j}$$ (6)

$x_{ij}$ definition: $$x_{ij} = \sum\limits_{h=1}^{M_{j}} x_{ij_{h}}$$ (7) $$x_{ijh}\leq M.y_{ijh}$$ (8)

I would like some help with constraints 4, 5 and 6 since they appear to conflict with each other. Thanks for any help!

$\endgroup$
  • $\begingroup$ I think there are some LaTeX errors, but I am unsure what the correct expressions would be. Is there actually a subscripted version of subscript $j$ (i.e., $j_h$), and if so what does it mean? What is $F$ in constraint (1)? Should $yijh$ be $y_{ijh}$ or $y_{ij_h}$? Also, having $x$ with two subscripts and $x$ with three subscripts is a bit confusing. Perhaps you could change one of them to a different symbol? $\endgroup$ – prubin Jan 24 at 18:31
  • $\begingroup$ @prubin $h$ is a subscript of $j$. Is one of the parallel machines that can execute activity $j$ of the cycle. $F$ is a given constant. Beyond $F$ is not necessary to optimize. Correct is $y_{ij_{h}} $. I agree with the change is the x variable with 3 subscritps to make it clear that is not the same as the x with 2 subscript. I kept trying to figure out and the problem in constraint 4 is when $p_{ij} $ is $0$. Thanks for answering. $\endgroup$ – Sghat Jan 24 at 19:07

Your Answer

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

Browse other questions tagged or ask your own question.