A simple linear-time approximation algorithm for multi-processor job scheduling on four processors Conference Paper uri icon

abstract

  • Springer-Verlag Berlin Heidelberg 2000. 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 in- troduces 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 P4|fix|Cmax, which significantly improves previous results. Our techniques are also useful for multiprocessor job scheduling problems on systems with more than four processors.

name of conference

  • Algorithms and Computation, 11th International Conference, ISAAC 2000, Taipei, Taiwan, December 18-20, 2000, Proceedings

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Huang, J., Chen, J., & Chen, S.

complete list of authors

  • Huang, J||Chen, J||Chen, S

publication date

  • January 2000