3
$\begingroup$

I am working on problem (15-11) Inventory planning from Introduction to Algorithms (CLRS, 3rd Ed).

15-11: Inventory Planning, p.411

The Rinky Dink Company makes machines that resurface ice rinks. The demand for such products varies from month to month, and so the company needs to develop a strategy to plan its manufacturing given the fluctuating, but predictable, demand. The company wishes to design a plan for the next $n$ months. For each month $i$, the company knows the demand $d_i$, that is, the number of machines that it will sell. Let $D = \displaystyle\sum_{i=1}^{n} d_i $ be the total demand over the next $n$ months. The company keeps a full-time staff who provide labor to manufacture up to m machines in a given month, it can hire additional, part-time labor, at a cost that works out to c dollars per machine. Furthermore, if, at the end of a month, the company is holding any unsold machines, it must pay inventory costs. The cost for holding j machines is given as a function $h(j)$ for $u = 1, 2, ... , D$, where $h(j) \ge 0$ for $1 \le j \le D$ and $h(j) \le h(j+1)$ for $j \le 1 \le D - 1$.
Give an algorithm that calculates a plan for the company that minimizes its costs while fulfilling all the demand. The running time should be polynomical in $n$ and $D$.

In other words, problem asks to create dynamic programming algorithm that solves this problem.

So far, I came up the the following solution, and not sure if it is any good.
Optimal sub-problem: Let $MinCost(i,j)$ be the function that returns minimized cost of operation for past $i$ months, $j$ is the number of unsold machines left at the end of the month $i$.(Goal, is to calculate $MinCost(n,0)$, in other words, at the end of planning period(month $n$), there are no unsold machines.)

So, the DP recurrence is given by $MinCost(0,0) = 0$ and

$\quad MinCost(i,j) = \min\{MinCost(i-1,j-k) + c(k,j,i) + h(j) \mid 1 \le k \le D \}$

for $i+j > 0$; here, $c(k,j,i)$ is the function that calculates the costs of the production.

If my optimal sub-problem is correct, how do I create an algorithm to solve it?

$\endgroup$

3 Answers 3

4
$\begingroup$

CLRS give plenty of implementations in their chapter on dynamic programming, e.g. in the section on Rod cutting

  • recursive top-down (p363),
  • memoized (p365f) and
  • bottom-up (p366).

I suggest you try to adapt one of these.

$\endgroup$
0
$\begingroup$

The overal idea of the sub-problem sounds good.

I've noticed a few issues:

What is k supposed to represent?

$j$ represents the number of machines unsold at the end of month $i$. This can't be negative as you cannot have a negative number of machines unsold, which means you sold more than what you produced!

You said you start with $MinCost(n,0)$ so you start with $j=0$, but then you need to compute $MinCost(n-1,0-k)$ and you wrote that $1 \leq k$, which leaves to negative $j$!. There seem to be an issue here.

I think your idea was that $k$ was the net difference of machines unsold on day $i$, which makes it hard to reason about.

So let's define $k$ as the number of unsold machines at the beginning of month $i$ (= number of unsold at the end of month $i-1$).

What is $c(k,j,i)$?

You should have enough data to compute the costs yourself. By the new definition of $k$, $c(k,j,i)= c \cdot (j-k + d_i - m)$. This is because you had $k$ machine at the beginning of month $i$, you have $j$ machines at the end of that month and you sold $d_i$ machines, so you produced $j-k + d_i$ machines that month. You can produce $m$ machines without any additional cost so the remaining number of machine costs $c$ dollars per machine.

Please note that this value cannot be negative, as you can't get back the costs if you have to build less than $m$ machines. So $c(k,j,i)= max(0, c \cdot (j-k + d_i - m))$.

This brings us to

$\quad MC(i,j) = \min\{MC(i-1,k) + max(0, c \cdot (j-k + d_i - m)) + h(j) \mid 0 \le k \le D \}$

With $MC(0, j) = \begin{cases} 0 & \quad \text{if } i = 0\\ + \infty & \quad \text{if } i \neq 0 \end{cases}$

Because you can't have machines in stock before the first day.

We could make some optimisation on the max value of $k$ but it's a bit hard to compute and won't improve the asymptotic complexity.

I believe this should be enough to write the algorithm.

$\endgroup$
0
$\begingroup$

I was visiting the dynamic programming questions in the CLRS the other day, and I saw this problem. I think this can be solved in $O(nD)$.

Let $C(i,j)$ be the minimum cost of producing a total of $1 \leq j \leq D$ machines at the end of $1 \leq i \leq n$ months. Since the production must meet the demand, if we have $j < \sum_{k=1}^i d_k$ at month $i$ (i.e., we couldn't meet the demand), we set $C(i,j) = \infty$ since this is not a valid solution. Otherwise, at month $i$ to produce $j$ machines, where $j \geq \sum_{k=1}^i d_k$, we have the choice of producing $l \leq j$ machines in $i-1$ months and $j-l$ machines this month. The optimal cost of the former is given by $C(i-1,l)$ and the cost of the latter is $c \cdot (j-l-m)$. Since this value cannot be negative, we can rewrite it as $c \cdot max(0, (j-l-m))$, which makes the cost $0$ if it is negative. We also need to store the extra produced machines that are over the demand in an inventory, whose cost is $h(j-\sum_{k=1}^i d_k)$. This must be added to the cost above. Let $C$ be an $(n+1) \times D$ matrix. We also compute the cumulative summation of demands in an array $A$ to help checking whether we meet the demand in a particular month. Then the recursive formulation becomes:

\begin{equation} C(i,j) = \begin{cases} 0, & \text{if } i=0 \\ \infty, & \text{if } j < A[i] \\ min_{1\leq k \leq j} (C(i-1,k) + (c \cdot max((j-k-m),0)) + h(j-A[i])), & \text{otherwise} \end{cases} \end{equation}

The above formulation looks like $O(nD^2)$. But assume we computed $C(i,j)$ and this cell chose some $k$ in row $i-1$ as minimum. While computing $C(i,j+1)$ the minimum cell in the above row for it must either be again $k$ (i.e., $C(i-1,k)$) or $C(i-1,j+1)$. The former is because $h(j) \leq h(j+1)$ and we would choose the same minimum in the above row when computing for $j+1$ if we did not consider $C(i-1,j+1)$. By keeping a running minimum for row $i-1$, thus the runtime can be reduced to $O(nD)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.