Scholarlink

<p>We consider two single-machine scheduling problems with the late work criterion, where each job’s processing time follows a decreasing convex function of the resource consumption amount, and each job can be interrupted and resumed later. The first objective is to minimize the sum of late work and resource consumption amount, while the second objective is to minimize the total late work with a constraint on the total resource consumption amount. We show that both problems can be solved in strongly polynomial time.</p>

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

A preemptive single-machine scheduling problem with a late work criterion and convex resource consumption functions

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年2月4日

查看全文
  • Byung-Cheon Choi,
  • Myoung-Ju Park

摘要

We consider two single-machine scheduling problems with the late work criterion, where each job’s processing time follows a decreasing convex function of the resource consumption amount, and each job can be interrupted and resumed later. The first objective is to minimize the sum of late work and resource consumption amount, while the second objective is to minimize the total late work with a constraint on the total resource consumption amount. We show that both problems can be solved in strongly polynomial time.