Optimal static load balancing of multi-class jobs in a distributed computer system model is considered. This model is an extension of the Tantawi and Towsley single job class model to a multiple job class model. Some properties of the optimal solution are shown. On the basis of these properties, a straight-forward and efficient algorithm optimal load balancing of multi-class jobs is derived. We compare the performance of our algorithm and two other well known algorithms for multi-class jobs, the flow deviation algorithm and the Dafermos algorithm. Our algorithm and the flow deviation algorithm both require a comparable amount of storage that is far less than that required by the Dafermos algorithm. In the results of numerical experiments our algorithm and the Dafermos algorithm required mutually comparable computation times for obtaining the optimal solution which were far less than that of the flow deviation algorithm.

The effects of changing system parameters on job scheduling policies are studied for load balancing of multi-class jobs in a distributed computer system that consists of heterogeneous host computers connected by a single-channel communications network. A job scheduling policy decides which host should process the arriving jobs. We consider two job scheduling policies. The one is the overall optimal policy whereby jobs are scheduled so as to minimize the overall mean job response time. Tantawi and Towsley obtained the algorithm that gives the solution of the policy in the single class job environment and Kim and Kameda extended it to the multiple job class environment. The other is the individually optimal policy whereby jobs are scheduled so that every job may feel that its own expected response time is minimized. We can consider three important system parameters in a distributed computer system: the communication time of the network, the processing capacity of each node, and the job arrival rate of each node. We examine the effects of these three parameters on the two load balancing policies by numerical experiment.