Stochastic scheduling on parallel machines to minimize discounted holding costs

Xiaoqiang Cai, Xianyi Wu*, Xian Zhou

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


We study stochastic scheduling on m parallel identical machines with random processing times. The cost involved in the problem is discounted to the present value and the objective is to minimize the expected discounted holding cost, which covers in a unified framework many performance measures discussed in the literature as special cases, including discounted rewards, flowtime, and makespan. We prove that the SEPT rule is optimal, on a fairly general ground, in the class of preemptive dynamic policies, the class of nonpreemptive dynamic policies, and the class of nonpreemptive static list policies. The LEPT rule, on the other hand, is optimal to minimize the expected discounted makespan only under certain restrictive conditions. Without such conditions, the LEPT rule is found no longer optimal for discounted makespan by a counterexample, in contrast to the case without discounting.

Original languageEnglish
Pages (from-to)375-388
Number of pages14
JournalJournal of Scheduling
Issue number4
Publication statusPublished - Aug 2009


Dive into the research topics of 'Stochastic scheduling on parallel machines to minimize discounted holding costs'. Together they form a unique fingerprint.

Cite this