Minimization of ordered, symmetric half-products

We introduce a class of pseudo-Boolean functions called ordered, symmetric half-products. The class includes a number of well known scheduling problems. We study sets of dominating solutions for minimization of the half-products, and we show their fully polynomial time approximation schemes that use a natural rounding scheme to obtain ε-solutions in O(n2/ε) time.