Hoogeveen, HanSkutella, MartinWoeginger, Gerhard J.2021-12-172021-12-1720002197-8085https://depositonce.tu-berlin.de/handle/11303/15560http://dx.doi.org/10.14279/depositonce-14333We 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.en510 Mathematikschedulingpreemptionapproximation algorithmworst case ratiocomputational complexityin-approximabilityResearch Paper