Extension of the bivariate characterization for stochastic orders

The bivariate characterization of stochastic ordering relations given by Shanthikumar and Yao (1991) is based on collections of bivariate functions g(x, y), where g(x, y) and g(y, x) satisfy certain properties. We give an alternate characterization based on collections of pairs of bivariate functions, g1(x, y) and g2(x, y), satisfying certain properties. This characterization allows us to extend results for single machine scheduling of jobs that are identical except for their processing times, to jobs that may have different costs associated with them.