The price of multi-organization constraint in unrelated parallel machine scheduling
The price of multi-organization constraint in unrelated parallel machine scheduling
复制标题
不相关并行机调度中多组织约束的代价
DOI：
10.1142/s0129626412500065
复制
发表时间：
2012
影响因子：
0.4
通讯作者：
Taisuke Izumi
中科院分区：
文献类型：
--
作者：
Fukuhito Oosita;Tomoko Izumi;Taisuke Izumi
我们考虑并行计算环境，其中 m 个组织提供机器和多个要执行的作业。虽然需要组织之间的合作来最大限度地缩短全球完工时间，但每个组织也主要希望更快地完成自己的工作，因此不一定是合作的。为了处理这种情况，我们提出了α-合作多组织调度问题（α-MOSP），其中α≥1是代表合作程度的参数。 α-MOSP在多组织约束下最小化完工时间，即每个组织不允许自己的作业完成时间比自己执行作业的情况延迟α倍。首先，我们揭示了完工时间与合作程度之间的关系。我们表明，当 α = 1 时，多组织约束可能会使最佳完工时间降低 m 倍，而当 α > 1 时，退化比率受到 α/(α - 1) 的限制。这意味着弱合作会显着提高完工时间。其次，我们研究了α-MOSP的复杂性。我们展示了它的强 NP 硬度和近似因子小于 max{(α + 1)/α, 3/2} 的不可近似性。我们还展示了从无多组织约束下的最优调度到 α-MOSP 的最优调度的转换难度。这个结果证明了保留近似比的通用多项式时间变换算法不存在。
We consider the parallel computing environment where m organizations provide machines and several jobs to be executed. While cooperation of organizations is required to minimize the global makespan, each organization also expects the faster completion of its own jobs primarily and thus it is not necessarily cooperative. To handle the situations, we formulate the α-cooperative multi-organization scheduling problem (α-MOSP), where α ≥ 1 is a parameter representing the degree of cooperativeness. α-MOSP minimizes the makespan under the multi-organization constraint that each organization does not allow the completion time of its own jobs to be delayed α times of that in the case where those jobs are executed by itself.First, we reveal the relation between the makespan and the degree of cooperativeness. We show that the multi-organization constraint may degrade the optimal makespan by m times for α = 1, while the degradation ratio is bounded by α/(α - 1) for α > 1. This implies that weak cooperation improves the makespan dramatically. Second, we study the complexity of α-MOSP. We show its strongly NP-hardness and inapproximability for the approximation factor less than max{(α + 1)/α, 3/2}. We also show the hardness of transformation from an optimal schedule under no multi-organization constraint to an optimal schedule for α-MOSP. This result is a witness for inexistence of a general polynomial-time transformation algorithm that preserves the approximation ratio.