Minimizing maximum lateness of jobs with naturally bounded job data on a single machine in polynomial time

What is it about?

This paper considers the problem of scheduloing jobs with release dates and due dates on a single machine to minimize maximum lateness. For this NP-hard problem, it is shown that the special case when the maximal processing time and the difference between any job release dates is bounded by a constant can be polynomially solved.

Featured Image

Why is it important?

These restrictions often arise naturally in applications so that a polynomial algorithm exists in this case.