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 Shortest Expected Processing Time (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 Longest Expected Processing Time (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.
