New Asymptotic Results on Stochastic Online Scheduling Problems

In the stochastic online scheduling environment, jobs with unknown release times and weights arrive over time. Upon arrival, the information on the weight of the job is revealed but the processing requirement remains unknown until the job is finished. In this paper, we consider the stochastic online single machine problem, uniform parallel machine problem and flow shop problem with the objective of minimizing the total weighted completion time. For each of these three problems, we show that a large class of nondelay algorithms is asymptotically optimal under some mild probabilistic assumptions. We also give examples to illustrate the significance and the practical usage of these results.