  We study flow scheduling under node capacity constraints. We are given
capacitated nodes and an online sequence of jobs, each with a release time and
a demand to be routed between two nodes. A schedule specifies which jobs are
routed in each step, guaranteeing that the total demand on a node in any step
is at most its capacity. A key metric in this scenario is response time: the
time between a job's release and its completion. Prior work shows no
un-augmented algorithm is competitive for average response time, and that a
constant factor competitive ratio is achievable with augmentation exceeding 2
(Dinitz-Moseley Infocom 2020). For maximum response time, the best known result
is a 2-competitive algorithm with a augmentation 4 (Jahanjou et al SPAA 2020).
We improve these bounds under various response time objectives. We show that,
without resource augmentation, the best competitive ratio for maximum response
time is $\Omega(n)$, where $n$ is the number of nodes. Our Proportional
Allocation algorithm uses $(1+\varepsilon)$ resource augmentation to achieve a
$(1/\varepsilon)$-competitive ratio in the setting with general demands and
capacities, and splittable jobs. Our Batch Decomposition algorithm is
$2$-competitive (resp., optimal) for maximum response time using resource
augmentation 2 (resp., 4) in the setting with unit demands and capacities, and
unsplittable jobs. We also derive bounds for the simultaneous approximation of
average and maximum response time metrics.
