Xiaoqiang Cai, Xianyi Wu and Xian Zhou. Stochastic Scheduling on Parallel Machines to Minimize General Discounted Holding Costs

Abstract. We study stochastic scheduling on a set of 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 a general discounted holding cost, which
covers in a unified framework many performance measures arising in practical applications such as telecommunications, manufacturing, and logistics management, 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 some 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.