direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 639-1999

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

The Power of alpha-Points in Preemptive Single Machine Scheduling
Journal of Scheduling, to appear.
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
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.
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe