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 journalArticle

6 Citations (Scopus)

Abstract

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
Volume12
Issue number4
DOIs
Publication statusPublished - Aug 2009

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

Cite this