12
$\begingroup$

I'm currently developing a small capacity planning problem and right now I am struggling with the "activation" of a subset. Needless to say I am not an expert in this kind of things.

I have a set of $i\in I$ products. Each product $i$ can be produced by $p∈P_i$ processes. Each process $p$ requires a set of different machines $w∈W_p$. Decision variable $x_{tip}$ represents the quantity of product $i$ produced in period $t$ through process $p$. The quantity is subject to change in each period to satisfy the demand $D_{ti}$. However, the company must stick to the process selected in $t=1$ for the whole planning period $T$. This is indicated by the binary variable $u_{tip}$. I already formulated the relevant constraints to force this behavior:

$$x_{tip} \le u_{tip}\cdot M \quad \quad \forall t \in T,i\in I, p \in P_i$$ $$u_{tip} = u_{t+1ip} \quad \quad \forall t \in T,i\in I, p \in P_i$$

$$\sum_{p∈P_i} u_{tip} \le 1 \quad \quad \forall t \in T,i\in I$$ $$u_{tip} \in \{0,1\}\quad \quad \forall t \in T,i\in I, p \in P_i$$

So now I want to use $u_{tip}$ to activate all machines that are required for the selected process $p$. However, I am at my wit's end and just have no clue how to implement this behavior linearly.

Example: Assume we have a product $i=1$ that can be produced by processes $P_1\in\{1,3\}$. Disregarding the other products, process $1$ is selected for product $1$, so $u_{t11}=1$. Process $1$ requires machines $W_1 \in \{2,3\}$. Is there a way to use a new indicator variable, e.g. $y_{tiw}$, to "activate" all machines $w \in W_1$ for product $1$?

As I try to minimize my set-up costs, I need to know whether a machine $w$ is used by a product $i$ in period $t$. I tried it with $$u_{tip} \le y_{tiw} \quad \quad \forall t \in T, i \in I, p \in P_i, w \in W_i$$ but after toying around I don't think this works. Note that every process $p$ may have a different no. of required machines $w$.

As I said I am currently struggling to find a way to make this work linearly. I tried to find similar papers in the operations management literature but that wasn't successful either. I would gladly appreciate any help or hints/references on similar work. Thank you!

$\endgroup$
  • 2
    $\begingroup$ Hi @Paroth, welcome to OR.SE. Is the number of machines required for each process given? And are different processes share some machines? $\endgroup$ – Oguz Toragay Aug 13 '19 at 6:58
  • 1
    $\begingroup$ Hi @OguzToragay, thank you for your response. Yes, the number is given, so basically I assume that the company has total information about which process requires which machine. Yes, processes can share the same machine, too. $\endgroup$ – Paroth Aug 13 '19 at 7:23
  • 1
    $\begingroup$ Beside the answer another approach comes to my mind: you may find the index of the selected process for each $i$ and use the dataset that you have to put the summation of all $q_{pk}$ equal to $|p|$ which hasbeen selected in period $t$. $\endgroup$ – Oguz Toragay Aug 13 '19 at 9:28
  • $\begingroup$ If $u$ is required to be the same across $t$, why not omit that index and just use $u_{ip}$ everywhere instead? $\endgroup$ – Rob Pratt Aug 13 '19 at 15:44
  • $\begingroup$ I am building a base model which i want to extend later on, where the company can change the process throghout the planning period. So you are right, it isn't necessary in this specific model, but I will need it later on. $\endgroup$ – Paroth Aug 13 '19 at 16:44
7
$\begingroup$

$I$: Number of products

$|P_i|$: Number of available processes for product $i$

$|p|$: Number of machines in each process $p$

You can define two new binary variables for each $k$ machine as follow:

$s_{tipk} = \left\{\begin{array}{l}1 & \text{if machine $k$ in time $t$ under process $p$ is working on product $i$}\\0 & \text{otherwise}\end{array}\right.$

$q_{pk} = \left\{\begin{array}{l}1 & \text{if machine $k$ is among the ones that are being used in process $p$}\\0 & \text{otherwise}\end{array}\right.$

Now you need to add the following constraints to the model:

  1. $\sum_{i\in I} s_{tipk} =1 \ \ \ \forall \ t,k$ (each machine can produce only one type of product at each time period)

  2. $\sum_{k} q_{pk} =|p|*u_{tip} \ \ \ \forall \ \ i,t$

  3. $s_{tipk} \leq q_{pk} \ \ \ \forall \ \ t,k,i,p$

I believe this answer will give you at least some hints on how to model the problem (if it hasn't already covered all the necessary details).

$\endgroup$
  • $\begingroup$ Your suggestion looks really promising and helps me alot! So if we assume that a machine $w$ can produce more than one product $i$ in period $t$, i might think that the proposed solution can be shortened. A possible solution to my problem (with binary variable $y_{tipw}$ indicating whether machine $w$ is activated through process $p$) can be formulated as follows: $$\sum_{w \in W_p} y_{tipw} = |p| \cdot u_{tip} \qquad\forall t\in T, i \in I, p \in P_i$$ Is this a viable formulation or am I missing something? $\endgroup$ – Paroth Aug 13 '19 at 12:08

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.