Math Forum Discussions

simon

Posts: 2
Registered: 5/14/12

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

Plain Text

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 sub-optimal 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