License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.98
URN: urn:nbn:de:0030-drops-181502
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18150/
Rajaraman, Rajmohan ;
Stalfa, David ;
Yang, Sheng
Scheduling Under Non-Uniform Job and Machine Delays
Abstract
We study the problem of scheduling precedence-constrained jobs on heterogenous machines in the presence of non-uniform job and machine communication delays. We are given a set of n unit size precedence-ordered jobs, and a set of m related machines each with size m_i (machine i can execute at most m_i jobs at any time). Each machine i has an associated in-delay ρ^{in}_i and out-delay ρ^{out}_i. Each job v also has an associated in-delay ρ^{in}_v and out-delay ρ^{out}_v. In a schedule, job v may be executed on machine i at time t if each predecessor u of v is completed on i before time t or on any machine j before time t - (ρ^{in}_i + ρ^{out}_j + ρ^{out}_u + ρ^{in}_v). The objective is to construct a schedule that minimizes makespan, which is the maximum completion time over all jobs.
We consider schedules which allow duplication of jobs as well as schedules which do not. When duplication is allowed, we provide an asymptotic polylog(n)-approximation algorithm. This approximation is further improved in the setting with uniform machine speeds and sizes. Our best approximation for non-uniform delays is provided for the setting with uniform speeds, uniform sizes, and no job delays. For schedules with no duplication, we obtain an asymptotic polylog(n)-approximation for the above model, and a true polylog(n)-approximation for symmetric machine and job delays. These results represent the first polylogarithmic approximation algorithms for scheduling with non-uniform communication delays.
Finally, we consider a more general model, where the delay can be an arbitrary function of the job and the machine executing it: job v can be executed on machine i at time t if all of v’s predecessors are executed on i by time t-1 or on any machine by time t - ρ_{v,i}. We present an approximation-preserving reduction from the Unique Machines Precedence-constrained Scheduling (umps) problem, first defined in [Sami Davies et al., 2022], to this job-machine delay model. The reduction entails logarithmic hardness for this delay setting, as well as polynomial hardness if the conjectured hardness of umps holds.
This set of results is among the first steps toward cataloging the rich landscape of problems in non-uniform delay scheduling.
BibTeX - Entry
@InProceedings{rajaraman_et_al:LIPIcs.ICALP.2023.98,
author = {Rajaraman, Rajmohan and Stalfa, David and Yang, Sheng},
title = {{Scheduling Under Non-Uniform Job and Machine Delays}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {98:1--98:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-278-5},
ISSN = {1868-8969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18150},
URN = {urn:nbn:de:0030-drops-181502},
doi = {10.4230/LIPIcs.ICALP.2023.98},
annote = {Keywords: Scheduling, Approximation Algorithms, Precedence Constraints, Communication Delay, Non-Uniform Delays}
}
|
Keywords: |
|
Scheduling, Approximation Algorithms, Precedence Constraints, Communication Delay, Non-Uniform Delays |
|
Collection: |
|
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
05.07.2023 |
