Minimizing the number of tardy job units under release time constraints (Q919993)

Two single-machine scheduling problems are considered: minimizing the weighted and unweighted number of tardy units, when release times are present. Fast strongly polynomial algorithms are given for both problems: for problems with n jobs, algorithms which require O(n log n) and \(O(n^ 2)\) steps, for the unweighted and weighted problems are given, respectively. These results imply an extension of the family of very efficiently solvable transportation problems, as well as of those which are greedily solvable using the ``Monge sequence'' idea.