# Modeling IP Problem

Hallco runs a day shift and a night shift. No matter how many units are produced, the only production cost during a shift is a setup cost. It costs \$8,000 to run the day shift and \$4,500 to run the night shift. Demand for the next two days is as follows: day 1, 2,000; night 1, 3,000; day 2, 2,000; night 2, 3,000. It costs $1 per unit to hold a unit in inventory for a shift. Determine a production schedule that minimizes the sum of setup and inventory costs. All demand must be met on time. I am confused on how to model these sentences. It costs$1 per unit to hold a unit in inventory for a shift. What does it mean in mathematical language?

• Just consider day $1$ and night $1$. You have a choice, including (a) running both times, at a cost of $\$8000 + \$4500$; and (b) running in the day and keeping $3000$ items for the night but not running at night, at a cost of $\$8000 + \$3000$ where the $\$3000$represents the costs of holding$3000\$ items for one shift. Obviously (b) is a better choice than (a) here – Henry May 22 at 0:42

## 1 Answer

Let $$x_i = \begin{cases} 1,& \text{ if shift i is run}\\0,& \text{ otherwise}\end{cases}$$ and $$y_{ij}=\begin{cases}1,&\text{ if demand during shift j is met using production from shift i}\\0,&\text{ otherwise}\end{cases}$$ for $$i\leqslant j$$. (Here shift $$1$$ corresponds to the day shift on day $$1$$, shift $$2$$ the night shift on day $$1$$, and so on.) We can model this problem by

\begin{align} \min &\quad 8000x_1 + 4500x_2 + 8000x_3 + 4500x_4 + 3000y_{12}+4000y_{13}+9000y_{14}\\ &\ +2000y_{23}+6000y_{24}+3000y_{34}\\\\ \mathrm{s.t.} &\quad \sum_{i\leqslant j} y_{ij} = 1,\quad 1\leqslant j\leqslant 4\\ &\quad y_{ij} \leqslant x_i,\quad 1\leqslant i\leqslant j\leqslant 4\\ &\quad x_i\in\{0,1\},\quad 1\leqslant i\leqslant 4\\ &\quad y_{ij}\in\{0,1\},\quad 1\leqslant i\leqslant j\leqslant 4. \end{align} The coefficients on the $$x_i$$ in the objective function correspond to the cost of running a shift, and the coefficients on the $$y_{ij}$$ to the cost of holding units in inventory for one or more shifts. The first set of constraints ensures that each demand is met by production during that shift or an earlier shift. The second set of constraints ensures that a demand cannot be met by production during a shift unless that shift is run.