Assume that we want to develop a warehouse management system, which picks up plastic boxes and stacks them on a pallet. A pallet has a maximum of 5 vertical box stacks and the maximum height of a box stack is 1400 mm. There are 3 box sizes with varying heights (other dimensions are the same). The heights of the boxes are 170 mm, 200 mm and 270 mm. An item is possible to place only in one type of box. All boxes are compatible to stack with each other. There are only two objectives: the number of completed pallets should be minimal, and the height difference of towers of boxes can be at most 500 mm.
The goal is to design a warehouse management program, which takes the order as an input, that is, the information of ordered items and how many boxes has been ordered. The program should determine how many boxes of each product should be stacked on a determined pallet and on a specific stack. A single product is always associated with only one box type.
How should one construct this kind of a program? I'm looking for general design guidelines and the methods to achieve the desired result. All tips and advices are welcome. I appreciate your effort.
Asked By : johnns
Answered By : afeldspar
It looks like what you have is a variant of the knapsack problem. However, you have an advantage that, rather than trying to optimize one "sack", you're simply trying to minimize the number of sacks (or in this case, pallets.)
I would have my program start by adding up the total height of the boxes I have to stack, and dividing it by the total height I could get out of each pallet if I could pack it perfectly (in this case, 7000mm). If there's no possible way I could fit the boxes I'm given on less than three pallets, for example, I'm better off knowing that to begin with.
So once I've calculated my P, the number of pallets I may be able to fit my boxes on (if I'm lucky and calculate well) I'm going to start distributing my biggest boxes first. I've got 5*P stacks to fill; I'm just going to go around them, always choosing the stack that's currently the lowest height to put the next box on. I'll continue that as I run out of the biggest boxes and move on to the next biggest.
If I'm fortunate, this is all I'll need to solve the problem. If I'm less fortunate, I'll have to have code that explores to see if swapping boxes around creates the room I need. This is where the problem gets hairy; there's only so much you can do other than just plain trial and error.
In planning for that contingency, I might be well-advised to do some searching to see if there are any "perfect" stacks that can be made with the box sizes I'll have to work with (for instance, 7 of the 200 mm boxes make a perfect stack). Any "perfect" stacks that I can make simplify the task of figuring out how to swap boxes between the remaining stacks ... or, regrettably, accepting that there's no way to swap boxes around so that they fit on our hoped-for number of pallets.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/28919
0 comments:
Post a Comment
Let us know your responses and feedback