The assignment problem can be exactly solved in cubic time by the Hungarian method
(aka the Kuhn-Munkres
algorithm), no need for approximation or brute force. There's implementations floating around all over the internet. (Even I wrote one --- http://www.cs.princeton.edu/~ken/hungar ... hod.tar.gz
--- as an errata supplement for a book on combinatorial optimization.)
On the other hand, I've never looked for an approximation algorithm for it. Maybe there's a sub-cubic time one?(edit)
... I think I saw "assignment problem" in your thread title and saw the basic processor/task structure you have, and I assumed you were talking about an approximation algorithm for the assignment problem. Whereas, it seems your problem is only superficially similar to the assignment problem.
Perhaps an idea: Let A be the sum of your "processor powers", and let B be the sum of your task work-amounts. For each processor i, let the "ratios of work" be r_i = ( a_i / A ) * B. This does not reduce your problem to the assignment problem, at least not outright. Your problem makes me think of bin-packing, but I'm only familiar with bin-packing where the bin size is fixed and the number of bins is to be minimized, versus here, where the "bin size" r_i is variable and the number of "bins" n is fixed.(/edit)