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.



processing time/weight for every job


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).