We consider the problem of scheduling jobs on a single machine.
Given a nonlinear cost function, we aim to compute a schedule minimizing
the weighted total cost, where the cost of each job is defined as the
cost function value at the job's completion time. Throughout the past
decades, great effort has been made to develop fast optimal branch-and-bound
algorithms for the case of quadratic costs. The practical efficiency of these
methods heavily depends on the utilization of structural properties of optimal
schedules such as order constraints, i.e., sufficient conditions for pairs of jobs
to appear in a certain order. The first part of this
paper substantially enhances and generalizes the known order constraints.
We prove a stronger version of the global order conjecture by Mondal and
Sen that has remained open since 2000, and we generalize the two main
types of local order constraints to a large class of polynomial cost functions.

The new constraints directly give rise to branch-and-bound algorithms with
improved efficiency. We take a different route
in the second part of this paper and demonstrate the usefulness of order constraints as analytical tools. The WSPT rule, which is well-known to be optimal in the linear cost case, is proven to approximate optimal schedules up to a constant factor that equals the degree of the cost function when the latter is a polynomial with nonnegative coefficients. Furthermore, we give a slightly modified algorithm improving that factor; from 2 to 1.75 in the quadratic case. The previously best known approximation ratio achieved for all these problems is 16.