ABSTRACT
Many scheduling problems that arise in practice are inherently online in nature. In these settings, scheduling decisions must be made without complete information about the entire problem instance. This lack of information may stem from various sources: (1) Jobs arrive one by one as a list or even as an input stream over time. Scheduling decisions must always be made without knowledge of any future jobs. (2) The processing times of jobs are unknown initially and during run time. They become known only when jobs actually finish. (3) Machine breakdown and maintenance intervals are unknown.
