# Single machine scheduling minimizing non-linear cost
or $1||\sum w_j sgn(\beta)C_j^\beta$

We are given *n* jobs. Each job has a processing time p_{j} and a weight w_{j}. The goal is to find an ordering of the jobs that minimizes Σw_{j}sgn(β)C_{j}^{β}, where β is some arbitrary real constant, and C_{j} is the completion time of job j. Also sgn(β) is defined as β/|β|.
The complexity status of this problem is open.

[src]

## Input

## Output

The diagram below shows the optimal schedule. Vertical lines indicate for all job pairs *i,j* the separation point *t*^{*}. (See this article for explanation).