Bin Allocation from a Lot based on set of rules

[Bala216]

Hi There,

Here is the screen shot of my problem scenario and output required....

Forum experts help is highly appreciated to solve this problem...

Thank you...

Box Number Generator Problem Description.xlsx
	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W
1	Box Number Generator
2
3	Technical Terms used:
4	1. Lot Number
5	2. Size
6	3. Pairs
7	4.Box Number
8
9	Scenario:
10	1. A lot number is a 5 digit unique identity number given for a group of pairs from different sizes.
11	2. A lot will have minimum 18 Pairs and maximum of 144 pairs in different sizes and multiples of 18 pairs (eg. 18,36,54,72,90,108,126,144)
12	3. Each size will have minimum zero pairs and maximum of 144 pairs and will be always multiple of 3. (eg. 0, 3, 6,9,12,15………max of 144)
13	4. Minimum size is 2.5 and increases with an increment of 0.5 and maximum would be 12.
14
15	Picotral Representation of a typical scenario:
16		Sizes / Pairs
17	Lot Number:	2.5	3	3.5	4	4.5	5	5.5	6	6.5	7	7.5	8	8.5	9	9.5	10	10.5	11	11.5	12	Total Pairs
18	12345	3		6	9	12		15		24	36	36						3				144
19	67890		15	3	3	9	12	15			3			12								72
20	78901			3	3	3	3	3	3	3	3	3	3	6								36
21
22
23	Objective:
24
25	1.When a size run is filled up for a lot number, then these sizes has to be split/ grouped into sum of 12 pairs.
26	2. Each group of pairs (called Box ) will be assigned a box number starting from 1 to maximum of 12.
27	3. A full box will have maximum of 12 pairs and minmum of 3 pairs and always be either 3 or 6 or 9 or 12.
28	4. Sizes more than 12 pairs are split into multiples of 12 and assigned box number
29	5. Sizes less than 12 are grouped with other sizes to make up 12 pairs if possible to form a box.
30	6. 3 can join only with 9, if this option is not available then the second option is to join with 6 & 3 . Simillarly 6 can join only with 6 or 3 & 3. 9 can join with 3
31	7. A box can have minimum one size and maximum of 4 sizes
32
33	A typical grouping of size / pairs into Box numbers for the above 3 lot numbers is as follows:
34
35	Lot No.	12345
36	Box Number	1	2	3	4	5	6	7	8	9	10	11	12
37	Size	2.5	3.5	4.5	5.5	6.5	6.5	7	7	7	7.5	7.5	7.5
38	Pairs	(1-3)	(1-6)	(1-12)	(1-12)	(1-12)	(13-24)	(1-12)	(13-24)	(25-36)	(1-12)	(13-24)	(25-36)
39
40	Size	4	5.5
41	Pairs	(1-9)	(13-15)
42
43	Size		10.5
44	Pairs		(1-3)													*
45
46	Size
47	Pairs
48
49	Lot No.	67890
50	Box Number	1	2	3	4	5	6	7	8	9	10	11	12
51	Size	3	3	3.5	5	5.5	8.5
52	Pairs	(1-12)	(13-15)	(1-3)	(1-12)	(1-12)	(1-12)
53
54	Size		4.5	4
55	Pairs		(1-9)	(1-3)
56
57	Size			5.5
58	Pairs			(13-15)
59
60	Size			7
61	Pairs			(1-3)
62
63	Lot No.	78901
64	Box Number	1	2	3	4	5	6	7	8	9	10	11	12
65	Size	3.5	5.5	7.5
66	Pairs	(1-3)	(1-3)	(1-3)
67
68	Size	4	6	8
69	Pairs	(1-3)	(1-3)	(1-3)
70
71	Size	4.5	6.5	8.5
72	Pairs	(1-3)	(1-3)	(1-6)
73
74	Size	5	7
75	Pairs	(1-3)	(1-3)
76
Problem Description

Cell Formulas
Range	Formula
V18:V20	V18	=SUM(B18:U18)

 

[i_nth]

It is a common issue with this type of problem that the requirements are unclear.
For example, using your test4 data, it is possible to have 23 non-zero parts in 14 boxes. It is also possible to have 22 non-zero parts in 15 boxes. I'm not sure if it is possible to have 22 non-zero parts in 14 boxes.
Which solution is preferred, and why? That would be a question for the OP to clarify.

 

[KRice]

Good point. About the "parts" term, does that mean any subset of shoes of one size added to a bin? For example, if I subdivide 9 pairs of size 10 into 3-3-3 to use toward filling three bins, then each of those would constitute a "part"...so in that case, three parts?

Just to add to the mix (or confusion?), I had a look at the test4 data (9, 6, 21, 9, 21, 9, 9, 9, 9, 9, 3, 6, 3, 3, 9, 9, 6, 3, 3, 3 ) with the three-table formula-based approach I posted. I get 14 boxes (13 complete and 1 incomplete), and those are formed from a total of 25 parts (using the definition I suggested above), while subdividing 2 sets of partials (size 10 was split 3-3-3, and size 10.5 was split 3-3).

 

[i_nth]

Yes, that's what I mean by "Parts".
The solution of 23 non-zero parts in 14 boxes comes from a slightly modified model, where I solve for the minimum number of boxes and then constrain the number of bins at that level and minimise the number of parts.

 

[KRice]

Thanks for the clarification. I'm curious if the OP weighs in about which factors matter and their relative weights: number of bins, number of parts, and number of sets of partials that are subdivided.

 

[Bala216]

H

Thanks for the link. I haven't had much luck with OpenSolver on other integer optimization problems, but this might be interesting to investigate further. I had a look at your Formulation/Notes and think your assessment of the number of sizes per bin (<=4) is correct: the number of partials is either 0, 3, 6, or 9--and since 0 is moot, one cannot have more than 4 sizes in a bin. So your point about not needing enforcement of that constraint is spot on.

I have to apologize for messing up the description of the rules...unfortunately, I forgot to mention a critical point: after the first partial is added to a bin and the search begins for the next partial, priority is given to using a 9 over a 6 or 3, and to using a 6 over a 3. Other than this detail, the rest of my description is consistent with earlier posts offered by @Bala216.

I'll recap the Phase 1 and Phase 2 rules because they illustrate something important:

Phase 1:

1. Allocate to individual bins all sets of 12 pairs (homogeneous sizes) that are readily apparent in the original list.

Phase 2:

1. Searches always begin at the left and proceed to the right (small-to-large size)---this applies to the first partial added to a bin and any subsequent partials.
2. The first partial added is always the smallest size available, and any other partials are added in the order they are encountered while first honoring the priority to use larger partials before smaller partials if the situation allows. This means that if we have a new bin and the smallest shoe size partial is a quantity of 3 (so it is added first), then the partials are searched left-to-right for a 9, and if none, then for a 6, and if none, then for another 3. If multiple 9's are encountered in this example, the first one would be added. Similarly, if multiple 6's are encountered and no 9's are available, then the first 6 would be added, and so on if 3's were present and no 9's or 6's were available...the first encountered would be added.
3. Partials are not to be subdivided.
4. For any given bin that is being filled, after searching for suitable partials and finding none, the bin is set aside and treated as an incomplete bin, and a new bin is begun.

The important take-away from the Phase 1 and Phase 2 rules is that they are completely deterministic. This part of the problem does not lend itself to optimization.

Once the partials remaining in incomplete bins are reinstated and the stringent rules for forming sets of 12 are lifted, as is done in Phase 3, that would lend itself to an optimization strategy. In that case, there is considerable latitude in combining the remaining partials and subdividing them if necessary. I believe the primary objective in that case would be to minimize the number of bins, and if there are multiple solutions, then preference would be given to those that minimize the number of sets of partials that need to be subdivided. Even then, more clarity would be needed to choose a preferred solution since there may be multiple solutions with those characteristics. With that said, it's not clear to me either where the threshold is for an acceptable solution...I think this comes close, but some details are still lacking.

HI i_nth... Welcome to the thread and thanks for your inputs..

Hi Kirk...Thanks for your in depth understanding of the problem and detailed description of it to i_nth.... I doubt whether I could have been able to do that..

Coming back to the discussion, I hope now there is no confusion up to phase-II. Coming to phase-III, as Kirk has mentioned, the objective would be to have less number of bins to combine the partials and also the final spill over partials quantity is to be minimum. In that way i think we can narrow down and eliminate possible multiple options. Here with I have attached the illustration of partial combination rule set for your further understanding and I hope that will help to understand better and arrive at an optimal solution. In the illustration the order of priority runs from top to bottom... Hope we will have interesting outcome...

And thank you guys for your valuable time and input to refine the solution to this problem....