Consider an M/G/1 queue with multiple classes of customers, non-preemptive service, and a cost of waiting. The server can select next any customer present or can remain idle; this decision can be made as a function of the complete state of the system, i.e., the number of each class of customer present. The objective is to minimize the stationary expected cost rate. Let 1/mu(i) be the mean service time and C(i) be the waiting cost per unit time for class i customers. The optimal policy is: Never hold the server idle when customers are present; and serve next a customer with the largest value of C(i)mu(i) among those present. This policy is Cox and Smith's priority class rule generalized to apply to any state of the system and to a broader class of allowable decisions. The result is obtained by formulating the problem as a semi-Markov decision process and solving the corresponding linear program. 18 pp. Ref.