15-11 Inventory planning

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 = \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 per month. If the company needs to make more than \(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 \(j = 1, 2, \ldots, D\), where \(h(j) \ge 0\) for \(1 \le j \le D\) and \(h(j) \le h(j + 1)\) for \(1 \le j \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 polyomial in \(n\) and \(D\).

Our subproblems will be indexed by and integer \(i \in [n]\) and another integer \(j \in [D]\). \(i\) will indicate how many months have passed, that is, we will restrict ourselves to only caring about \((d_i, \dots, d_n)\). \(j\) will indicate how many machines we have in stock initially. Then, the recurrence we will use will try producing all possible numbers of machines from \(1\) to \([D]\). Since the index space has size \(O(nD)\) and we are only running through and taking the minimum cost from \(D\) many options when computing a particular subproblem, the total runtime will be \(O(nD^2)\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用