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

Mor, Baruch, Mosheiov, Gur
Journal of Scheduling · Springer Nature · 2026-06-26 · DOI: 10.1007/s10951-026-00881-4

Abstract

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.

Read at publisher →

Similar articles