Computing optimal preemptive schedules for parallel tasks: linear programming approaches
Computing optimal preemptive schedules for parallel tasks: linear programming approaches
复制标题
计算并行任务的最佳抢占式调度：线性编程方法
DOI：
10.1007/s10107-002-0361-7
复制
发表时间：
2003
影响因子：
2.7
通讯作者：
Lorant Porkolab
中科院分区：
文献类型：
--
作者：
K. Jansen;Lorant Porkolab
摘要。基于线性编程公式，我们提出了一种以最小化的算法来计算preemptive的算法，并表明算法的运行时间在多个方面取决于M。可以在O（n）时间内计算。
Abstract. We study the problem of scheduling a set of n independent parallel tasks on m processors, where in addition to the processing time there is a size associated with each task indicating that the task can be processed on any subset of processors of the given size. Based on a linear programming formulation, we propose an algorithm for computing a preemptive schedule with minimum makespan, and show that the running time of the algorithm depends polynomially on m and only linearly on n. Thus for any fixed m, an optimal preemptive schedule can be computed in O(n) time. We also present extensions of this approach to other (more general) scheduling problems with malleable tasks, due dates and maximum lateness minimization.