I want to implement some algorithms for the basic load balancing problem (also known as multiprocessor scheduling problem), where the input is a set of n independent jobs J={j1,j2,j3...,jn} and a number m of identical machines. The goal is to find an assignment of jobs to machines that minimizes the execution time of the most loaded machine. I would like to use a standard set of instances in order to compute the experimental approximation factor delivered by some algorithms.
Have you tried making a tight example? That is, an infinite set of instances that hit your approximation factor yet?
I am working on the makespan problem on unrelated parallel machines these days, so I can suggest some ideas as your problem is very related to this (not the same though). If experimental and not formal results are wanted, one thing I can suggest is just generating permutations of a schedule you know will have an optimal load you know (say m). A big thing to deal with in a scheduling problem is what order jobs are processed. For example, the classic list scheduling algorithm by Graham does some pretty nasty things if you force it to pick bad choices then try to squeeze a job on a machine that is already balanced. That's how you get the tight example.
One thing I can suggest is looking at your algorithm, and the properties it has, and prove it has a certain approximation factor based on the characteristics of your algorithm. Usually knowing the approximation factor typically requires finding the flaws in the algorithm by finding a provably good bound you know about the scheduling problem.
But yes, for experimental results, try permuting a set of jobs where about half are even, half are odd. Usually even and odd job lengths (with difference greater than 2) can do funky things to a schedule sometimes. I can't suggest any standard instances beyond what I said, as I usually go about this formally, since an approximation factor is something somebody can prove usually.
Hope this helps!
- Badges
- Science topic
- Similar topics
- Computer Science