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 pj and a weight wj. The goal is to find an ordering of the jobs that minimizes Σwjsgn(β)Cjβ, where β is some arbitrary real constant, and Cj 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).
