The paper examines one of the basic, well studied problems of scheduling theory, that of nonpreemptive assignment of independent tasks on m parallel processors with the objective of minimizing the makespan. Because this problem is NP-complete and apparently intractable in general, much effort has been directed toward devising fast algorithms which find near optimal schedules. Two well-known heuristic algorithms LPT (largest processing time first) and MULTIFIT, shortly MF, find schedules having makespans within 4/3, 13/11, respectively, of the minimum possible makespan, when the m parallel processors are identical. If they are uniform, then the best worst-case performance ratio bounds that are known are 1.583, 1.40, respectively. In this paper the bound to 1.382 for MF algorithm for the uniform-processor system is tightened. On the basis of some of the present general results and other investigations, it is conjectured that the bound could be tightened further to 1.366.
