AN EFFICIENT JOB SCHEDULING ALGORITHM IN PARTITIONABLE MESH CONNECTED SYSTEMS
Keqin Li · International Journal of Foundations of Computer Science · 2001
In this paper, we consider the problem of scheduling independent jobs in partitionable mesh connected systems. The problem is NP-hard, since it includes the multiprocessor scheduling problem as a special case when all jobs request for one processor. We analyze a simple approximation algorithm called A m. In particular, we show that if the sizes of submeshes requested by jobs are independent and identically distributed (i.i.d.) random variables uniformly distributed in the range [1..M1]×[1..M2], where M1×M2 is the size of a partitionable mesh connected system, and task execution times are i.i.d. random variables with finite mean and variance, then the average-case performance ratio E( A m(L))/E( OPT (L)) is asymptotically bounded from above by 1.6637594…. The average-case performance ratio improves significantly when jobs request for square submeshes or small submeshes.