English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Distributed computing systems often need to consider the scheduling probleminvolving a collection of highly dependent data-processing tasks that must workin concert to achieve mission-critical objectives. This paper considers theunrelated machine scheduling problem for minimizing weighted sum completiontime under arbitrary precedence constraints and on heterogeneous machines withdifferent processing speeds. The problem is known to be strongly NP-hard evenin the single machine setting. By making use of Queyranne's constraint set andconstructing a novel Linear Programming relaxation for the scheduling problemunder arbitrary precedence constraints, our results in this paper advance thestate of the art. We develop a $2(1+(m-1)/D)$-approximation algorithm (and$2(1+(m-1)/D)+1$-approximation) for the scheduling problem with zero releasetime (and arbitrary release time), where $m$ is the number of servers and $D$is the task-skewness product. The algorithm can be efficiently computed inpolynomial time using the Ellipsoid method and achieves nearly optimalperformance in practice as $D>O(m)$ when the number of tasks per job toschedule is sufficiently larger than the number of machines available. Ourimplementation and evaluation using a heterogeneous testbed and real-worldbenchmarks confirms significant improvement in weighted sum completion time fordependent computing tasks.

On the Approximability of Related Machine Scheduling under Arbitrary Precedence