论文标题
通过共享处理的多任务调度的流算法
Streaming Algorithms for Multitasking Scheduling with Shared Processing
论文作者
论文摘要
在本文中，我们设计了第一个流媒体算法，以解决具有共享处理的并行机上多任务调度的问题。在一个通过中，我们的流近似方案可以提供最佳makepan的近似值。如果可以通过两次通过读取作业，则算法可以找到具有近似值的时间表。这项工作不仅为研究问题提供了算法的大数据解决方案，而且还可以深入了解调度领域其他问题的流算法设计。
In this paper, we design the first streaming algorithms for the problem of multitasking scheduling on parallel machines with shared processing. In one pass, our streaming approximation schemes can provide an approximate value of the optimal makespan. If the jobs can be read in two passes, the algorithm can find the schedule with the approximate value. This work not only provides an algorithmic big data solution for the studied problem, but also gives an insight into the design of streaming algorithms for other problems in the area of scheduling.
