Random Addressing / Fragmentation

No.10980477 ViewReplyOriginalReport
I'm working on a large engineering project where I have identified a potential programming flaw. I am hoping one of you math whizzes can point me in the right direction (not solve, just point me at the proper branch of mathematics)

The system starts as follows, with empty addresses: (grossly simplified here, the real application is a massive 3D array)

>0000000000000000000000000

As orders come in, addresses are occupied sequentially. The number of spaces to occupy is somewhat random. Nice and simple for a while.

>XXX0000000000000000000000
>XXXYYYYYYY00000000000000
>XXXYYYYYYYZZZ00000000000

XYZ indicate addresses that have been "confirmed" but not filled yet. Once the system fills the order (X gets filled with 1s), those addresses are freed up:

>111YYYYYYYZZZ00000000000
>1's order is now complete, gets pulled, spaces re-used
>000YYYYYYYZZZ00000000000

This seems simple and logical, until you eventually hit a point where the array is fragmented like a hard-drive from recycling addresses. There is no set timing for when addresses are occupied, so consider it almost random. There IS, however, a metric for number of address groupings being processed per day. You may wind up with the following dilemma, and have no room for a 5-address order to be processed without truncating (truncating is a no-no):

>00XX0GG0LLLLL000FFF00AA0000BBBB

So where do you fit a 5-address order? I don't have the ability to "defragment," as this is a monstrous physical system, so what branch of mathematics or programming would help me solve this? I'm thinking some level of extra capacity and planning would help, but aside from just throwing some rough figure at it, I have no way of solving the dilemma. I'm almost thinking some form of kerning is needed. Extra capacity = $$$$$, so if a rough guess is 50% and an analysis reveals 20%, that 30% difference could be in the $10M to $15M range.

Any help/advice is appreciated.