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.
展开▼
机译：研究了在m维超立方体系统上调度n个独立作业以最小化完成时间的问题。每个作业J / sub i /，其中1> or = i> or = n，都与维度d / sub i /和处理时间t / sub i /相关联，这意味着J / sub i /需要ad / sub t / sub i /时间单位的i /维子多维数据集。如果允许作业抢占，则O（n / sup 2 / log / sup 2 / n）时间算法可以生成最多具有min（n-2,2 / sup m / -1）个抢占的最小完成时间计划。获得。如果不允许工作抢占，则问题是NP完成。结果表明，一种称为LDF的简单列表调度算法可以渐近最优地执行，并且绝对界限不小于2-1 / 2 / sup m /。对于绝对边界，还显示出对于包括LDF的一类调度算法，存在一个下界（1+平方根6）/ 2大约= 1.7247。
展开▼
