Despite the warning from the StackExchange Question engine that this question appears subjective, I'm going to ask it anyway.
We have a script as part of an application at work which is responsible for sorting items into bins. (Sounds simple, right?)
There are X items and Y bins. Each Item has a Primary, Secondary and Tertiary preferential bin. It also has an overall rating which corresponds to the item's overall quality, as well as the bin preference (rating is adjusted by -0.5, -1 for decreasing bin preference).
All item's ratings are probably different, and this affects the rating of each bin, and also an overall rating of all bins.
The ordering of items and their preferences into according bins is also important, i.e. Bin A containing Item1 and Item2, may have a different rating overall to Bin B containing Item1 and Item2.
Rules:
- Each bin can contain between 1 and 3 items.
- Any one item can only appear once in each bin, and can only appear in one bin.
Initially, we thought it was a knapsack problem, or possibly a multiple knapsack problem, but after researching each, we're not sure that any of the common algorithms for that problem fits our task.
We currently brute force it, but given that the Item pool contains 50 items, and the number of Bins is about 10, the runtime for a single bruteforce run is in the order of tens of seconds. We'd like to get this down to 0.5s
So basically, has anyone come across this problem before, and does it have a name (that we can search academic papers with)?