patternMinor
Inventory planning problem solved through dynamic programming
Viewed 0 times
problemplanninginventoryprogrammingdynamicthroughsolved
Problem
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 o
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 o
Solution
CLRS give plenty of implementations in their chapter on dynamic programming, e.g. in the section on Rod cutting
I suggest you try to adapt one of these.
- recursive top-down (p363),
- memoized (p365f) and
- bottom-up (p366).
I suggest you try to adapt one of these.
Context
StackExchange Computer Science Q#6379, answer score: 4
Revisions (0)
No revisions yet.