2026-07-23T04:16:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18150 2024-03-06T11:01:09Z ddc:004 open_access

Scheduling Under Non-Uniform Job and Machine Delays Rajaraman, Rajmohan Stalfa, David Yang, Sheng Scheduling Approximation Algorithms Precedence Constraints Communication Delay Non-Uniform Delays 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rajmohan Rajaraman and David Stalfa and Sheng Yang 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.98 urn:nbn:de:0030-drops-181502 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.98 eng https://creativecommons.org/licenses/by/4.0/legalcode