Scholarlink

<p>We investigate a variant of the classic knapsack problem in the context of single-machine scheduling with controllable processing times under a makespan constraint. In this problem, the processing time of each job is a bounded linear decreasing function of the amount of resource allocated to its job processing operation. The task is to choose some jobs for processing with the goal to maximize the total profit while satisfying a given makespan constraint, where the total profit is the total revenue minus the total resource consumption cost. We show that the studied problem is NP-hard. By exploring the structural properties on the optimal solution, we propose a constant factor approximation algorithm with a performance ratio of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\frac{1}{5}\)</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mn>1</mn> <mn>5</mn> </mfrac> </math></EquationSource> </InlineEquation>. Subsequently, we design a dynamic programming exact algorithm and a fully strongly polynomial time approximation scheme.</p>

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

Single-machine scheduling with rejection and controllable processing times to maximize profit under a makespan constraint

  • 期刊论文

  • 发表日期：

    2026年5月20日

查看全文
  • Yanjie Guo,
  • Wenchang Luo

摘要

We investigate a variant of the classic knapsack problem in the context of single-machine scheduling with controllable processing times under a makespan constraint. In this problem, the processing time of each job is a bounded linear decreasing function of the amount of resource allocated to its job processing operation. The task is to choose some jobs for processing with the goal to maximize the total profit while satisfying a given makespan constraint, where the total profit is the total revenue minus the total resource consumption cost. We show that the studied problem is NP-hard. By exploring the structural properties on the optimal solution, we propose a constant factor approximation algorithm with a performance ratio of \(\frac{1}{5}\) 1 5 . Subsequently, we design a dynamic programming exact algorithm and a fully strongly polynomial time approximation scheme.