Minimizing maximum late work with optional job rejection on a single machine

In this paper, we study the problem of minimizing the maximum late work with the popular option of job rejection on a single machine. We provide two fundamental properties regarding an optimal schedule, prove that the problem is NP-hard, and suggest pseudo-polynomial dynamic programming (DP), establishing that the problem is ordinary NP-hard. We also provide an extensive numerical study. Next, we leverage the provided DP to introduce an algorithm that maps the Pareto-optimal frontier.