RANKING THE VERTICES OF A COMPLETE MULTIPARTITE PAIRED-COMPARISON DIGRAPH

A paired comparison digraph (abbreviated to PCD) D=(V,A) is a weighted digraph in which the sum of the weights of arcs, if any, joining two distinct vertices equals one. A one-to-one mapping alpha from V onto { 1,2,...,\V\} is called a ranking of D. For every ranking alpha, an arc vu is an element of A is said to be forward if alpha(upsilon) < alpha (u), and backward otherwise. The length of an arc vu is l(vu)=epsilon( vu)\alpha(upsilon)-alpha(u)\, where epsilon(vu) is the weight of vu. T he forward (backward) length f(D)(alpha) (b(D)(alpha)) of alpha is the sum of the lengths of all fonvard (backward) arcs of D. A ranking alp ha is forward (backward) optimal if f(alpha) is maximum (b(alpha) is m inimum). Kano (Discrete Appl. Math. 17 (1987) 245-253) characterized a ll backward optimal rankings of a complete multipartite PCD L and rais ed the problem to characterize all forward optimal rankings of a compl ete multipartite PCD L. We show how to transform the last problem into the single machine job sequencing problem of minimizing total weighte d completion time subject to precedence ''parallel chains'' constraint s. This provides an algorithm for generating all fonvard optimal ranki ngs of L as well as a polynomial algorithm for finding the average ran k of every vertex in L over all forward optimal rankings L.