Job scheduling in a partitionable mesh using a two-dimensionalbuddy system partitioning scheme |
| |
Authors: | Li K Cheng K-H |
| |
Affiliation: | Dept. of Math. & Comput. Sci., State Univ. of New York, New Paltz, NY; |
| |
Abstract: | The job scheduling problem in a partitionable mesh-connected system in which jobs require square meshes and the system is a square mesh whose size is a power of two is discussed. A heuristic algorithm of time complexity O(n(log n+log p)), in which n is the number of jobs to be scheduled and p is the size of the system is presented. The algorithm adopts the largest-job-first scheduling policy and uses a two-dimensional buddy system as the system partitioning scheme. It is shown that, in the worst case, the algorithm produces a schedule four times longer than an optimal schedule, and, on the average, schedules generated by the algorithm are twice as long as optimal schedules |
| |
Keywords: | |
|
|