SCHEDULiNG PROBLEMS ON UNIFORM MACHINE AND PARALLEL MACHINE

The thesis consists of three chapters. The first introduces some background information. The main result obtained on scheduling are put into two separated parts, namely Chapter 2 and Chapter 3.We investigate the problem of on-line scheduling jobs on the case of uniform machines, namely, the speeds of the m machines are s1,s2,?..,~,. and Sm .In part one(Chapter 2), LS algorithm for the case of is analyzed. We derived a tight bound on the worst-case performance ,namely. In part two(Chapter 3), an effective algorithm for the case of problem is provided. We conclude that its performance is.