Probabilistic Asymptotic Analysis 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 objective of minimizing the total weighted completion time. With the assumptions that job weights are bounded, machine capacity is adequate and processing requirements are i.i.d. across the machines and jobs, we show that any nondelay algorithm is asymptotically optimal for the stochastic online single machine problem and the stochastic online flow shop problem. For the stochastic online uniform parallel machine problem, we characterize the relationship between any two nondelay schedules and show that any nondelay algorithm is asymptotically optimal with the additional assumption that all job processing requirements are bounded. Our simulation studies on these stochastic online scheduling problems show that two generic nondelay algorithms converge very fast.