Rearrangement, Majorization and Stochastic Scheduling

Rearrangement inequalities, such as the classical Hardy-Littlewood-Polya inequality and the more general Day's inequality, and related majorization results are often useful in solving scheduling problems. Among other things, they are essential for pairwise interchange arguments. Motivated by solving stochastic scheduling problems, we develop stochastic versions of Day's Inequality, over both unrestricted and restricted (specifically, one-cycle) permutations. These lead to a general and unified approach, which we apply to solve the stochastic versions of several classical deterministic scheduling problems. In most cases, the approach leads to new or stronger results; in other cases it recovers known results with new insight. The approach is built upon recent developments in stochastic majorization and multivariate characterization of stochastic order relations.