A study of single‐machine scheduling problem to maximize throughput

We study inherent structural properties of a strongly NP‐hard problem of scheduling $n$ jobs with release times and due dates on a single machine to minimize the number of late jobs. Our study leads to two polynomial‐time algorithms. The first algorithm with the time complexity $O(n^3\log n)$ solves the problem if during its execution no job with some special property occurs. The second algorithm solves the version of the problem when all jobs have the same length. The time complexity of the latter algorithm is $O(n^2\log n)$ , which is an improvement over the earlier known algorithm with the time complexity $O(n^5)$ .