Semi-online scheduling on two identical machines with a common due date to maximize total early work

In this paper, we consider four semi-online scheduling problems with the goal of early work maximization, which shares the same essence with late work minimization when the optimal offline solutions are determined, but differs from it when the approximation or online solutions are constructed. First, we prove a tight bound 6/5 for scheduling jobs with a common due date when assuming that the total processing time of all jobs, or, the optimal criterion value is known in advance. Then, we show that if both the total and maximal processing time is known, the bound can be reduced to 10/9 and it is still tight. Finally, we prove that if only know the maximal processing time, the upper and lower bounds are 1.1375 and 1.1231, respectively. (C) 2020 Elsevier B.V. All rights reserved.

Automated summary

This paper investigates four semi-online scheduling problems with the goal of maximizing early work completion. The results show that different upper and lower bounds exist under different conditions.