Scholarlink

<p>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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 发表日期：

    2026年6月26日

查看全文
  • Baruch Mor,
  • Gur Mosheiov

摘要

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.