What is the best design for dynamic assignment of locations for variable sized grid boxes to occupy? I want to build a database that will have limited single locations to put boxes. It's divided by lanes and bays. 

Imagine a 4x4 grid, with a total of 16 slots, and every time I query the tables, I want to return one location for me to put boxes down. 

My approach is to have every slot named and stored in database. And have a flag "occupied" and name for the box to keep track of the box location. The tricky part is there is different sizes of boxes. Some will occupied 3 slots, some will occupy 2 slots and some will occupy 1 slot. 

How can I design the database structure so that it's easier for me to query the next available slot based on the size?



Responses to comments


  Is this some resource scheduling application?


It's more like a dynamic space allocation application.


  Are the boxes to be allocated are mono- or bi-dimensional? In other words, do you allocate a space of 2x2 boxes or 4 boxes? In the second case, can you allocate both "horizontally" and "vertically"?    


You can only go one way, neither, entire locations is either they go all horizontally or all vertically, they can never be both. Just the size is different, it can occupy 1 slot, 2 slots or 3 slots, but once it is occupied, it can never be used for another box, unless the previous box removed.

Boxes can be placed in the grid horizontally for an entire grid, you can have another grid that can put boxes down vertically. Once a grid is set for this property, it will stay like that.


  Do you have some kind of classification regarding the boxes sizes? Do you have, as stated in comments, only three different sizes of boxes? In case you do not have it, I think that such classification is necessary in order to ensure compatibility between the boxes and the grids (via the “slots”), and it is also necessary to take into account the common dimensions: width, height and depth. 


The boxes can allocate 1 slot, or 2 slots or 3 slots, it depends on the size.


  Are the grids fixed to 4x4 exclusively? 


Actually 4X4 is a simplified example I gave. The actual size could be 31X8, imagine OOOOOOOO X31 and 8 lanes of those.


  Are you planning to include different types of grids (for instance, 5x3, 10x10, 6x4, etc.) in the future?


The size won't be changed very often. It's pretty set, if there is space increase, I can always add them.


  What is the meaning of the terms bays and lanes in your business context?


Bays and lanes are just terms to distinguish the X, and Y. On a 31 slots per lane, and 8 lanes in each grid. OOOOOOOO X 31 and 8 lanes of these next to each other vertically, bay means each of the "O", and lane is 8 lanes for each row of 31 "O".
This is actually an NP-complete problem 

You won't find an optimal way to pack your bins, but you can find a good way

Here's Joe Celko's take on it:

https://www.simple-talk.com/sql/t-sql-programming/bin-packing-problems-the-sql/