It is shown that First-In-First-Out (FIFO) has competitive ratio $\Omega(\log m)$ even when every job is an out-tree, and a lower bound is proved of $\Omega(\min\{m,\mathrm{OPT}\})$ for every non-clairvoyant online algorithm, where $\mathrm{OPT}$ is the maximum flow time of an optimal offline schedule.
Abstract
We study online scheduling of parallel jobs on $m$ identical processors to minimize maximum flow time. Each arriving job is represented by a directed acyclic graph (DAG) whose vertices are unit-time subjobs and whose edges specify precedence constraints. We consider non-clairvoyant algorithms: the DAG is not known when a job arrives, and each subjob is revealed only when it becomes ready. Agrawal, Moseley, Newman, and Pruhs (SPAA 2024) showed that First-In-First-Out (FIFO) has competitive ratio $\Omega(\log m)$ even when every job is an out-tree. They also proved that FIFO is $O(\log m)$-competitive in several natural settings and asked whether this guarantee extends to general instances. More broadly, they asked whether any non-clairvoyant algorithm can be $O(1)$-competitive. We answer both questions in the negative by proving a lower bound of $\Omega(\min\{m,\mathrm{OPT}\})$ for every non-clairvoyant online algorithm, where $\mathrm{OPT}$ is the maximum flow time of an optimal offline schedule. In particular, every non-clairvoyant algorithm has competitive ratio $\Omega(m)$ on some instance with $\mathrm{OPT} \ge m$. The lower bound holds even when every job is an out-forest. We complement these lower bounds with an asymptotically optimal non-clairvoyant algorithm. FIFO is $O(m)$-competitive, but can have competitive ratio $\Omega(m)$ even when $\mathrm{OPT}=O(1)$. For instances with small $\mathrm{OPT}$, we design a Small-Frontier-First algorithm that is $O(\mathrm{OPT})$-competitive. Combining the two algorithms yields an $O(\min\{m,\mathrm{OPT}\})$-competitive non-clairvoyant algorithm.
In classical fixed-interval scheduling, each job of a given set must be processed during a prescribed time interval. The goal is to assign each job to exactly one machine such that no two jobs assigned to the same machine overlap in their interiors, and the number of machines used is minimized. Without further constrai...
Shreyas Ghildiyal, N. MuralidharaV· arXiv.org· 0 citations
We study unweighted nonpreemptive throughput maximization: given jobs with processing times, release times, and deadlines, schedule a maximum-cardinality subset on identical machines. For every fixed $\varepsilon>0$, we give randomized algorithms with expected approximation ratios $17/13+\varepsilon$ in polynomial time...
We study the single-machine total-completion-time problem $1||\sum C_j$ when processing times are unknown but each job comes with a reported interval. Jobs are initially processed in nondecreasing order of reported upper bound. If a job is still unfinished after receiving that much service, the reported upper bound has...
These results give sharp guarantees for bounded-size local search on matchable semi-matchings, including exact guarantees under degree bounds for bounded-size local search on matchable semi-matchings.
The classic scheduling problem of minimizing the total weight of tardy jobs ($P_m||\sum_jw_jU_j$) asks for a schedule of jobs each with a processing time, weight, and due date on a constant number of parallel identical machines. A job is late in a schedule if it completes after its due date, and an optimal schedule is...
Klaus Jansen, Björn Schumacher, Corinna Wambsganz· 0 citations
The Polytope Scheduling Problem (PSP) is a general framework for preemptive scheduling in which feasible instantaneous job allocations form a packing polytope. In the nonclairvoyant online setting, Proportional Fairness (PF), a practical allocation rule rooted in market theory, is the leading general-purpose algorithm....
Sven Jäger, Alexander Lindermayr, Bart Zondervan· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.