Semi-normal schedulings: Improvement on Goemans' algorithm Conference Paper uri icon

abstract

  • Theoretical study of the multiprocessor job scheduling problem has made significant progress recently, which, however, seems not yet to imply practical algorithms. This paper offers new observations and introduces new techniques for the multiprocessor job scheduling problem P3|fix|C max. The concept of semi-normal schedulings is introduced and a very simple linear time algorithm for constructing semi-normal schedulings is developed. Thorough analysis is provided in the study of semi-normal schedulings, which enables us to conclude that the proposed algorithm is an approximation algorithm of ratio 9/8 for the P3|fix|C max problem. This improves the previous best (practical) ratio 7/6 by Goemans. Our techniques are also useful for multiprocessor job scheduling problems on systems with more than three processors. 2001 Springer Berlin Heidelberg.

name of conference

  • Algorithms and Computation, 12th International Symposium, ISAAC 2001, Christchurch, New Zealand, December 19-21, 2001, Proceedings

published proceedings

  • ALGORITHMS AND COMPUTATION, PROCEEDINGS

author list (cited authors)

  • Chen, J., & Huang, J. G.

citation count

  • 5

complete list of authors

  • Chen, J||Huang, JG

publication date

  • December 2001