Title
The Power of alpha-Points in Preemptive Single
Machine Scheduling
Authors
-
Publication
Journal of Scheduling, to appear.
Source
-
Classification
-
| MSC: |
| primary: | 90C27 | Combinatorial optimization |
| secondary: | 68Q25 | Analysis of algorithms and problem complexity |
| 90B35 | Scheduling theory, deterministic |
| 68M20 | Performance evaluation; queueing; scheduling |
| 90C59 | Approximation methods and heuristics |
Keywords
-
scheduling theory, approximation algorithm, on-line
algorithm, randomized algorithm, LP relaxation,
combinatorial optimization
-
-
We consider the NP-hard preemptive single machine scheduling
problem to minimize the total weighted completion time subject to
release dates. A natural extension of Smith's ratio rule is to
preempt the currently active job whenever a new job arrives that
has higher ratio of weight to processing time. We prove that the
competitive ratio of this simple on-line algorithm is
precisely~2. We also show that list scheduling in order of
random α-points drawn from the same schedule results in an
on-line algorithm with competitive ratio~4/3. Since its
analysis relies on a well-known integer programming relaxation of
the scheduling problem, the relaxation has performance
guarantee~4/3 as well. On the other hand, we show that it is at
best an~8/7-relaxation.
See also
-
