Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
    
I am confused by you "Y-time", do you mean width? –  Pieter B May 11 '13 at 17:20
    
I think his use of time for Y means that it's how long the space is occupied by the item. –  Loren Pechtel May 11 '13 at 18:18
    
Now graphics are added, to clarify the problem, –  Independent May 11 '13 at 18:52
    
Should i be more clear in my attempt to describe, or is the alorithm hard to get? –  Independent May 12 '13 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. –  Independent May 25 '13 at 10:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.