4
$\begingroup$

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:

enter image description here

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?

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

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.

  2. Your timeframe is short.

  3. You are guaranteed a solution. (Though this doesn't usually make the problem any easier.)

The literature on the problem is probably vast, so perhaps someone already considered your particular variant.

$\endgroup$
  • $\begingroup$ Arkin and Silverbergs in their paper described the algorithm that maximizes the value of jobs completed. In my case, I actually have to verify if there exists a scheduling such that all jobs are executed. I guess if such a schedule exists, then maximization of the value of completed jobs is equivalent to my problem (where I want to execute all of them, and I know it's possible), right?. $\endgroup$ – user5539357 Mar 14 '16 at 10:02
  • $\begingroup$ Right, that's completely equivalent, though your problem might be easier. $\endgroup$ – Yuval Filmus Mar 14 '16 at 10:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.