# Mixed-Integer Linear Programming (Capacity Planning)

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!

• Hi @Paroth, welcome to OR.SE. Is the number of machines required for each process given? And are different processes share some machines? – Oguz Toragay Aug 13 '19 at 6:58
• 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. – Paroth Aug 13 '19 at 7:23
• 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$. – Oguz Toragay Aug 13 '19 at 9:28
• If $u$ is required to be the same across $t$, why not omit that index and just use $u_{ip}$ everywhere instead? – RobPratt Aug 13 '19 at 15:44
• 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. – Paroth Aug 13 '19 at 16:44

$$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).

• 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? – Paroth Aug 13 '19 at 12:08