Abstract
We study the problem of maximizing the violation of due dates when considering either the total violation, or the number of jobs that are tardy. We consider classical completion times and a variant useful in heuristics. The four problems arise when solving (exactly or heuristically) robust scheduling problems with release and due dates/deadlines and processing time uncertainty, and also routing problems with (soft) time windows and travel time uncertainty. We provide polynomial dynamic programming algorithms for the four problems.