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 (r_{i}), production capacity (c_{i}), setup cost (b_{i}), incremental production cost coefficient (p_{i}), and inventory cost coefficient (h_{i}). We’re also given an overall bound B. Can we find a positive production amount (x_{i}) for each period such that:

- x
_{i}≤ c_{i}for all i (we never produce more than the production capacity) - The inventory on hand for each period (I
_{i }=(x_{j}-r_{j}) is non-negative - (p
_{i}x_{i}+h_{i}I_{i}) + b_{i}≤ 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 (c_{i}) of the product, and it costs a certain amount to use the factory at all during a time period (b_{i}) and then an additional amount to make each instance of the product (p_{i}). Each time period also has a demand (r_{i}) that has to be met. We can get ahead of the demand by producing more than we need (leaving I_{i} extra around at time i), but also at a cost (h_{i}).

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:

- 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.
- 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.
- 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.
- 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= {a_{1} .. a_{n}} 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 a_{i}. The production cost at time period 0 is 0, the production cost at time period i is . 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 a_{i} goods, we pay exactly a_{i} cost. If we build less than a_{i} goods in time period i (but more than 0), we pay more than a_{i} cost in that time period. So the only to get a total cost of B’ while meeting the demand is to make exactly a_{i} 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.