Abstract
This paper studies the preemptive stochastic online scheduling problem, which is a simple combination of online and stochastic scheduling. The processing times of jobs are assumed to be subject to independent probability distributions, and we assume that jobs arrive overtime, which means there is no knowledge about the jobs that arrive in the future. We particularly consider the preemptive setting where a job is allowed to be interrupted during its processing. The weight (holding cost ratio) associated with each job may change during its processing, and the objective is to minimize the expected value of total holding cost for all jobs. For the single andmidentical machine problems, we propose scheduling policies, SPGS [semi‐preemptive Gittins Index Priority Policy (GIPP) on single machine] and SPGI (semi‐preemptive GIPP on identical machines), respectively, both of which are proved to be constant‐factor approximation. Copyright © 2009 Curtin University of Technology and John Wiley & Sons, Ltd.

This publication has 18 references indexed in Scilit: