Stochastic Online Scheduling

In this paper we consider a model for scheduling under uncertainty. Inthis model, we combine the main characteristics of online and stochasticscheduling in a simple and natural way. Jobs arrive in an online mannerand as soon as a job becomes known, the scheduler only learns aboutthe probability distribution of the processing time and not the actualprocessing time. This model is called the stochastic online scheduling(SOS) model. Both online scheduling and stochastic scheduling are specialcases of this model. In this paper, we survey the results for the SOS model