We consider discrete-time dynamic scheduling problems of the following three types of G/G/1 queue with K different customer classes: (i) a G/DFR/1 queue with K classes under preemptive resume service discipline, (ii) a G/IFR/1 queue with two classes under preemptive resume service discipline, and (iii) a G/G/1 queue with two classes under non-preemptive service discipline. Interchange arguments are used to show that simple index policies of different type minimize the total holding cost of customers in a finite-horizon scheduling period for the three cases. Our results extend the result for a G/M/1 queue by Buyukkoc et al. (1985) to general queues.

In a recent paper by Shanthikumar and Sumita (1987), it is conjectured that the ergodic sojourn time of a customer in G/IFR/1 queues is minimized by FIFO (first in, first out) discipline in the sense of increasing and convex ordering. This paper shows that their conjecture is true. In fact, FIFO discipline minimizes for any non-decreasing and convex function f, where N is the (constant) number of arrivals, θ (k) is the customer identity of the kth departing customer, and an and τ n denote the arriving and departing times of the nth customer, respectively.