Online scheduling for buffering problems [Elektronische Ressource] / vorgelegt von Matthias Englert

Online Schedulingfor Bu ering ProblemsVon der Fakult at fur Mathematik, Informatik und Naturwissenschaftender RWTH Aachen University zur Erlangung des akademischen Gradeseines Doktors der Naturwissenschaften genehmigte Dissertationvorgelegt vonDiplom-InformatikerMatthias Englertaus WarendorfBerichter: Dr. Matthias WestermannUniversit atsprofessor Dr. Ir. Joost-Pieter KatoenUniversit Dr. Rolf NiedermeierTag der mundlic hen Prufung: 30. Mai 2008Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfugbar.AbstractIn a scheduling problem, tasks have to be assigned to resources in such a way thatsome speci ed objective is accomplished. Often times, tasks either can or have tobe stored in a bu er before they are assigned to a resource. In these cases, a bu ermanagement strategy has to constantly facilitate decisions as to which tasks to storein the bu er, which tasks to execute, and which tasks to delete from the bu er. Ifthe tasks arrive over time, these decisions have to be made online, that is, withoutknowledge of the future.The predominant method to investigate online algorithms is the competitiveanalysis. An online algorithm isc-competitive if, for every input, the solution returnedby the algorithm is at most by a factor of c worse than a solution given by an optimalo ine algorithm. We study four di erent online scheduling problems, in which buersare a crucial component, in a competitive analysis.