A polynomially solvable case of a single machine scheduling problem when the maximal job processing time is a constant

What is it about?

This conference paper considers a single machine scheduling problem with given release and due dates and the minimization of maximum lateness. We consider the special case of this NP-hard problem when the maximim processing time is bounded by a constant and give a polynomial-time algorithm for this case.

Featured Image