Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Uniform Bounds for Scheduling with Job Size Estimates   We consider the problem of scheduling to minimize mean response time in M/G/1
queues where only estimated job sizes (processing times) are known to the
scheduler, where a job of true size $s$ has estimated size in the interval
$[\beta s, \alpha s]$ for some $\alpha \geq \beta > 0$. We evaluate each
scheduling policy by its approximation ratio, which we define to be the ratio
between its mean response time and that of Shortest Remaining Processing Time
(SRPT), the optimal policy when true sizes are known. Our question: is there a
scheduling policy that (a) has approximation ratio near 1 when $\alpha$ and
$\beta$ are near 1, (b) has approximation ratio bounded by some function of
$\alpha$ and $\beta$ even when they are far from 1, and (c) can be implemented
without knowledge of $\alpha$ and $\beta$?
  We first show that naively running SRPT using estimated sizes in place of
true sizes is not such a policy: its approximation ratio can be arbitrarily
large for any fixed $\beta < 1$. We then provide a simple variant of SRPT for
estimated sizes that satisfies criteria (a), (b), and (c). In particular, we
prove its approximation ratio approaches 1 uniformly as $\alpha$ and $\beta$
approach 1. This is the first result showing this type of convergence for M/G/1
scheduling.
  We also study the Preemptive Shortest Job First (PSJF) policy, a cousin of
SRPT. We show that, unlike SRPT, naively running PSJF using estimated sizes in
place of true sizes satisfies criteria (b) and (c), as well as a weaker version
of (a).

31
The categories of this paper are: ao-sci
12
The categories of this paper are: nucl-th
28
The categories of this paper are: alg-geom
3
The categories of this paper are: physics
15
The categories of this paper are: nucl-ex
23
The categories of this paper are: solv-int
32
The categories of this paper are: atom-ph
26
The categories of this paper are: bayes-an
2
The categories of this paper are: math
14
The categories of this paper are: math-ph
16
The categories of this paper are: stat
5
The categories of this paper are: gr-qc
37
The categories of this paper are: supr-con
8
The categories of this paper are: hep-ex
0
The categories of this paper are: hep-ph
36
The categories of this paper are: cmp-lg