  In this study, we investigated several online and semi-online scheduling
problems on two hierarchical machines with a common due date to maximize the
total early work. For the pure online case, we designed an optimal online
algorithm with a competitive ratio of $\sqrt 2$. For the case when the total
processing time is known, we proposed an optimal semi-online algorithm with a
competitive ratio of $\frac{4}{3}$. Additionally, for the cases when the
largest processing time is known, we gave optimal algorithms with a competitive
ratio of $\frac{6}{5}$ if the largest job is a lower hierarchy one, and of
$\sqrt 5-1$ if the largest job is a higher hierarchy one, respectively.

Data Structures and Algorithms;Optimization and Control