An approximation scheme for scheduling independent jobs into subcubes of a hypercube of fixed dimension

✍ Scribed by Y. Kopidakis; V. Zissimopoulos

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 518 KB
• Volume: 178
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(96)00282-4

✦ Synopsis

We study the problem of scheduling independent jobs in a hypercube where jobs are executed in subcubes of various dimensions. The problem being NP-complete, several approximation algorithms based on list scheduling have been proposed, having approximation ratio of order of 2. In this paper, a linear time &-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 bounded number of distinct pieces. Then, we transform the strip-packing solution into a feasible one for the initial scheduling problem with a small loss in performance. Finally, we provide an improvement which leads to significant reduction of the size of the strip-packing problem.