Article ID: | iaor20072280 |
Country: | Netherlands |
Volume: | 13 |
Issue: | 1 |
Start Page Number: | 33 |
End Page Number: | 45 |
Publication Date: | Jan 2007 |
Journal: | Journal of Combinatorial Optimization |
Authors: | Chen Jianer, Huang Jingui, Chen Songqiao, Wang Jianxin |
Multiprocessor job scheduling problem has become increasingly interesting, for both theoretical study and practical applications. Theoretical study of the problem has made significant progress recently, which, however, seems not to imply practical algorithms for the problem, yet. Practical algorithms have been developed only for systems with three processors and the techniques seem difficult to extend to systems with more than three processors. This paper offers new observations and introduces new techniques for the multiprocessor job scheduling problem on systems with four processors. A very simple and practical linear time approximation algorithm of ratio bounded by 1.5 is developed for the multi-processor job scheduling problem