Bin Packing Algorithm

Question

question

SudheerReddy asked Dec 12, '19 Braydn T commented Jan 3, '20

Bin Packing Algorithm

As shown in below image, I am trying to pull items where cumulative Value should be <=9.

First Bin Packed with id:2 Value 9 (100% bin utilization)

Second BIn Packed with id:3 Value 9 (100% bin utilization)

Third BIn Packed with id:9 Value 9 (100% bin utilization)

Fourth Bin Packed with id:6 and id:8 cumulative Value 9 (100% bin utilization)

Fifth Bin Packed with id:7 and id:10 cumulative Value is 9 (100% bin utilization)

Sixth Bin packed with id:4 Value 7 (bin Utilization <100)

Seventh Bin packed with id:1 Value 3( bin utilization<100)

For example following code pulls first token in the list with Value 3 because when we add next token Value, the cumulative exceeds >=9. So first token is pulled. Instead need to loop all the tokens and pull the tokens where bin utilization is high.

List itemList = List("ItemList1");
int listLen = itemList.entries().length;
int valueSum = 0;
for (int i = 1; i <= listLen; i++)
{	
	valueSum += List("ItemList1").entries()[i].value.labels["Value"].value;
	
	if(valueSum >= 9)
	{
		return i - 1;
	}
}
return 0;

Team I need to pack the bins in the above mentioned way. Please help me on this.I am attaching model for reference

binpacking.fsm

Software Version:

FlexSim 19.2.4

list

query1.jpg (37.7 KiB)

binpacking.fsm (32.0 KiB)

· 5

Braydn T commented · Dec 12, 2019 at 09:22 PM

@Sudheer R

what would you like to have happen with the tokens that are passed over? should the stay on the list?

I think the main issue you are going to encounter is you have one token that is doing all the pulling. All of the items pulled will go to one token. You will have to have a token run the algorithm, determine the number of bins that will be released and then release that number of tokens to your algorithm again, and then pull from the list.

As for your algorithm I would take a look at the First Fit Algorithm and see if you can adapt it for your needs. First fit has bins with different capacities, but you should be able to adapt it for your needs.

0 ·

SudheerReddy Braydn T commented · Dec 12, 2019 at 11:34 PM

@Braydn T Thanks for your input.

Could you please share First Fit Algorithm code or sample model so that I can try.

0 ·

Braydn T SudheerReddy commented · Dec 16, 2019 at 02:49 PM

Here is some info on the first fit algorithmn: https://www.geeksforgeeks.org/program-first-fit-algorithm-memory-management/

0 ·

Benjamin W2 Braydn T commented · Dec 20, 2019 at 06:02 PM

Hi @Sudheer R,

Was Braydn's answer helpful for you? If so, please click the accept button. If not, how else can we help?

0 ·

SudheerReddy Benjamin W2 commented · Dec 20, 2019 at 09:09 PM

@Benjamin W2

I am still trying first fit algorithm. If possible could you please update any sample model having first fit algorithm. It really helps me.

0 ·

Answer 1 · 2019-12-26T18:00:28Z

tannerp answered Dec 26, '19 tannerp commented Jan 2, '20

Hi @Sudheer R,

Here's an example where I used the first fit algorithm to fill queues. All of the custom code can be found in the Custom Code activity in Process Flow. Hopefully this helps give you an example of what you can do in your model. Your model was incomplete, so I wasn't sure exactly the route you wanted to go with this, but this code should get you started.

The idea is that each queue has a valueSum label that adds the values on each of the items in the queue and should be equal to 9.

binpacking.fsm

binpacking.fsm (32.4 KiB)

· 2

SudheerReddy commented · Jan 02, 2020 at 01:18 PM

@tanner.p

In below shown image for pulledItem it is showing as Queue8/Box1 but for pulled it is showing as Internal Type. I would like to see what is the content of pulled instead of Internal Type. I am trying to find in Tree Structure what is pulled content. Where to find this in Tree Structure

Following is the Tree Structure I am looking for pulled. Where to find in Tree Structure.

0 ·

internaltype.jpg (27.2 KiB)

pulled.jpg (163.3 KiB)

tannerp SudheerReddy commented · Jan 02, 2020 at 04:49 PM

@Sudheer R,

That "pulled" value that you've found isn't necessary and is just a local duplicate of "pulledItem". I wouldn't worry about it. I deleted that part of the code and the model still functions.

24476-binpacking-3.fsm

0 ·

24476-binpacking-3.fsm (32.0 KiB)

question