This looks a bit like the knapsack problem where the total length of the bundle (in the examples, 89cm) is the limit of the knapsack. The lengths in the sausage problem are equivalent to the weights of items in the knapsack problem. Wikipedia has some information on this. It’s an old problem and should also appear in many text books on “combinatorial optimization” or on “operations research” (or “operational research”).
There was a previous study group problem (I believe) to do with packing meat portions to get to a given weight. This seems like a similar problem. I wasn’t involved with it but I think that they came up with a strategy. I was not able to find anything with a quick search on MIIS
Would the machine be given the casings one at a time in some arbitrary order as they became ready for bundling up? Also, am I correct in understanding that the length of the casing completely determines if it is part of a small bundle, a medium bundle or a large bundle? If so, these can be considered as three parallel processes.
The general strategy (if my memory serves me well) might be to try to put large items (above average length) into the bundle first. This is more difficult if they are arriving sequentially. You have to have a strategy for when to put something into an existing, partially filled bundle and when to start a new bundle.
Rebecca
----------------------------------------
Dr Rebecca Gower,
Research Liaison Officer (Mathematics and Statistics)
Mathematical Institute
24 - 29 St Giles,
Oxford, OX1 3LB
加好友 
发短信
Post By：2010/12/10 20:08:03 [只看该作者]
