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.
Mor, Baruch, Mosheiov, Gur. Minimizing maximum late work with optional job rejection on a single machine. // Journal of Scheduling. – 2026. – DOI: 10.1007/s10951-026-00881-4. – URL: http://link.springer.com/openurl/fulltext?id=doi:10.1007/s10951-026-00881-4
Mor, Baruch, Mosheiov, & Gur (2026). Minimizing maximum late work with optional job rejection on a single machine. Journal of Scheduling. https://doi.org/10.1007/s10951-026-00881-4
Mor, et al. “Minimizing maximum late work with optional job rejection on a single machine.” Journal of Scheduling, 2026. doi:10.1007/s10951-026-00881-4.
@article{Mor2026,
title = {Minimizing maximum late work with optional job rejection on a single machine},
author = {Mor and Baruch and Mosheiov and Gur},
journal = {Journal of Scheduling},
year = {2026},
doi = {10.1007/s10951-026-00881-4},
url = {http://link.springer.com/openurl/fulltext?id=doi:10.1007/s10951-026-00881-4}
}
In this paper, we consider cost-sharing problems defined on rooted trees. We refer to these problems as cost-tree problems and to the induced transferable utility cooperative games as irrigation games. We introduce a formal notion of...
In this paper, we focus on nonlinear programming problems with cardinality constraints that restrict the number of nonzero components of the decision vector. We start with a straightforward mixed-integer programming reformulation....
Portfolio selection is a critical issue in financial management under uncertainty. In this paper, we propose a complex approach for portfolio selection with quantile return approximation. In particular, we propose a practical workflow...
The transcendental logarithmic (translog) production function is recognised as a flexible functional form for modelling production processes. It accommodates varying elasticities of input substitution and diverse types of...
This study investigates mothership-drone route determination using two optimization approaches: a Mixed Integer Linear Programming (MILP) model based on a discrete hexagonal grid, and a Mixed Integer Nonlinear Programming (MINLP) model...