Scholarlink

<p>This paper investigates the online scheduling of unit jobs with rejection on two identical parallel machines. All jobs arrive sequentially in an online fashion, and upon each job’s arrival, an immediate decision must be made to either accept or reject it. The goal is to minimize the maximum quadratic completion time of accepted jobs plus the total rejection penalty of rejected jobs. For this problem, we present a deterministic online algorithm with the best-possible competitive ratio of 2.</p>

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

Online Two Identical Parallel Machine Scheduling of Unit Jobs with Rejection to Minimize the Maximum Quadratic Completion Time

  • 期刊论文

  • 发表日期：

    2026年7月4日

查看全文
  • Jing Zhang,
  • Ling-Fa Lu,
  • Li-Qi Zhang

摘要

This paper investigates the online scheduling of unit jobs with rejection on two identical parallel machines. All jobs arrive sequentially in an online fashion, and upon each job’s arrival, an immediate decision must be made to either accept or reject it. The goal is to minimize the maximum quadratic completion time of accepted jobs plus the total rejection penalty of rejected jobs. For this problem, we present a deterministic online algorithm with the best-possible competitive ratio of 2.