Scheduling on Uniform Nonsimultaneous Parallel Machines

We consider the problem of scheduling on uniform processors which may not start processing at the same time with the purpose of minimizing the maximum completion time. We provide a variant of the MULTIFIT algorithm which generates schedules which end within 1.382 times the optimal maximum completion time for the general problem, and withinv root 6/2 times the optimal maximum completion time for problem instances with two processors. Experimental results suggest that our algorithm is a viable option for addressing this problem in practice.