1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ A question: is the maximum height difference between box towers on a pallet between ANY of the five box stacks, or between adjacent box stacks? $\endgroup$ – afeldspar Aug 4 '14 at 22:50
  • $\begingroup$ @afeldspar Between any of the five box stacks. $\endgroup$ – johnns Aug 4 '14 at 23:04
  • 1
    $\begingroup$ This is bin packing, isn't it? Find the "best" (according to your needs) algorithm that solves that problem and use it. $\endgroup$ – Raphael Aug 7 '14 at 8:20
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thank you very much for a thorough answer! Much appreciated! It indeed looks like a knapsack problem. $\endgroup$ – johnns Aug 5 '14 at 1:28
  • 1
    $\begingroup$ Note that bin packing is a hard problem, too. You propose a greedy algorithm; it may be a usable heuristic, but it's not optimal. $\endgroup$ – Raphael Aug 7 '14 at 8:21
  • $\begingroup$ I'm pretty sure anyone who can devise an optimal algorithm for this problem has some major awards to collect. =) $\endgroup$ – afeldspar Aug 7 '14 at 11:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.