On-line scheduling to minimize average completion time revisited
dc.contributor.author | Megow, Nicole | |
dc.contributor.author | Schulz, Andreas S. | |
dc.date.accessioned | 2021-12-17T10:05:36Z | |
dc.date.available | 2021-12-17T10:05:36Z | |
dc.date.issued | 2003 | |
dc.description.abstract | We consider the scheduling problem of minimizing the average weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms. | en |
dc.identifier.issn | 2197-8085 | |
dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15497 | |
dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14270 | |
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 | en |
dc.subject.other | on-line algorithms | en |
dc.subject.other | approximation algorithms | en |
dc.subject.other | deterministic | en |
dc.subject.other | competitive analysis | en |
dc.subject.other | average completion time | en |
dc.title | On-line scheduling to minimize average completion time revisited | 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 | 2003, 22 | en |
tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |