论文标题
流式近似方案，以最大程度地减少并行机器的总完成时间
Streaming Approximation Scheme for Minimizing Total Completion Time on Parallel Machines Subject to Varying Processing Capacity
论文作者
论文摘要
我们研究了在处理能力不同的并行机器上最小化总完成时间的问题。在本文中，我们为数据流模型下的问题开发了一个近似方案，其中输入数据庞大，无法适应内存，因此只能扫描几次。我们的算法可以在一个通过中计算最佳总完成时间的近似值，并以两次通过的近似值输出时间表。
We study the problem of minimizing total completion time on parallel machines subject to varying processing capacity. In this paper, we develop an approximation scheme for the problem under the data stream model where the input data is massive and cannot fit into memory and thus can only be scanned for a few passes. Our algorithm can compute the approximate value of the optimal total completion time in one pass and output the schedule with the approximate value in two passes.
