Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints
Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints
复制标题
DOI：
10.1287/opre.2021.2198
复制
发表时间：
2020-04
期刊：
影响因子：
--
通讯作者：
Mehrnoosh Shafiee;Javad Ghaderi
中科院分区：
文献类型：
--
作者：
Mehrnoosh Shafiee;Javad Ghaderi
现代并行计算框架（例如 Hadoop 和 Spark）中的作业受到多种限制。在这些框架中，数据通常分布在机器集群中，并分多个阶段进行处理。因此，属于同一阶段（作业）的任务具有由集合中最慢的任务确定的集体完成时间。此外，任务的处理时间取决于机器，每台机器能够根据其容量一次处理多个任务。 Mehrnoosh Shafiee 和 Javad Ghaderi 所著的《调度受打包和放置约束的并行任务作业》一文中，提供了具有理论保证的多种近似算法来解决抢占式和非抢占式场景下的问题。使用真实交通轨迹的数值结果表明，该算法比以前的方法产生了显着的收益。
Jobs in modern parallel-computing frameworks, such as Hadoop and Spark, are subject to several constraints. In these frameworks, the data are typically distributed across a cluster of machines and is processed in multiple stages. Therefore, tasks that belong to the same stage (job) have a collective completion time that is determined by the slowest task in the collection. Furthermore, a task’s processing time is machine dependent, and each machine is capable of processing multiple tasks at a time subject to its capacity. In “Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints,” by Mehrnoosh Shafiee and Javad Ghaderi, multiple approximation algorithms with theoretical guarantees are provided to solve the problem under preemptive and nonpreemptive scenarios. The numerical results, using a real traffic trace, demonstrate that the algorithms yield significant gains over the prior approaches.