I have a situation where I would like your input and think over / solve algorithm.

The specs

There are inventories with a specified amount of capacity.
'X (width) and Y (time)' creates together a total space. '60 * 100 = 6000'. In reality "width" are a business value unit, but we can talk width here.

Now there also are boxes, which take a part of the space.
Each box take width (X) and time (Y). Two boxes with 80 * 20 each, will fill a inventory with 1600+1600. It will result a fill factor, 2800 space left in the inventory, after the boxes are added. Each box always belong to it's inventory.

There exist unlimited, serial dependent, inventories with boxes added individually. The former inventory have to be performed before next are performed.

Boxes themself have a attribute, like a color, which make a ownership in higher context. Like a "give me all boxes of color -yellow-" context. I.e. to find out which inventories contain that color. A box with same color can exist several times, even in same inventory. But if in same inventory, they have unique box-id's.

The problem

There have to be added optimization strategy which make width (X) adjustable. Time (Y) is still fixed and can't change. The optimization rule is that available space in former inventory should be filled with a part/slice from second inventory.

Time must fit. I.e. 2x15 or 1x25 can fit to 1x30. 1x35 can't fit. Also the width added to former, must be reduced from second. Remember that a box isn't allowed to be removed from it's inventory (but width can be 1 as minimum). Though, on adjustment, new boxes have to be created in the former inventory.

It's a mathematical theory but i mainly want to transform a algorithm of this kind, into code. Or give the question a glance of what kind of theories to look for. Perhaps this is a common problem? or too complex considered as "re-invent the wheel" and recommend to buy a third party module.

[Edit] 'length' changed to 'width'
Added a graphic to better illustrate how the optimization rule will apply. enter image description here

There are a little green piece remaind at right, after optimization, because of the "at least 1 width must remain"-rule. The red and blue did not fit fully.

  • I am confused by you "Y-time", do you mean width?
    – Pieter B
    May 11, 2013 at 17:20
  • I think his use of time for Y means that it's how long the space is occupied by the item. May 11, 2013 at 18:18
  • Now graphics are added, to clarify the problem, May 11, 2013 at 18:52
  • Should i be more clear in my attempt to describe, or is the alorithm hard to get? May 12, 2013 at 8:11
  • I think there can be a hint related to two dimensional stock cutting problem. There also is a kind of problem called knapsack, which is more about weight. However this is also about move load between areas. May 25, 2013 at 10:46


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.