Bin Packing Problem - but not quite?

[bearminmaxing]

I'm trying to automate a process I currently do very inaccurately - specifically I'm trying to optimize the number of parts and sheets used in printing. The closest approximations that I've been able to find names for are the Bin Packing Problem and the Knapsack Problem.

1 MASTER SHEET can hold 22 PNs. PNs on a single MASTER SHEET can have more than one instance on a MASTER, but PNs cannot be split across multiple MASTERs. Each PN has different quantities required. MASTER SHEETs can be printed as many times as required to produce required quantities of PNs.

For example, PNs A-1 has a required quantity of 24, A-4 has a required quantity of 141, and A-5 has a required quantity of 90. If these PNs are combined onto one MASTER with 2 instances of A-1, 12 instances of A-4, and 8 instances of A-5, the MASTER SHEET can be printed 12 times to achieve the required quantities with low numbers of OVERAGEs (respectively: 0, 3, 6).

My objective is to allocate PNs with varying quantities to MASTER SHEETs while creating the fewest number of MASTER SHEETs and fewest OVERAGEs (how many times each MASTER has to be printed are not limited and does not have to be optimized). Below I have an example of a set of PNs that I was provided and which I allocated using trial and error.

Is there a way for me to automate this process using Solver or a similar add-on? I've looked up solutions for the Bin Packing Problem and the Knapsack Problem but because my objective is slightly different from those problems, I can't find a way to make those solutions work correctly.

BPPSolution.xlsx
	A	B	C	D	E	F	G
1	PN	QTY	MASTER	QTY/MASTER	TIMES PRINTED	OVERAGE
2	A-1	24	1	2	12	0
3	A-2	18	2	4	5	2
4	A-3	30	2	6	5	0
5	A-4	141	1	12	12	3
6	A-5	90	1	8	12	6
7	A-6	26	2	6	5	4
8	A-7	720	3	22	33	6
9	A-8	7	2	2	5	3
10	A-9	18	2	4	5	2
11
Sheet2

Cell Formulas
Range	Formula
F2:F10	F2	=(E2*D2)-B2

 

[Logit]

I'm having a difficult time understanding the 'common denominator' in your image. How have you decided that A1, A4, A5 belong in the same category ?

Can you provide an 'After' example of what your data would look like ?

 

[bearminmaxing]

I'm having a difficult time understanding the 'common denominator' in your image. How have you decided that A1, A4, A5 belong in the same category ?

Can you provide an 'After' example of what your data would look like ?

Like I said, it's kind of a trial and error process - and a bit arbitrary at times because of how many PNs I receive at one time to be split into MASTER SHEETs, so I try to kind of group things instinctively/based on my pattern recognition (I am a graphic designer but handle a lot of mass production products, so I've been trying to optimize my work in Excel). In that particular example I actually combined a couple of sets just to get a dataset that wasn't too large for demonstration purposes, so it's likely not the most efficient way to allocate those quantities.

Here's a different example that was a full list of PNs I received together to split.

Because PNs B-1 and B-2 are much larger numbers than the rest, I've grouped those two together. There are 12 PNs at QTY 13, so I've grouped 11 of those together to print approximately half of the sheet amounts (whole numbers only). I've grouped the last one with B-3 and B-4 at QTY 5 and 20 respectively. This, again, might not be the most efficient way to distribute the quantities, but after going through a couple of permutations it seems like this would create the least amount of OVERAGEs.

I also forgot to mention something in my original post - MASTERs shouldn't have empty spaces, so I add extra of the PNs (again, arbitrarily decided) to make sure each group adds up to 22. COLUMN E, named "Q/M ADD", has those additional instances as I've decided to distribute them.

Book1
	A	B	C	D	E	F	G
1	PN	QTY	MASTER	QTY/MASTER	Q/M ADD	TIMES PRINTED	OVERAGE
2	B-1	205	1	12	0	18	11
3	B-2	165	1	10	0	18	15
4	B-3	5	2	3	0	2	1
5	B-4	20	2	10	1	2	2
6	B-5	13	2	7	1	2	3
7	B-6	13	3	2	0	7	1
8	B-7	13	3	2	0	7	1
9	B-8	13	3	2	0	7	1
10	B-9	13	3	2	0	7	1
11	B-10	13	3	2	0	7	1
12	B-11	13	3	2	0	7	1
13	B-12	13	3	2	0	7	1
14	B-13	13	3	2	0	7	1
15	B-14	13	3	2	0	7	1
16	B-15	13	3	2	0	7	1
17	B-16	13	3	2	0	7	1
Sheet1

Cell Formulas
Range	Formula
D2:D17	D2	=ROUNDUP(B2/F2,0)
G2:G17	G2	=((F2*D2)+(F2*E2))-B2

 

[Logit]

Your 'arbitrary' method of selecting rows to print doesn't provide a set means of selection. There isn't an Excel formula or VBA macro that would
perform in the same manner as your 'arbitrary selection manner'.

The closest you could get to your method of selection would be to create a macro that randomly selects rows to print. There would be no rhyme nor reason
regarding which rows would be selected.

You'll need to determine a better method of selecting which rows to group for printing.

 

[bearminmaxing]

Your 'arbitrary' method of selecting rows to print doesn't provide a set means of selection. There isn't an Excel formula or VBA macro that would
perform in the same manner as your 'arbitrary selection manner'.

The closest you could get to your method of selection would be to create a macro that randomly selects rows to print. There would be no rhyme nor reason
regarding which rows would be selected.

You'll need to determine a better method of selecting which rows to group for printing.

I apologize for any misunderstanding - when you asked how I decided how to group items, I didn't realize you were asking what the most methodical/logical way I would like to determine a group was. I recognize that my means of selection isn't set, however it's currently quicker for me than to go through every possible solution (sometimes for lists of hundreds of PNs). That's why I mentioned the Bin Packing Problem in my original post. I'm looking for an formula or process of using Solver to run something akin to a recursive algorithm to automatically go through the options to make calculations and find the best fit.

If I'm barking up the wrong tree, I understand, but there are solutions for the Bin Packing Problem using Solver or Macros that I've found and since solutions for that problem similarly involve recursive logic, and I feel like there must be a solution for this particular problem.

 

[Logit]

Someone better than me will need to address your request. Best wishes.