Approximation Algorithms on Multiprocessor Task Scheduling

Multiprocessor task scheduling problem has become increasingly interesting, for both theoretical study and practical applications. Theoretical study of the problem has made significant progress recently. However, it seems not to imply practical algorithms for the problem yet. In this paper, the offline version of the Multiprocessor scheduling problem on m-processor system is discussed for the case of not only the unit process time tasks but also the arbitrary processing time tasks. Some approximation algorithms are proposed by using the Split Scheduling, the First Fit and the Large Width First techniques. The approximation ratios here are better than the best results existed in the current literature.