通过线性规划进行无关并行处理器的抢占式调度

研究表明，某些无关并行处理器的最优抢占式调度问题可以被表述为线性规划问题。作为这些问题线性规划公式的副产品，获得了最优调度所需的抢占次数的上界。特别是，证明了为了在 m 个无关处理器上调度 n 个作业而最小化完工时间，所需的抢占次数不超过 O(m²)。