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/droppped.Also the jobs all have the same size. It is like a "generalized assignment problem" but with load balancing.

Thus, this is a combinatorial 0-1 problem.

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,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.

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, also because I'm confused a little bit.

I really hope some of you can help me with this.

Thanks very much for your time! ;)

This question is marked "community wiki".

asked 13 May '12, 20:21

Simon's gravatar image

Simon
112
accept rate: 0%


I've done 2 load balancing examples with such a bin packing problem:

In my experience, the approximation algorithm construction heuristic First Fit Decreasing works ok. But it can improve a lot to suffix it with a few milliseconds or seconds of Tabu Search.

link

answered 14 May '12, 04:04

Geoffrey%20De%20Smet's gravatar image

Geoffrey De ... ♦
3.6k32764
accept rate: 6%

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.

Also, I usually have about 150/30 (machines/jobs), so this might work well. Let's see...

Thanks man...

(14 May '12, 19:43) Simon

Ant Colony implementation is on Drools Planner's long term todo list.

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 DefaultLocalSearchSolverPhase and reuse the classes Termination, Move, MoveSelector, ... and be phased after a construction heuristic.

(15 May '12, 03:39) Geoffrey De ... ♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×28
×13
×6
×2
×1

Asked: 13 May '12, 20:21

Seen: 3,004 times

Last updated: 15 May '12, 03:39

OR-Exchange! Your site for questions, answers, and announcements about operations research.