| Schedulers play an important role in the overall performance of computer systems. The theoretical results presented in this thesis are steps towards developing distributed schedulers for distributed computer systems. Two objective functions we studied; namely minimizing the Weighted-Mean-Finish-Time (WMFT) and maximizing the exponential payoff (EP), where exponential payoff is the sum of the job payoffs and each job's payoff is a decreasing exponential function of the job's finish time.;There are known optimal solutions with O(nlogn) time complexity for these objective functions in the uniprocessor case. But for more than one processor the WMFT problem is known to be NP-hard and the proof of the NP-hardness of the EP problem is presented in this thesis. So an algorithm with a reasonable relative error bound could be an acceptable solution for the problem.;Two simple list scheduling algorithms, wth time complexities of O(nlogn), are presented for the WMFT (with .309 relative error bound) and the EP problem (with .269 relative error bound ), for centralized scheduling and definite job execution times. Then it is shown that these algorithms, with slight modifications, will have the same performance when the jobs have random execution times and we want to optimize the expected values of the objective functions. The next step toward our goal was to present two dynamic scheduling policies based on the developed algorithms, considering both non-preemptive schedules, and a certain level of preemption We are interested in a dynamic scheduling policy, since, especially when the system is overloaded (because of failure of components or receiving too many requests), a static policy is incapable of efficient scheduling. Finally, to demonstrate how these algorithms could be utilized in a distributed schedule for a distributed computer system, a distributed scheduler is proposed. This schedule could also be used as a base for evaluating other heuristics, when one study the effect of other parameters in the system which justify considering distributed schedulers such as; communication time, scheduling time, and reliability. |
