# A problem similar to bin packing

Let's say we have $n$ items of size $si_i$ and $m$ containers, each has a capacity $sc_i$. Every container can have at most one item at a time, provided its size is less than or equal its capacity.

Now we add time axis to this problem, because otherwise it would be trivial. Every item $i$ starts to exist at time $t_{i1}$ and ceases to exists at $t_{i2}$. You could visualize this with Gant diagram. There are no limitations of how many items may exist simultaneously, or anything like that. All we know that every item has its birth and death time. Also $t_{i1}, t_{i2} \in \{0,1,2,...,59\}$ and $t_{i2}>t_{i1}$. These are all constraints on $t_{i1}$ and $t_{i2}$

How to assign containers to all items, assuming the solution exists? The naive approach is to assign the smallest possible container to every item, but the order does matter:

If the are two avaliable containers $c_1$ and $c_2$ of capacity $sc_1=10$ and $sc_2=12$, if $c_1$ is assigned to the 1st item (because it's the smallest available container), and $c_2$ to the 2nd item (again, the smallest available container), the 3rd item won't have any available container. However if you assign the smallest container to 2nd and then 1st item, there will also be a container of capacity $12$ for the 3rd item, because it won't be blocked by the 2nd item.

Does this problem as a name already? And is there any simple algorithm to solve it, except brute force?

• This isn't really similar to bin packing. It's a scheduling problem. – Yuval Filmus Mar 12 '16 at 10:56

Your problem belongs to the family of problems known as fixed interval scheduling. For a recent survey, see Kovalyov et al. A classical paper of Arkin and Silverberg solves the problem when all sizes or capacities are the same, and shows that if you generalize the notion of size then the problem of deciding whether all jobs (i.e., items) can be scheduled (i.e., stored) is NP-complete, though it has an $O(n^{k+1})$ solution, where $n$ is the number of jobs and $k$ is the number of machines (i.e., containers).

Your problem is easier than the NP-complete variant considered by Arkin and Silverberg:

1. Your constraints on which jobs can be scheduled on which machines are not arbitrary – they depend on the notion of size.