Scholarlink

<p>We consider a multi-agent scheduling problem on a single machine with <i>k</i> competing agents. The objective is to minimize the total completion time of first agent, subject to the condition that the total completion time of any other agent is bounded. When <i>k</i> is arbitrary, the exact complexity of this problem is open. We show the unary NP-hardness of this problem and present a polynomial-time algorithm when all the jobs of first agent have deadlines and any other agent has only one job.</p>

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

Multi-agent Scheduling to Minimize Total Completion Times

  • 期刊论文

  • 发表日期：

    2025年6月17日

查看全文
  • Ru-Bing Chen,
  • Yuan Gao,
  • Jin-Jiang Yuan,
  • Qiu-Lan Zhao

摘要

We consider a multi-agent scheduling problem on a single machine with k competing agents. The objective is to minimize the total completion time of first agent, subject to the condition that the total completion time of any other agent is bounded. When k is arbitrary, the exact complexity of this problem is open. We show the unary NP-hardness of this problem and present a polynomial-time algorithm when all the jobs of first agent have deadlines and any other agent has only one job.