On job scheduling on a hypercube

The problem of scheduling n independent jobs on an m -dimensional hypercube system to minimize the finish time is studied. Each job J_i, where 1⩽i⩽n, is associated with a dimension d _i and a processing time t_i, meaning that J_i needs a d_i-dimensional subcube for t_i units of time. When job preemption is allowed, an O(n² log² n) time algorithm which can generate a minimum finish time schedule with at most min{n-2,2^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^m. For the absolute bound, it is also shown that there is a lower bound (1+√6)/2≈1.7247 for a class of scheduling algorithms including LDF