Preemptive scheduling of independent jobs on a hypercube (Q1111373)

We consider the problem of scheduling n independent jobs on an m- dimensional hypercube system to minimize the finishing time, where each job \(J_ i\) is associated with a dimension \(d_ i\) and a processing time \(t_ i\), meaning that \(J_ i\) requires a \(d_ i\)-dimensional subcube for \(t_ i\) units of time. An \(O(n^ 2)\) algorithm is presented that decides if all n jobs can be finished by a given deadline T. Using this algorithm, one may obtain a minimum-finishing-time schedule in polynomial time.