Approximation in batch and multiprocessor scheduling [Elektronische Ressource] / Tim Nonner

.Approximation in Batch andMultiprocessor SchedulingDissertationzur Erlangung des Doktorgradesder Technischen Fakultat¨der Albert-Ludwigs-Universitat¨Freiburg im BreisgauTim NonnerDezember 2010Albert-Ludwigs-Universit¨at FreiburgTechnische Fakultat¨Dekan: Prof. Dr. Bernd BeckerReferent: Prof. Dr. Susanne AlbersKoreferent: Prof. Dr. Sven O. KrumkeTag der Promotion: 3. Dezember 2010AbstractThis thesis is about scheduling problems where jobs arrive over time. Dependingontheproblem,weconsiderthecasethateachjobhasadeadline,ortherelaxationthatthesumofflowtimesorcompletiontimesneedtobeminimized. SincemostofthediscussedproblemsareNP-hard,thegoalistofindpolynomialtimealgorithmswith provable approximation guarantee, preferably in an on-line setting.In the first part of this thesis, we consider batch scheduling problems for the casethat each job has a deadline, and hence two jobs may be added to the same batchif their due intervals intersect. We first present a framework that unifies all batchcost structures discussed in this part. For instance max-batching, where the costof each batch is the maximum weight of any contained job. We show that max-batchingisstronglyNP-hardinthiscontextifthesizeofeachbatchisadditionallyrestricted by a constant capacity constraint, and we also give a polynomial timeapproximation scheme (PTAS) for this case. Moreover, we consider a minmax-variant of max-batching which finds application in the area of data aggregation.