I don't really know, what NP complete/hard means, but I think, supply autoplanning is a kind of that.
You have demand plan 90 days forwards for 100 product SKUs: beer! The 100 product SKU comes from:
- there're 10-15 kind of level-1 base raw brewed stuff, they're brewed in thousdnd litre big cans, and it takes a day;
- after brewing, some materials must be added (leaven?), and it must be rest for 10-15 day, then you got 15-20 kind of level-2 stuff;
- finally, when it's ready, some materials should be added, it's the level-3 stuff, called drinkable beer, there're cc. 30 kind of beers;
- the beer can be bottled as 3 dl, 5 dl, sometimes it gets special necklacigng (level 4), then it can be packed as 5x4 box, 6-pack (level 5).
There're machine "lines" for each operation: from brewing to packaging. The machines can perform more operations, say, some packing machines can make 6-pack and 3-pack, but others can do only 6-pack. There're constraints, e.g. speed, or the big brewing kettle is for brewing min. 6000, max, 8000 l of beer, (but if the beer type is light, then the min. is 5000 l and the max. is 7000 l). And so on, on every level.
The task: as I mentioned, there's a demand plan, for the 100 kind of level-5 (the bottled, packaged stuff). Make an optimal manufactoring plan for all the 5 levels, all machines. Minimize machine switches (e.g. bottling .5, .5, .5, .3, .3, .3 is better than .3, .5, .3, .5, .3, .5, there're less swithc, less dead time for bottling machines). Priorize by customer: some customers requires to ship the beer only with more than 50% of expiration time remains. Etc, etc.
Discover bottlenecks (eh), make alternate plans with adding non-existent machines to these points, then the best virtual scenario can be used to suggest to buy a new machines.
Is it hard enough, or should I tell ya how a textile factory works?
(Personal remark: the web, the bank and the logistics are challenging areas, but they're baby toys compared to manufactoring problems.)
Disclaimer: numbers are distorted for security reason, order of magnitude is real.