Stochastic scheduling problem with varying weight for each job
Authors:
- 1 July 2010
- journal article
- research article
- Published by Wiley in Asia-Pacific Journal of Chemical Engineering
- Vol. 5 (4) , 681-689
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.Keywords
This publication has 18 references indexed in Scilit:
- Preemptive stochastic online scheduling on two uniform machinesInformation Processing Letters, 2009
- Stochastic Machine Scheduling with Precedence ConstraintsSIAM Journal on Computing, 2005
- Approximation in stochastic schedulingJournal of the ACM, 1999
- On almost optimal priority rules for preemptive scheduling of stochastic jobs on parallel machinesAdvances in Applied Probability, 1995
- A Short Proof of the Gittins Index TheoremThe Annals of Applied Probability, 1994
- Stochastic scheduling problems II-set strategies-Mathematical Methods of Operations Research, 1985
- Stochastic scheduling problems I — General strategiesMathematical Methods of Operations Research, 1984
- Sequencing Tasks with Exponential Service Times to Minimize the Expected Flow Time or MakespanJournal of the ACM, 1981
- Scheduling for Minimum Total Loss Using Service Time DistributionsJournal of the ACM, 1974
- A note on time-sharingJournal of Combinatorial Theory, 1968