On job scheduling on a hypercube

Abstract

The problem of scheduling n independent jobs on an m-dimensional hypercube system to minimize the finish time is studied. Each job J/sub i/, where 1<or=i<or=n, is associated with a dimension d/sub i/ and a processing time t/sub i/, meaning that J/sub i/ needs a d/sub i/-dimensional subcube for t/sub i/ units of time. When job preemption is allowed, an O(n/sup 2/ log/sup 2/ n) time algorithm which can generate a minimum finish time schedule with at most min(n-2,2/sup m/-1) preemptions is obtained. When job preemption is not allowed, the problem is NP-complete. It is shown that a simple list scheduling algorithm called LDF can perform asymptotically optimally and has an absolute bound no worse than 2-1/2/sup m/. For the absolute bound, it is also shown that there is a lower bound (1+ square root 6)/2 approximately=1.7247 for a class of scheduling algorithms including LDF.<<ETX>>