Job scheduling in a distributed system

This thesis studies the scheduling of jobs in a distributed computer system. This problem differs from the classical computer scheduling problem because the entire scheduling problem is not known at any point and neither does the scheduling processor have complete knowledge of the system state. Both of these differences result from the distributed nature of the computer system. Because of these constraints it is not possible to use classical optimal scheduling theory. Because of the need to compare the performance of a distributed scheduling heuristic with optimal and non-optimal centralized scheduling algorithms a new nonrelative bound for all list schedules is developed. Using this new bound, the performance distribution of random list schedules is then studied. This is the first time the author is aware of the distribution of list schedule performance being studied. Classical centralized scheduling theory is then extended to distributed scheduling theory. The difference between a centralized algorithm and a distributed algorithm is discussed. The distributed scheduling problem is presented and the reasons requiring a distributed algorithm are discussed. With this as background the performance distribution of a simple network scheduling heuristic is studied. Finally, the effect of network delay on scheduling performance is studied, centralized and network scheduling performance is compared, and the direction of future work is indicated.