Answers to: Load Balancing between Bins (heuristic or approximation algorithm)?http://www.or-exchange.com/questions/5411/load-balancing-between-bins-heuristic-or-approximation-algorithm<p>Hi guys,</p>
<p>so I'm working on balancing load between bins. Each Bin has a finite size, the problem only has a limited number of bins available(i.e. consider only N bins). The load is divided in units of load, you can consider them as jobs that have a finite size as well, and these will be allocated to the bins. If by any chance the bins are all full, then some of the jobs will be blocked/droppped.Also the jobs all have the same size. It is like a "generalized assignment problem" but with load balancing.</p>
<p>Thus, this is a combinatorial 0-1 problem.</p>
<p>This is also a medium scale problem.I had a MIQP solution/formulation for this and I was going to solve it like that (with branch and bound), but the size (numberBINS*numberjobs) and the constraints require to much time to find an optimal solution.</p>
<p>However, I only need a sub-optimal solution for the load balancing. So I turned to approximation algorithms and heuristics to solve the problem faster. </p>
<p>I've seen the "Multiple Knapsack" problem,unfortunatly the cost functions do not support balancing. But if there was....... it would be great because the rest would fit in to the problem.</p>
<p>Then I turned to the "job shop / minimize makespan" problem,Generalized Load Balancing with finite buffers (i.e. Flow shops with parallel machines and Finite buffers). But did not find anything relevant still. I tried to use this problem because it does load balancing between T machines and Z jobs. Thus, I was trying to adapt this to my problem, since there is no scheduling or time restrictions. The issue comes when the buffer has to be finite. </p>
<p>I was basically trying to find some platform/problem formulation so that I could use the algorithms defined in the literature for it!</p>
<p>So if you guys know some work already done that fits my problem, or some tips to solve this would be great. I've spent some time know with this and I do not really know if there is some work done in this, also because I'm confused a little bit.</p>
<p>I really hope some of you can help me with this.</p>
<p>Thanks very much for your time! ;)</p>enTue, 15 May 2012 03:39:15 -0400Comment by Geoffrey De Smet on Geoffrey De Smet's answerhttp://www.or-exchange.com/questions/5411/load-balancing-between-bins-heuristic-or-approximation-algorithm#5422<p>Ant Colony implementation is on Drools Planner's long term todo list.</p>
<p>We welcome contributions (github pull requests), so if you feel like implementing Ant Colony (so you can compare it with Tabu Search and Sim Ann with the Planner benchmarker):
A prototype implementation should not be hard to implement, because it can copy <a href="https://github.com/droolsjbpm/drools-planner/blob/master/drools-planner-core/src/main/java/org/drools/planner/core/localsearch">DefaultLocalSearchSolverPhase</a> and reuse the classes <code>Termination</code>, <code>Move</code>, <code>MoveSelector</code>, ... and be phased after a construction heuristic.</p>Geoffrey De SmetTue, 15 May 2012 03:39:15 -0400http://www.or-exchange.com/questions/5411/load-balancing-between-bins-heuristic-or-approximation-algorithm#5422Comment by Simon on Geoffrey De Smet's answerhttp://www.or-exchange.com/questions/5411/load-balancing-between-bins-heuristic-or-approximation-algorithm#5419<p>I've seen the references I think I'm going to try that. Inicially I was going to try ant colony. But after readung about it and seeing your work on Cloud Balance seems the righ way to do it.</p>
<p>Also, I usually have about 150/30 (machines/jobs), so this might work well. Let's see...</p>
<p>Thanks man...</p>SimonMon, 14 May 2012 19:43:55 -0400http://www.or-exchange.com/questions/5411/load-balancing-between-bins-heuristic-or-approximation-algorithm#5419Answer by Geoffrey De Smethttp://www.or-exchange.com/questions/5411/load-balancing-between-bins-heuristic-or-approximation-algorithm/5412<p>I've done 2 load balancing examples with such a bin packing problem:</p>
<ul>
<li>Cloud balance (<a href="http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html_single/index.html#cloudBalancingTutorial">tutorial</a>, <a href="http://vimeo.com/25902052">video</a>, <a href="http://docs.jboss.org/drools/blog/2012-05-13/index.html">benchmark report</a>)</li>
<li>Machine reassignment Google roadef 2012 (<a href="http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html_single/index.html#machineReassignment">docs</a>)</li>
</ul>
<p>In my experience, the approximation algorithm construction heuristic <strong><em>First Fit Decreasing</em></strong> works ok. But it can improve a lot to suffix it with a few milliseconds or seconds of <em>Tabu Search</em>.</p>Geoffrey De SmetMon, 14 May 2012 04:04:20 -0400http://www.or-exchange.com/questions/5411/load-balancing-between-bins-heuristic-or-approximation-algorithm/5412