The maximum deviation just-in-time scheduling problem. (Q1421459)

The authors revisited one of the most basic scheduling models of just-in-time production systems. Despite its apparent simplicity, this model is not completely understood, yet. In particular, its computational complexity is not exactly known. They show that the model is in co-NP and it is polynomially solvable when the number of part-types is fixed, but its general version may still turn out to be either co-NP-complete or polynomially solvable. Finally, obtaining a full description of instances with small max-deviation the authors present an interesting challenge for future research.