Preemptive scheduling with rejection
dc.contributor.author | Hoogeveen, Han | |
dc.contributor.author | Skutella, Martin | |
dc.contributor.author | Woeginger, Gerhard J. | |
dc.date.accessioned | 2021-12-17T10:06:27Z | |
dc.date.available | 2021-12-17T10:06:27Z | |
dc.date.issued | 2000 | |
dc.description.abstract | We consider the problem of preemptively scheduling a set of n jobs on m (identical, uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the jobs and thereby incur job-dependent penalties for each rejected job, and he must construct a schedule for the remaining jobs so as to optimize the preemptive makespan on the m machines plus the sum of the penalties of the jobs rejected. | en |
dc.identifier.issn | 2197-8085 | |
dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15560 | |
dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14333 | |
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 | preemption | en |
dc.subject.other | approximation algorithm | en |
dc.subject.other | worst case ratio | en |
dc.subject.other | computational complexity | en |
dc.subject.other | in-approximability | en |
dc.title | Preemptive scheduling with rejection | 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 | 2000, 684 | 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 |