Approach to sql bin packing problem
I have a problem in sql where I need to create a packing list from a list of transactions.
Data model
Transactions are stored in a table containing:
- transaction id
- item id
- amount of elements
Each transaction can have multiple items (and coincidentally multiple rows with the same transaction ID). Each element then has a count from 1 to N.
Business problem
The business requires us to create a packing slip where each item on the packing slip contains the quantity of each item in the box.
Each box can only contain 160 items (they are all the same size / weight). Based on the total order bill, we need to split the items into different boxes (sometimes dividing even separate collections of items into two parts)
So the challenge is to accept this data schema and come up with a result set that includes how much of each item belongs in each field.
I am currently rudely forcing this not so pretty and wondering if anyone has a nifty / simple solution that I missed.
I / O example
We really need to isolate the quantity of each item in each field ... for example:
Order 1:
- 100 element A
- 100 element B
- 140 element C
This will result in three rows appearing in the result set:
- Box 1: A (100), B (60)
- Box 2: B (40), C (120)
- Box 3: C (20)
Ideally, the query would be smart enough to combine all the Cs, but for now - we're not too worried about that.
source to share
How about something like
SELECT SUM([Item quantity]) as totalItems
, SUM([Item quantity]) / 160 as totalBoxes
, MOD(SUM([Item Quantity), 160) amountInLastBox
FROM [Transactions]
GROUP BY [Transaction Id]
Let me know what fields in the result list you are looking for and I could come up with a better one
source to share
Have you read the Bible Bible?
http://sqlblog.com/blogs/hugo_kornelis/archive/tags/Bin+Packing/default.aspx
source to share
I was looking for something similar and all I could achieve was expanding the rows to the number of items in a transaction and grouping them into bins. Not very elegant though .. Also, since row aggregation is still very cumbersome in SQL Server (Oracle, I miss you!), I have to leave the last part. I mean summing up the counters in one row.
My solution looks like this:
Example of a transaction table:
INSERT INTO transactions
(trans_id, item, cnt) VALUES
('1','A','50'),
('2','A','140'),
('3','B','100'),
('4','C','80');
GO
Create a dummy sequence table that contains numbers from 1 to 1000 (I'm assuming the maximum number allowed for an item in one transaction is 1000):
CREATE TABLE numseq (n INT NOT NULL IDENTITY) ;
GO
INSERT numseq DEFAULT VALUES ;
WHILE SCOPE_IDENTITY() < 1000 INSERT numseq DEFAULT VALUES ;
GO
Now we can create a temporary table from the transaction table, in which each transaction and item exists "cnt" times in a subquery, and then gives the numbers in cells using division and grouping by cell number:
SELECT bin_nr, item, count(*) count_in_bin
INTO result
FROM (
SELECT t.item, ((row_number() over (order by t.item, s.n) - 1) / 160) + 1 as bin_nr
FROM transactions t
INNER JOIN numseq s
ON t.cnt >= s.n -- join conditionally to repeat transaction rows "cnt" times
) a
GROUP BY bin_id, item
ORDER BY bin_id, item
GO
Result:
bin_id item count_in_bin
1 A 160
2 A 30
2 B 100
2 C 30
3 C 50
In Oracle, the last step is just as simple:
SELECT bin_id, WM_CONCAT(CONCAT(item,'(',count_in_bin,')')) contents
FROM result
GROUP BY bin_id
source to share
try to pick some ideas from http://www.postgresonline.com/journal/index.php?/archives/138-Allocating-People-into-Groups-with-SQL-the-Sequel.html
he uses CTE
source to share
This is not the nicest answer, but I use a similar method to keep track of stock items through the ordering process, which is easy to understand and could lead to developing a better method than mine.
I would create a table called "PackedItem" or something similar. The columns will be:
packed_item_id (int) - Primary Key, Identity column
trans_id (int)
item_id (int)
box_number (int)
Each entry in this table represents 1 physical unit that you will send.
Let's say someone adds a row to transaction 4 with 20 of 12, I would add 20 records to the PackedItem table, all with a Transaction ID, Item ID and NULL number. If the row is updated, you need to add or remove records from the PackedItem table so that there is always a 1: 1 correlation.
When the time is right, you can just
SELECT TOP 160 FROM PackedItem WHERE trans_id = 4 AND box_number IS NULL
and set box_number
these entries to the next available window number until there are no entries left, where box_number
is NULL. This is possible using one rather complicated UPDATE statement inside a WHILE loop, which I don't have time for a complete build.
Now you can easily get your desired packing list by querying this table like this:
SELECT box_number, item_id, COUNT(*) AS Qty
FROM PackedItem
WHERE trans_id = 4
GROUP BY box_number, item_id
Benefits - easy to understand, fairly easy to implement. Pitfalls - if the table is out of sync with the transaction rows, the end result may be wrong; There will be many entries in this table, and this will be additional work for the server. It will be necessary that each identifier field be indexed to ensure good performance.
source to share