Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


simon
Posts:
2
Registered:
5/14/12


Load balancing and combinatorial optimization (approximation algorithms and heuristics)
Posted:
May 13, 2012 9:00 PM


Hi guys,
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/dropped.
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.
However, I only need a suboptimal solution for the load balancing. So I turned to approximation algorithms and heuristics to solve the problem faster.
I've seen the "Multiple Knapsack" problem,unfortunately the cost functions do not support balancing. But if there was....... it would be great because the rest would fit in to the problem.
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.
I was basically trying to find some platform/problem formulation so that I could use the algorithms defined in the literature for it!
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.
Thanks very much for your time! ;)
Simon



