AN APPROXIMATION SCHEME FOR SCHEDULING INDEPENDENT JOBS INTO SUBCUBESOF A HYPERCUBE OF FIXED DIMENSION

We study the problem of scheduling independent jobs in a hypercube whe re jobs are executed in subcubes of various dimensions. The problem be ing NP-complete, several approximation algorithms based on list schedu ling have been proposed, having approximation ratio of order of 2. Ln this paper, a linear time E-approximation algorithm for the problem is provided when the size of the hypercube is fixed. We use a reduction to a special strip-packing (or two-dimensional packing) problem with b ounded number of distinct pieces. Then, we transform the ship-packing solution into a feasible one for the initial scheduling problem with a small loss in performance. Finally, we provide an improvement which l eads to significant reduction of the size of the strip-packing problem .