CaltechAUTHORS
  A Caltech Library Service

Communication-Aware Scheduling of Precedence-Constrained Tasks on Related Machines

Su, Yu and Ren, Xiaoqi and Vardi, Shai and Wierman, Adam (2020) Communication-Aware Scheduling of Precedence-Constrained Tasks on Related Machines. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20200526-151456655

[img] PDF - Submitted Version
See Usage Policy.

673kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200526-151456655

Abstract

Scheduling precedence-constrained tasks is a classical problem that has been studied for more than fifty years. However, little progress has been made in the setting where there are communication delays between tasks. Results for the case of identical machines were derived nearly thirty years ago, and yet no results for related machines have followed. In this work, we propose a new scheduler, Generalized Earliest Time First (GETF), and provide the first provable, worst-case approximation guarantees for the goals of minimizing both the makespan and total weighted completion time of tasks with precedence constraints on related machines with machine-dependent communication times.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/2004.14639arXivDiscussion Paper
ORCID:
AuthorORCID
Ren, Xiaoqi0000-0002-1121-9046
DOI:10.48550/arXiv.2004.14639
Record Number:CaltechAUTHORS:20200526-151456655
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200526-151456655
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:103474
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:26 May 2020 22:24
Last Modified:02 Jun 2023 01:05

Repository Staff Only: item control page