Scholarlink

<p>In this paper, we consider the <i>W</i>-prize-collecting scheduling problem on a single machine with submodular rejection penalties. In this problem, we are given one machine, <i>n</i> jobs and a value <i>W</i>. Every job has a processing time and a profit. Each job is either accepted and processed on the machine, or rejected and a rejection penalty is paid. The objective is to minimize the sum of the makespan of the accepted jobs and the rejection penalties of the rejected jobs which is determined by a submodular function, provided that the total profit of the accepted jobs is at least <i>W</i>. Under the assumption that the submodular penalty function is polymatriod, we design a 2-approximation algorithm based on the primal-dual framework.</p>

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

Approximation algorithms for the W-prize-collecting scheduling problem on a single machine with submodular rejection penalties

  • 期刊论文

  • 发表日期：

    2025年5月21日

查看全文
  • Tianjiao Guo,
  • Wen Liu,
  • Gengsheng Zhang,
  • Bo Hou

摘要

In this paper, we consider the W-prize-collecting scheduling problem on a single machine with submodular rejection penalties. In this problem, we are given one machine, n jobs and a value W. Every job has a processing time and a profit. Each job is either accepted and processed on the machine, or rejected and a rejection penalty is paid. The objective is to minimize the sum of the makespan of the accepted jobs and the rejection penalties of the rejected jobs which is determined by a submodular function, provided that the total profit of the accepted jobs is at least W. Under the assumption that the submodular penalty function is polymatriod, we design a 2-approximation algorithm based on the primal-dual framework.