Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Structural Properties of an Open Problem in Preemptive Scheduling   Structural properties of optimal preemptive schedules have been studied in a
number of recent papers with a primary focus on two structural parameters: the
minimum number of preemptions necessary, and a tight lower bound on `shifts',
i.e., the sizes of intervals bounded by the times created by preemptions, job
starts, or completions. So far only rough bounds for these parameters have been
derived for specific problems. This paper sharpens the bounds on these
structural parameters for a well-known open problem in the theory of preemptive
scheduling: Instances consist of in-trees of $n$ unit-execution-time jobs with
release dates, and the objective is to minimize the total completion time on
two processors. This is among the current, tantalizing `threshold' problems of
scheduling theory: Our literature survey reveals that any significant
generalization leads to an NP-hard problem, but that any significant
simplification leads to tractable problem.
  For the above problem, we show that the number of preemptions necessary for
optimality need not exceed $2n-1$; that the number must be of order
$\Omega(\log n)$ for some instances; and that the minimum shift need not be
less than $2^{-2n+1}$. These bounds are obtained by combinatorial analysis of
optimal schedules rather than by the analysis of polytope corners for
linear-program formulations, an approach to be found in earlier papers. The
bounds immediately follow from a fundamental structural property called
`normality', by which minimal shifts of a job are exponentially decreasing
functions. In particular, the first interval between a preempted job's start
and its preemption is a multiple of 1/2, the second such interval is a multiple
of 1/4, and in general, the $i$-th preemption occurs at a multiple of $2^{-i}$.
We expect the new structural properties to play a prominent role in finally
settling a vexing, still-open question of complexity.

23
The categories of this paper are: solv-int
12
The categories of this paper are: nucl-th
7
The categories of this paper are: hep-th
35
The categories of this paper are: mtrl-th
27
The categories of this paper are: comp-gas
19
The categories of this paper are: eess
32
The categories of this paper are: atom-ph
16
The categories of this paper are: stat
26
The categories of this paper are: bayes-an
4
The categories of this paper are: cond-mat
36
The categories of this paper are: cmp-lg
29
The categories of this paper are: funct-an
25
The categories of this paper are: patt-sol
8
The categories of this paper are: hep-ex
0
The categories of this paper are: hep-ph
24
The categories of this paper are: dg-ga