Online Makespan Minimization and List Update are online problems relevant to scheduling and data management. For List Update in the paid exchange model, the goal is to dynamically maintain a linear linked list. Lists are sensible data structures for managing small numbers of items. Online Makespan Minimization is one of the most fundamental problems in scheduling and load balancing. The task is to assign jobs, defined by their processing times, to parallel and identical machines. The goal is to minimize the makespan, the time it takes to process them all. Preemption is not allowed. We study Online Makespan Minimization first in the recently popular random-order model and then under budgeted uncertainty assumptions. In the random-order model, jobs are presented to the online algorithm in a uniformly random order, leading to a more optimistic performance measure. Budgeted uncertainty assumptions, on the other hand, account for errors and malfunctions, which increase the processing times of a few jobs. We finally consider the dual problem of Makespan Minimization, Machine Covering, in the random-order model. For Machine Covering, the goal is to keep all machines busy for as long as possible. For each of these problems, we provide the current best upper and lower bounds.     «

Online Makespan Minimization and List Update are online problems relevant to scheduling and data management. For List Update in the paid exchange model, the goal is to dynamically maintain a linear linked list. Lists are sensible data structures for managing small numbers of items. Online Makespan Minimization is one of the most fundamental problems in scheduling and load balancing. The task is to assign jobs, defined by their processing times, to parallel and identical machines. The goal is t...     »

Online-Makespan-Minimimierung und List-Update sind Online-Probleme des Scheduling und Datenmanagement. Beim List-Update-Problem im Paid-Exchange-Modell ist eine verkettete Liste mit allgemeinen Tauschkosten d zu verwalten. Listen sind adäquate Datenstrukturen, um eine kleine Anzahl an Einträgen zu organisieren. Bei Online-Makespan-Minimimierung führen identische und parallele Maschinen Aufgaben mit festen Bearbeitungszeiten aus. Aufgaben sind dabei so Maschinen zuzuweisen, dass die Gesamtlaufzeit, auch der Makespan genannt, minimal ist. Präemption ist nicht erlaubt. Makespan-Minimimierung ist ein grundlegendes Scheduling- und Load-Balancing-Problem. Wir untersuchen Online-Makespan-Minimierung im Random-Order-Modell. Im Random-Order-Modell erhalten Online-Algorithmen die Aufgaben in einer uniform zufälligen Reihenfolge. Weiterhin betrachten wir Makespan-Minimierung unter Budgeted-Uncertainty-Voraussetzungen, welche Fehler und Fehlfunktionen beim Ausführen der Aufgaben miteinbeziehen. Zu guter Letzt analysieren wir das duale Problem, Machine-Covering, im Random-Order-Modell. Für Machine-Covering sollen die Aufgaben so zugewiesen werden, dass alle Maschinen möglichst lange gleichzeitig beschäftigt sind. Für jedes dieser Probleme präsentieren wir die derzeitig besten oberen und unteren Schranken.     «

Online-Makespan-Minimimierung und List-Update sind Online-Probleme des Scheduling und Datenmanagement. Beim List-Update-Problem im Paid-Exchange-Modell ist eine verkettete Liste mit allgemeinen Tauschkosten d zu verwalten. Listen sind adäquate Datenstrukturen, um eine kleine Anzahl an Einträgen zu organisieren. Bei Online-Makespan-Minimimierung führen identische und parallele Maschinen Aufgaben mit festen Bearbeitungszeiten aus. Aufgaben sind dabei so Maschinen zuzuweisen, dass die Gesamtlaufz...     »