A variant of job assignment (scheduling) problem with variable time span
I searched for "job shop scheduling uncertain processing times" and came up with this: http://www.waset.org/journals/waset/v64/v64-190.pdf.  I hope it helps.

I think you will find that the best approximation algorithm is going to depend on the probability distribution of completion times.  An algorithm for exponentially distributed times might be very different than an algorithm for a uniform distribution.

I think you will also need to trade off expected completion time vs. variance.  With known completion times a decent approximation algorithm is Coffman's list scheduling algorithm: sort the jobs by length (longest to shortest) and then schedule greedily (next job starts as soon as a machine is free.)  With uniform completion times you might try sorting by best-case completion times, expected completion times or worst-case completion times, and you would be getting different answers.