Firstly, for the processing benefit maximization scheduling problem of \( m \) identical machines with a common due date, we prove that the offline optimal value satisfies \(F^{*}=\min \left\{ P_{sum},md+\delta \left( P_{sum}-md \right) \right\} \) . Secondly, we consider the semi-online scheduling problem of two identical machines with delayed discount to maximize the processing benefit, prove the lower bound of this problem is \(\frac{6}{5+\delta }\) and design an optimal semi-online algorithm with a competitive ratio of \(\frac{6}{5+\delta }\) .

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

Semi-online Scheduling Problem of Two Identical Machines with Delayed Discount

  • Qingyu Luo,
  • Yaru Yang

摘要

Firstly, for the processing benefit maximization scheduling problem of \( m \) identical machines with a common due date, we prove that the offline optimal value satisfies \(F^{*}=\min \left\{ P_{sum},md+\delta \left( P_{sum}-md \right) \right\} \) . Secondly, we consider the semi-online scheduling problem of two identical machines with delayed discount to maximize the processing benefit, prove the lower bound of this problem is \(\frac{6}{5+\delta }\) and design an optimal semi-online algorithm with a competitive ratio of \(\frac{6}{5+\delta }\) .