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
![]() |
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: |
| ||||||
ORCID: |
| ||||||
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