Flowshop with parallel machines model

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 ii; \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 ii; \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!

• 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? – prubin Jan 24 at 18:31
• @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. – Sghat Jan 24 at 19:07