  Design and analysis of constant competitive deterministic semi-online
algorithms for the multi-processor scheduling problem with small number of
identical machines have gained significant research interest in the last two
decades. In the semi-online scheduling problem for makespan minimization, we
are given a sequence of independent jobs one by one in order and upon arrival,
each job must be allocated to a machine with prior knowledge of some Extra
Piece of Information (EPI) about the future jobs. Researchers have designed
multiple variants of semi-online scheduling algorithms with constant
competitive ratios by considering one or more EPI. In this paper, we propose
four new variants of competitive deterministic semi-online algorithms for
smaller number of identical machines by considering two EPI such as Decr and
Sum. We obtain improved upper bound and lower bound results on the competitive
ratio for our proposed algorithms, which are comparable to the best known
results in the literature. In two identical machines setting with known Sum, we
show a tight bound of 1.33 on the competitive ratio by considering a sequence
of equal size jobs. In the same setting we achieve a lower bound of 1.04 and an
upper bound of 1.16 by considering Sum and a sequence of jobs arriving in order
of decreasing sizes. For three identical machines setting with known Decr and
Sum, we show a lower bound of 1.11 on the competitive ratio. In this setting,
we obtain an upper bound of 1.5 for scheduling a sequence of equal size jobs
and achieves an upper bound of 1.2 by considering a sequence of decreasing size
jobs. Further we develop an improved competitive algorithm with an upper bound
of 1.11 on the competitive ratio.
