  We consider the classical scheduling problem on a single machine, on which we
need to schedule sequentially $n$ given jobs. Every job $j$ has a processing
time $p_j$ and a priority weight $w_j$, and for a given schedule a completion
time $C_j$. In this paper we consider the problem of minimizing the objective
value $\sum_j w_j C_j^\beta$ for some fixed constant $\beta>0$. This
non-linearity is motivated for example by the learning effect of a machine
improving its efficiency over time, or by the speed scaling model. For
$\beta=1$, the well-known Smith's rule that orders job in the non-increasing
order of $w_j/p_j$ give the optimum schedule. However, for $\beta \neq 1$, the
complexity status of this problem is open. Among other things, a key issue here
is that the ordering between a pair of jobs is not well-defined, and might
depend on where the jobs lie in the schedule and also on the jobs between them.
We investigate this question systematically and substantially generalize the
previously known results in this direction. These results lead to interesting
new dominance properties among schedules which lead to huge speed up in exact
algorithms for the problem. An experimental study evaluates the impact of these
properties on the exact algorithm A*.
