0

Can someone point me in the right direction to solve the following?

I have a machine that is able to process a batch containing any number of items, each with some length $L_n$, as long as the total length of all items in each batch does not exceed some quantity $Q$.

If I have a large set of items, how do I find the optimal allocation of items into $j$ batches that minimize the total "wasted" space:
$\sum_{i=1}^{j} (Q - L_1 - L_2 - .. - L_n)$

I've looked at job shop and single-machine scheduling, but I'm unsure of how to apply these methods in practice.

Please let me know if the question needs clarification. Thanks for your help!

mdho
  • 1
  • Why wouldn't one just make each batch size $Q$ and then the remainder on the last batch? Am I misinterpreting the question? – Dhanvi Sreenivasan Oct 27 '20 at 08:45
  • @DhanviSreenivasan My guess is that each item has a discrete size, so getting exactly $Q$ in a batch will be hard as you can't split items (processes, whatever^^). It's one of these discrete binning problems that is most likely NP-complete, but I don't remember which one right now. – Dirk Oct 27 '20 at 09:00
  • That makes sense.. but rather than trying to figure out the question we should wait for clarification from the poster – Dhanvi Sreenivasan Oct 27 '20 at 09:01
  • It seems to be a knapsack problem. There are various approximations algorithms for these. – DavidW Oct 27 '20 at 09:31
  • @DhanviSreenivasan, Dirk is exactly right. Each item has a size than cannot be split, so the "wasted" space will never be zero. For example, if Q=10 and the items are beams in lengths of 4,3, 4,6 and 4,8. – mdho Oct 28 '20 at 09:16
  • @DavidW, it does indeed seem like a knapsack problem. I will look more into this later today. Thanks! – mdho Oct 28 '20 at 09:19
  • @Dirk, thanks, I will look into binning problems! – mdho Oct 28 '20 at 09:22

0 Answers0