Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width
Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width
复制标题
DOI：
10.1007/s10878-012-9498-3
复制
发表时间：
2012-05
影响因子：
1
通讯作者：
Elisabeth Günther;F. König;Nicole Megow
中科院分区：
文献类型：
--
作者：
Elisabeth Günther;F. König;Nicole Megow
本文研究了具有优先约束的可延展并行任务的非抢占式排序和包装问题，以最小化完工时间。在调度变量中，我们允许自由选择处理器;在打包中，每个任务必须分配给一个连续的子集。可延展任务可以在不同数量的处理器上处理，处理时间不同，而并行任务需要固定数量的处理器，对于有界宽度的优先约束，我们解决了任意处理器数量和任意宽度界的问题的复杂性状态.我们提出了一个基于Dilworth的分解定理的NP-难问题的变种，并为所有剩余的特殊情况下精确有效的算法的FPTAS。对于我们的积极的结果，我们不需要其他常见的单调惩罚假设的可塑性任务的处理时间，而我们的硬度结果举行，即使假设这种限制。我们补充我们的结果表明，这些问题都是强NP-困难的优先约束下，形成一棵树。
We study the problems of non-preemptively scheduling and packing malleable and parallel tasks with precedence constraints to minimize the makespan. In the scheduling variant, we allow the free choice of processors; in packing, each task must be assigned to a contiguous subset. Malleable tasks can be processed on different numbers of processors with varying processing times, while parallel tasks require a fixed number of processors.For precedence constraints of bounded width, we resolve the complexity status of the problem with any number of processors and any width bound. We present an FPTAS based on Dilworth’s decomposition theorem for the NP-hard problem variants, and exact efficient algorithms for all remaining special cases. For our positive results, we do not require the otherwise common monotonous penalty assumption on the processing times of malleable tasks, whereas our hardness results hold even when assuming this restriction. We complement our results by showing that these problems are all strongly NP-hard under precedence constraints which form a tree.