Production Planning

This is one of those problems where we eliminate a lot of the parameters and are still left with a version that in NP-Complete.  I guess I would have started with the stripped-down version first, since adding extra parameters keeps the problem NP-Complete.

The problem: Production Planning.  This is problem SS21 in the appendix.

The description: Given a positive number n of time periods, and for each period i, several non-negative parameters: demand (ri), production capacity (ci), setup cost (bi), incremental production cost coefficient (pi), and inventory cost coefficient (hi).  We’re also given an overall bound B.  Can we find a positive production amount (xi)  for each period such that:

  • xi ≤ ci for all i (we never produce more than the production capacity)
  •  The inventory on hand for each period (Ii =\sum_{j=1}^i(xj -rj)  is non-negative
  • \sum_{i=1}^n(pixi+hiIi) + \sum_{x_{i}>0}bi ≤ B?

Example: There are a lot of variables here, but here’s what it’s really saying:

Suppose we have a factory that makes some product, and the factory’s schedule for making the product is split into time periods.  In each time period, we can only make a certain amount (ci) of the product, and it costs a certain amount to use the factory at all during a time period (bi) and then an additional amount to make each instance of the product (pi).   Each time period also has a demand (ri) that has to be met.  We can get ahead of the demand by producing more than we need (leaving Ii extra around at time i), but also at a cost (hi).

Suppose I have 3 time periods:

Time Period Production Capacity Demand Production Cost Inventory Cost Production Setup
1 5 3 2 1 6
2 5 3 4 3 2
3 1 2 20 20 5

Since at time period 3, we have less production capacity than demand, we will have to carry over inventory from a previous time period.  There are basically four strategies to meet the demands:

  1. Produce 4 units at time period 1, 3 at time 2, and 1 at time 3.  At time 1, this costs 6 to set up production, 4×2 to make the goods, and 1×1 to store the extra good (So 15).  At time period 2, it costs 2+3×4+1×3 = 17, and time period 3, it costs 5+1×20+0x20 = 25, for 57 total cost.
  2. Produce 3 units at time period 1, 4 at time 2, and 1 at time 3.  At time 1, this costs 6+3×2+0x1 = 12.  At time period 2, it costs 2+4×4+1×3 = 21. At time period 3, it costs 5+1×20+0x20  25.  This is a total cost of 58.
  3. Produce 5 units at time period 1, 3 at time period 2, and 0 at time period 3.  This would cost 6+5×2+2×1 = 18 at time 1, 2+3×4+2×3 =20, and 0 at time 3, for a cost of 38.
  4. Produce 3 units at time period 1, 5 at time period 2, and 0 at time period 3.  This would cost 6+3×2+0x1 =12 at time 1, 2+5×4+2×3 = 28 at time 2, and 0 at time 3, for a total time of 40.

So option 3 is the best choice.  But if we raised the inventory cost of time period 1 significantly (say, to 50), then option 3 would cost 114, and option 4 would still cost 40, and be best.

Reduction: The paper by Florian, Lenstra, and Rinnooy Kan say they use Knapsack, but by our definitions, the problem is really Sum of Subsets.    So we’re given a set of integers A= {a1 .. an} and a target B.    We will build a production planning instance with n+1 time periods numbered from 1 to n.  The demand of each period is B.  The b costs (to set up production) are 1 at all periods.   The capacity at time period 0 is n*B, and the capacity at time period i > 0 is ai.  The production cost at time period 0 is 0, the production cost at time period i is \frac{a_i -1}{a_i}.  All inventory costs are 0.   The cost bound B’ is equal to the SOS bound B + 1.

Since it costs 1 to make any amount of goods (up to our capacity limit) in time 0, we might as well make all of it that we can.  This gives us n*B goods, and will be enough to supply the demands at all of the other time periods except for the last, leaving B left over to be supplied in the last time period.  Notice that our production cost fraction is built in such a way that if in time period i, we make ai goods, we pay exactly ai cost.  If we build less than ai goods in time period i (but more than 0), we pay more than ai cost in that time period.  So the only to get a total cost of B’ while meeting the demand is to make exactly ai of the good in each time period that makes goods.  This corresponds to a subset of A that sums to exactly B.

Difficulty: 5.  If you do use this in a class, I’d give them a simpler version where you don’t even mention the inventory costs, and where the b cost is always 1, and where the demands are always equal in each time period, since that’s what the reduction does.

Leave a Reply

Your email address will not be published. Required fields are marked *