Is this a bin packing problem?

On the face of it, the words "bin packing" seem to very accurately describe
this, but I'm not sure anymore.
The situation is packing ordered products into shipping cartons. However,
we don't have complete freedom to choose what items go into what cartons;
for several reasons they have to be packed strictly in stock number order.
E.g., if customer 1 has ordered 20 of SKU 100, 20 of SKU 101, 30 of SKU 102
and 40 of SKU 103, and all four items are the same shape and size and we
have one standard carton which can hold 50 items, we get this sequence:
carton SKU qty
1 100 20
1 101 20
1 102 10
2 102 20
2 103 30
3 104 10
Not all items are the same shape and size, but there are only a few
different form factors.
When a customer has ordered enough of a product to fully pack a carton with
just that product (or more than that amount), then a full carton of just
that product should be shipped; do not split the quantity in order to
finish packing mixed cartons. (This will make more sense with the example
below.)
There are other considerations, but this is the basic idea.
So. DDL time. This is simplified from what I actually have, but feel free
to make corrections if I've been stupid.
-- The input tables:
CREATE TABLE Order (
CustomerID int NOT NULL PRIMARY KEY,
Name varchar(40) NOT NULL
);
CREATE TABLE OrderItem (
CustomerID int NOT NULL REFERENCES Order (CustomerID),
SKU int NOT NULL REFERENCES Product (SKU),
Qty int NOT NULL,
PRIMARY KEY (CustomerID, SKU)
);
CREATE TABLE Product (
SKU int NOT NULL PRIMARY KEY,
FullCarton int NOT NULL
);
-- The output tables:
CREATE TABLE Carton (
CustomerID int NOT NULL REFERENCES Order (CustomerID),
CartonNum int NOT NULL,
Total int NOT NULL,
IsFull char(1) NOT NULL
CHECK (IsFull = 'Y' OR IsFull = 'N'),
-- IsFull is a marker for cartons that are packed full of *one single
product*, as
-- opposed to a mix of more than one product.
PRIMARY KEY (CustomerID, CartonNum)
);
CREATE TABLE CartonItem (
CustomerID int NOT NULL,
CartonNum int NOT NULL,
SKU int NOT NULL REFERENCES Product (SKU),
Qty int NOT NULL,
PRIMARY KEY (CustomerID, CartonNum, SKU),
FOREIGN KEY (CustomerID, CartonNum)
REFERENCES Carton (CustemerID, CartonNum)
);
-- Input sample data:
INSERT INTO Product (SKU, FullCarton) VALUES (100, 100);
INSERT INTO Product (SKU, FullCarton) VALUES (101, 100);
INSERT INTO Product (SKU, FullCarton) VALUES (102, 100);
INSERT INTO Product (SKU, FullCarton) VALUES (103, 100);
INSERT INTO Product (SKU, FullCarton) VALUES (104, 100);
INSERT INTO Product (SKU, FullCarton) VALUES (200, 200);
INSERT INTO Product (SKU, FullCarton) VALUES (201, 200);
INSERT INTO Product (SKU, FullCarton) VALUES (202, 200);
INSERT INTO Product (SKU, FullCarton) VALUES (203, 200);
INSERT INTO Product (SKU, FullCarton) VALUES (204, 200);
INSERT INTO Order (CustomerID, Name) VALUES
(10001000, 'Chicago Branch');
INSERT INTO OrderItem (CustomerID, SKU, Qty) VALUES (10001000, 100, 140);
INSERT INTO OrderItem (CustomerID, SKU, Qty) VALUES (10001000, 101, 121);
INSERT INTO OrderItem (CustomerID, SKU, Qty) VALUES (10001000, 200, 87);
INSERT INTO Order (CustomerID, Name)
VALUES (10001001, 'New York Branch');
INSERT INTO OrderItem (CustomerID, SKU, Qty) VALUES (10001001, 100, 67);
INSERT INTO OrderItem (CustomerID, SKU, Qty) VALUES (10001001, 101, 123);
INSERT INTO OrderItem (CustomerID, SKU, Qty) VALUES (10001001, 200, 118);
INSERT INTO Order (CustomerID, Name)
VALUES (10001002, 'Philadelphia Branch');
INSERT INTO OrderItem (CustomerID, SKU, Qty) VALUES (10001002, 100, 54);
INSERT INTO OrderItem (CustomerID, SKU, Qty) VALUES (10001002, 101, 149);
INSERT INTO OrderItem (CustomerID, SKU, Qty) VALUES (10001002, 200, 67);
-- What I'm looking for is (hopefully) two INSERT statements, one for
Carton, one for CartonItem, that produce this output:
SELECT * FROM Carton
CustomerID CartonNum Total IsFull
10001000 1 100 Y
10001000 2 139 N
10001000 3 100 Y
10001000 4 9 N
10001001 1 110 N
10001001 2 100 Y
10001001 3 108 N
10001002 1 100 N
10001002 2 100 Y
10001002 3 70 N
SELECT * FROM CartonItem
CustomerID CartonNum SKU Qty
10001000 1 100 100
10001000 2 100 40
10001000 2 101 21
10001000 2 200 78
10001000 3 101 100
10001000 4 200 9
10001001 1 100 67
10001001 1 101 23
10001001 1 200 20
10001001 2 101 100
10001001 3 200 108
10001002 1 100 54
10001002 1 101 46
10001002 2 101 100
10001003 3 101 3
10001003 3 200 67
Explanation: Chicago branch ordered 140 of the first product, so 100 of
them go in the first full carton and the next 40 go into the second carton.
They ordered 121 of the next product, so 100 go in their own carton (carton
3) and the other 21 into the first carton. They ordered 87 of the third
product and 78 of them will fit in the first carton, so 78 go in that
carton and the last 9 go in another carton (carton 4). Similar for the
other two customers.
The ordering and numbering of the cartons that I have there is the optimal
one, but I would settle for statements that generate them out of order; I
can reorder them afterwards.
So. Is this "bin packing" or is it only remotely related to it?Ross,
You can call this a "bin packing" problem, but that term is
more usually applied to a specific problem that is more open-
ended than the one you have (see
http://www.nist.gov/dads/HTML/binpacking.html).
You might call this a "box filling" problem, and a greedy algorithm
looks like it will work fine.
There are set-based solutions for problems like these, but I
hesitate to suggest one, because of your comments about "only a few
different form factors" and "there are other considerations, but ..." I
doubt
any practical set-based solution can easily handle the kind of variations
those comments suggest.
More likely than not, you will do best with a solution that uses cursors
or loops, and I'd suggest giving the problem to a crack C/C++/C# programmer
with the condition that the source data will only be supplied in linked
(one-way)
lists, but in whatever order is most convenient.
Then translate the result into a cursor-based solution, using the
"convenient"
order to define cursors.
Here is a newsgroup thread that discusses what I think is a very
similar problem and offers some solutions. Hopefully you can adapt one
of these solutions to your needs.
http://groups.google.com/groups?hl=...son+bin+packing
Ignore the posts in this thread by CELKO, who seems to have misunderstood
the original question - see the suggestions by me and by John Gilson.
Steve Kass
Drew University
Ross Presser wrote:

>On the face of it, the words "bin packing" seem to very accurately describe
>this, but I'm not sure anymore.
>The situation is packing ordered products into shipping cartons. However,
>we don't have complete freedom to choose what items go into what cartons;
>for several reasons they have to be packed strictly in stock number order.
>E.g., if customer 1 has ordered 20 of SKU 100, 20 of SKU 101, 30 of SKU 102
>and 40 of SKU 103, and all four items are the same shape and size and we
>have one standard carton which can hold 50 items, we get this sequence:
>carton SKU qty
>1 100 20
>1 101 20
>1 102 10
>2 102 20
>2 103 30
>3 104 10
>Not all items are the same shape and size, but there are only a few
>different form factors.
>When a customer has ordered enough of a product to fully pack a carton with
>just that product (or more than that amount), then a full carton of just
>that product should be shipped; do not split the quantity in order to
>finish packing mixed cartons. (This will make more sense with the example
>below.)
>There are other considerations, but this is the basic idea.
>So. DDL time. This is simplified from what I actually have, but feel free
>to make corrections if I've been stupid.
>-- The input tables:
>CREATE TABLE Order (
> CustomerID int NOT NULL PRIMARY KEY,
> Name varchar(40) NOT NULL
> );
>CREATE TABLE OrderItem (
> CustomerID int NOT NULL REFERENCES Order (CustomerID),
> SKU int NOT NULL REFERENCES Product (SKU),
> Qty int NOT NULL,
> PRIMARY KEY (CustomerID, SKU)
> );
>CREATE TABLE Product (
> SKU int NOT NULL PRIMARY KEY,
> FullCarton int NOT NULL
> );
>-- The output tables:
>CREATE TABLE Carton (
> CustomerID int NOT NULL REFERENCES Order (CustomerID),
> CartonNum int NOT NULL,
> Total int NOT NULL,
> IsFull char(1) NOT NULL
> CHECK (IsFull = 'Y' OR IsFull = 'N'),
> -- IsFull is a marker for cartons that are packed full of *one single
>product*, as
> -- opposed to a mix of more than one product.
> PRIMARY KEY (CustomerID, CartonNum)
> );
>CREATE TABLE CartonItem (
> CustomerID int NOT NULL,
> CartonNum int NOT NULL,
> SKU int NOT NULL REFERENCES Product (SKU),
> Qty int NOT NULL,
> PRIMARY KEY (CustomerID, CartonNum, SKU),
> FOREIGN KEY (CustomerID, CartonNum)
> REFERENCES Carton (CustemerID, CartonNum)
> );
>-- Input sample data:
>INSERT INTO Product (SKU, FullCarton) VALUES (100, 100);
>INSERT INTO Product (SKU, FullCarton) VALUES (101, 100);
>INSERT INTO Product (SKU, FullCarton) VALUES (102, 100);
>INSERT INTO Product (SKU, FullCarton) VALUES (103, 100);
>INSERT INTO Product (SKU, FullCarton) VALUES (104, 100);
>INSERT INTO Product (SKU, FullCarton) VALUES (200, 200);
>INSERT INTO Product (SKU, FullCarton) VALUES (201, 200);
>INSERT INTO Product (SKU, FullCarton) VALUES (202, 200);
>INSERT INTO Product (SKU, FullCarton) VALUES (203, 200);
>INSERT INTO Product (SKU, FullCarton) VALUES (204, 200);
>INSERT INTO Order (CustomerID, Name) VALUES
> (10001000, 'Chicago Branch');
>INSERT INTO OrderItem (CustomerID, SKU, Qty) VALUES (10001000, 100, 140);
>INSERT INTO OrderItem (CustomerID, SKU, Qty) VALUES (10001000, 101, 121);
>INSERT INTO OrderItem (CustomerID, SKU, Qty) VALUES (10001000, 200, 87);
>INSERT INTO Order (CustomerID, Name)
> VALUES (10001001, 'New York Branch');
>INSERT INTO OrderItem (CustomerID, SKU, Qty) VALUES (10001001, 100, 67);
>INSERT INTO OrderItem (CustomerID, SKU, Qty) VALUES (10001001, 101, 123);
>INSERT INTO OrderItem (CustomerID, SKU, Qty) VALUES (10001001, 200, 118);
>INSERT INTO Order (CustomerID, Name)
> VALUES (10001002, 'Philadelphia Branch');
>INSERT INTO OrderItem (CustomerID, SKU, Qty) VALUES (10001002, 100, 54);
>INSERT INTO OrderItem (CustomerID, SKU, Qty) VALUES (10001002, 101, 149);
>INSERT INTO OrderItem (CustomerID, SKU, Qty) VALUES (10001002, 200, 67);
>
>-- What I'm looking for is (hopefully) two INSERT statements, one for
>Carton, one for CartonItem, that produce this output:
>SELECT * FROM Carton
>CustomerID CartonNum Total IsFull
>10001000 1 100 Y
>10001000 2 139 N
>10001000 3 100 Y
>10001000 4 9 N
>10001001 1 110 N
>10001001 2 100 Y
>10001001 3 108 N
>10001002 1 100 N
>10001002 2 100 Y
>10001002 3 70 N
>SELECT * FROM CartonItem
>CustomerID CartonNum SKU Qty
>10001000 1 100 100
>10001000 2 100 40
>10001000 2 101 21
>10001000 2 200 78
>10001000 3 101 100
>10001000 4 200 9
>10001001 1 100 67
>10001001 1 101 23
>10001001 1 200 20
>10001001 2 101 100
>10001001 3 200 108
>10001002 1 100 54
>10001002 1 101 46
>10001002 2 101 100
>10001003 3 101 3
>10001003 3 200 67
>
>Explanation: Chicago branch ordered 140 of the first product, so 100 of
>them go in the first full carton and the next 40 go into the second carton.
>They ordered 121 of the next product, so 100 go in their own carton (carton
>3) and the other 21 into the first carton. They ordered 87 of the third
>product and 78 of them will fit in the first carton, so 78 go in that
>carton and the last 9 go in another carton (carton 4). Similar for the
>other two customers.
>The ordering and numbering of the cartons that I have there is the optimal
>one, but I would settle for statements that generate them out of order; I
>can reorder them afterwards.
>So. Is this "bin packing" or is it only remotely related to it?
>|||I would first pack all of the single product boxes, which will leave
you with a set of less than one box SKU quantities. Since the other
rule is that the boxes are packed in SKU order, just go down this list.
This is probably best done in a procedural language, but I have a
two-part article on LIFO-FIFO inventory on www.DBAzine.com Just use SKU
instead of stocking date to get the box numbers.
Another article might help. I did a 30-minute data mining job for a
mail-order BBQ company that needed to add box sizes to its packing
slips. We found all of the unique configurations in the order history,
how often they occurred and the boxes used to pack them. If the same
configuration had two or more boxes, then you should go with the
smaller size. Most of the orders were stock gift boxes -- no problem.
As it turned out, there were 4995 unique configurations in the custom
orders which covered about 99.5% of those cases. Do a relational
division and you have the box size; if the division, hand pick that
order. If this kind of look up will work for you, it is the fastesst
way to go.
http://www.tdan.com/pubpers0501.htm|||On Mon, 29 Aug 2005 12:31:33 -0400, Steve Kass wrote:

> Ross,
> You can call this a "bin packing" problem, but that term is
> more usually applied to a specific problem that is more open-
> ended than the one you have (see
> http://www.nist.gov/dads/HTML/binpacking.html).
> You might call this a "box filling" problem, and a greedy algorithm
> looks like it will work fine.
>
Thank you, Steve. After reading the thread, the "box filling" vs. "bin
packing" distinction *exactly* describes the difference. I *don't* want a
minimal solution at all; I *need* a solution that fills strictly in order.
And now to confess: I already have a partially set-based algorithm, which
is based on doing a complicated self join (to generate a "space used up"
column) followed by a series of updates. This may be similar to the greedy
algorithm you describe. Here's an excerpt:
select a.club,a.ckey,sum(b.spacefactor*b.qty) "spaceused"
into #spaceused
from #clubitem a
inner join #clubitem b on a.club=b.club and a.boxgroup=b.boxgroup and
a.ckey >= b.ckey
group by a.club,a.boxgroup, a.ckey
order by a.club,a.boxgroup, a.ckey
update #clubitem
set spaceused=b.spaceused
from #clubitem a, #spaceused b
where a.club = b.club and a.ckey = b.ckey
-- space1 is space before adding item;
-- space2 is space after adding item, with >@.fullbox if filled up;
-- space3 is space after adding item and closing carton
update #ClubItem
set space1= (spaceused-qty*spacefactor) % @.fullbox,
space2= ((spaceused-qty*spacefactor) % @.fullbox) + qty*spacefactor,
space3=(((spaceused-qty*spacefactor) % @.fullbox) + qty*spacefactor) %
@.fullbox
Ugly as sin, eh? Still faster than when I did it in a client-side cursor.
I hoped that by submitting to the group I could get a fresh perspective.
The thread you pointed out should help; thanks.