Scholarlink

In this paper, we delve into the online budget allocation maximization (BAM) problem on two uniform machines. Given two uniform machines, \(M_1\) and \(M_2\) , with speeds \(s\ge 1\) and 1, respectively, all jobs \(\mathcal{J}=\{J_1,\cdots ,J_n\}\) are ordered in a list and arrive one by one. Each job \(J_j\) has a size \(p_j\) and a common due date d for \(j=1,\cdots ,n\) . The objective is to determine a schedule that maximizes the total size of jobs processed by these two machines before the due date. For this problem, we propose an online algorithm with a competitive ratio of \((\sqrt{s^2+10s+9}-s-1)/2\) , which is bounded by a constant value of 2 and reaches \(\sqrt{5}-1\) when \(s=1\) . For a special case, known as the BAM \(_{\le 1}\) problem, we devise an online algorithm with a competitive ratio of \((\sqrt{9s^2+10s+1}-s-1)/2s\) , which is no greater than \(\sqrt{5}-1\) .

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

Online Budget Allocation Maximization Problem on Two Uniform Machines with a Common Due Date

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Yaru Yang,
  • Honglin Ding,
  • Wentao He

摘要

In this paper, we delve into the online budget allocation maximization (BAM) problem on two uniform machines. Given two uniform machines, \(M_1\) and \(M_2\) , with speeds \(s\ge 1\) and 1, respectively, all jobs \(\mathcal{J}=\{J_1,\cdots ,J_n\}\) are ordered in a list and arrive one by one. Each job \(J_j\) has a size \(p_j\) and a common due date d for \(j=1,\cdots ,n\) . The objective is to determine a schedule that maximizes the total size of jobs processed by these two machines before the due date. For this problem, we propose an online algorithm with a competitive ratio of \((\sqrt{s^2+10s+9}-s-1)/2\) , which is bounded by a constant value of 2 and reaches \(\sqrt{5}-1\) when \(s=1\) . For a special case, known as the BAM \(_{\le 1}\) problem, we devise an online algorithm with a competitive ratio of \((\sqrt{9s^2+10s+1}-s-1)/2s\) , which is no greater than \(\sqrt{5}-1\) .