  We consider the following scheduling problem. There is a single machine and
the jobs will arrive for completion online. Each job j is preemptive and, upon
its arrival, its other characteristics are immediately revealed to the machine:
the deadline requirement, the workload and the value. The objective is to
maximize the aggregate value of jobs completed by their deadlines. Using the
minimum of the ratios of deadline minus arrival time to workload over all jobs
as the slackness s, a non-committed and a committed online scheduling algorithm
is proposed in [Lucier et al., SPAA'13; Azar et al., EC'15], achieving
competitive ratios of 2+f(s), where the big O notation
f(s)=\mathcal{O}(\frac{1}{(\sqrt[3]{s}-1)^{2}}), and (2+f(s*b))/b respectively,
where b=\omega*(1-\omega), \omega is in (0, 1), and s is no less than 1/b. In
this paper, without recourse to the dual fitting technique used in the above
works, we propose a simpler and more intuitive analytical framework for the two
algorithms, improving the competitive ratio of the first algorithm by 1 and
therefore improving the competitive ratio of the second algorithm by 1/b. As
stated in [Lucier et al., SPAA'13; Azar et al. EC'15], it is justifiable in
scenarios like the online batch processing for cloud computing that the
slackness s is large, hence the big O notation in the above competitive ratios
can be ignored. Under the assumption, our analysis brings very significant
improvements to the competitive ratios of the two algorithms: from 2 to 1 and
from 2/b to 1/b respectively.
