Semi-online Scheduling Problem of Two Identical Machines with Delayed Discount
摘要
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 }\) .