Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase

Packing Optimization Expand / Collapse
Author
Message
Posted Wednesday, December 18, 2013 1:16 PM
SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-Enthusiastic

Group: General Forum Members
Last Login: 2 days ago @ 9:34 AM
Points: 158, Visits: 617
So I have a client that wants to build a stored proc to determine the most optimal way to pick and pack items. Let's say for example it's shoes. He wants to be able to create master cartons of the most commonly ordered items at the manufacturer instead of having his warehouse do it when they arrive. He already knows how to build the master cartons but this SP would be used to look at incoming customer orders (bulk orders) and determine which master cartons would best fit the need of the order and the remainder of the items would be picked and packed into a separate box. An order has to fully utilize the master carton or it doesn't qualify and all items would be picked and packed.

So I'm trying to figure out the best way to build a packing optimization solution...whether that is via recursive code or an SSIS package.

Any thoughts on how to best do this type of scenario?
Post #1524337
Posted Wednesday, December 18, 2013 2:25 PM


SSC Eights!

SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!

Group: General Forum Members
Last Login: Today @ 1:49 PM
Points: 897, Visits: 7,101
You might want to start here:
https://www.simple-talk.com/sql/t-sql-programming/bin-packing-problems-the-sql/

Mr. Celko is always an interesting read unless he happens to be answering a forum question.




And then again, I might be wrong ...
David Webb
Post #1524359
Posted Wednesday, December 18, 2013 2:59 PM
SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-Enthusiastic

Group: General Forum Members
Last Login: 2 days ago @ 9:34 AM
Points: 158, Visits: 617
Thank you for the response. Though this is interesting, I'm not worried about the ability to pack items efficiently, rather reducing the man power required to pick items. So if 10 of the 15 items required are already contained in a "master carton" then we pick 6 total boxes (one master carton and five individual boxes) rather than picking 15 total boxes.

So the algorithm would need to determine if the contents of a master carton will be 100% utilized to fulfill part of the order, then determine if there are other master cartons that could fill any of the remainder of the order, and continue on until no more master cartons will work, and return the remaining items to be picked.
Post #1524366
Posted Wednesday, December 18, 2013 3:24 PM


SSCertifiable

SSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiable

Group: General Forum Members
Last Login: Today @ 2:48 PM
Points: 6,172, Visits: 7,242
In general when looking at problems with these types of algorithms, it's helpful if you have a data sample complex enough to show the issue that we can poke at.

However, the algorithm itself is annoyingly complex when you have multiple master cartons. The reason for this is the number of different assemblies you can make to 'fill gaps' depending on the order that's chosen. For example, if you have 5 master cartons with overlap, how do you determine which master carton to grab that fits well with another master carton that doesn't? It's not simply selecting the master carton, but multiple possible master cartons depending on who overlaps what.

Generic example: I have master carton that holds A,B,C, and another that holds A,B,C,D, and yet a third master carton that holds D,E, and F. An order comes in for A through F. If the 4 piece master carton gets selected (the largest overlap) and pick the other two items, then I miss the opportunity to use the DEF Master Carton, which could be used with the ABC carton. Start stacking these possibilities and it starts looking like a puzzle assembly.

How do you get these to mesh well? Well, really... you don't. What you have to do is slap EVERY combination of non-overlapping packages over the order, and see which has the least picks. This gets even MORE complex if you start looking at quantities, because overlaps no longer can be excluded. Let's say I get an order for 4 As, 2 Bs, 5Cs, and 1 D. Now I grab an ABCD Master carton, an ABC Master Carton, and pick 2 As and 3 Cs. So as this algorithm attempts to figure it out, it has to reduce quantities as you apply packages.

At this point, I'd have to see the full business expectation and packaging methods, standard order ideas, and the like to determine the algorithm. It would have to be very custom because there's no 'perfect way', just a lot of 'good enough' ideas (at least to me) that I would have to pick the best of to apply to the expectations.

However, the tool to apply wouldn't be my first question here. I'd want to nail down the algorithm I want to work with, then pick the tool. I really don't see a difference here between T-SQL, .NET, and SSIS for the implimentation until you get into the nitty gritty of the algorithm, then you'd just pick the easiest tool to implement it with.

On a side note, I've got an inkling of a thought about pre-assembling the carton possibilities (dynamically in theory) and then applying all the carton pre-builds against the order to see what had the least 'picks', but I don't really have time to assemble a full bore test process against that to see if it has merit.



- Craig Farrell

Never stop learning, even if it hurts. Ego bruises are practically mandatory as you learn unless you've never risked enough to make a mistake.

For better assistance in answering your questions | Forum Netiquette
For index/tuning help, follow these directions. |Tally Tables

Twitter: @AnyWayDBA
Post #1524377
« Prev Topic | Next Topic »

Add to briefcase

Permissions Expand / Collapse