  Online scheduling has been a well studied and challenging research problem
over the last five decades since the pioneering work of Graham with immense
practical significance in various applications such as interactive parallel
processing, routing in communication networks, distributed data management,
client-server communications, traffic management in transportation, industrial
manufacturing and production. In this problem, a sequence of jobs is received
one by one in order by the scheduler for scheduling over a number of machines.
On arrival of a job, the scheduler assigns the job irrevocably to a machine
before the availability of the next job with an objective to minimize the
completion time of the scheduled jobs. This paper highlights the state of the
art contributions for online scheduling of a sequence of independent jobs on
identical and uniform related machines with a special focus on preemptive and
non-preemptive processing formats by considering makespan minimization as the
optimality criterion. We present the fundamental aspects of online scheduling
from a beginner's perspective along with a background of general scheduling
framework. Important competitive analysis results obtained by well-known
deterministic and randomized online scheduling algorithms in the literature are
presented along with research challenges and open problems. Two of the emerging
recent trends such as resource augmentation and semi-online scheduling are
discussed as a motivation for future research work.
