The Power of α-Points in Preemptive Single Machine Scheduling
| dc.contributor.author | Schulz, Andreas S. | |
| dc.contributor.author | Skutella, Martin | |
| dc.date.accessioned | 2021-12-17T10:16:52Z | |
| dc.date.available | 2021-12-17T10:16:52Z | |
| dc.date.issued | 1999 | |
| dc.description.abstract | 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. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15940 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14713 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | scheduling theory | en |
| dc.subject.other | approximation algorithm | en |
| dc.subject.other | on-line algorithm | en |
| dc.subject.other | randomized algorithm | en |
| dc.subject.other | LP relaxation | en |
| dc.subject.other | combinatorial optimization | en |
| dc.title | The Power of α-Points in Preemptive Single Machine Scheduling | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 1999, 639 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
| tub.subject.msc2000 | 90C27 Combinatorial optimization | en |
| tub.subject.msc2000 | 68Q25 Analysis of algorithms and problem complexity | en |
| tub.subject.msc2000 | 90B35 Scheduling theory, deterministic | en |
| tub.subject.msc2000 | 68M20 Performance evaluation; queueing; scheduling | en |
| tub.subject.msc2000 | 90C59 Approximation methods and heuristics | en |