  Multiprocessor task scheduling is an important and computationally difficult
problem. This paper proposes a comparison study of genetic algorithm and list
scheduling algorithm. Both algorithms are naturally parallelizable but have
heavy data dependencies. Based on experimental results, this paper presents a
detailed analysis of the scalability, advantages and disadvantages of each
algorithm. Multiprocessors have emerged as a powerful computing means for
running real-time applications, especially where a uni-processor system would
not be sufficient enough to execute all the tasks. The high performance and
reliability of multiprocessors have made them a powerful computing resource.
Such computing environment requires an efficient algorithm to determine when
and on which processor a given task should execute. In multiprocessor systems,
an efficient scheduling of a parallel program onto the processors that
minimizes the entire execution time is vital for achieving a high performance.
This scheduling problem is known to be NP- Hard. In multiprocessor scheduling
problem, a given program is to be scheduled in a given multiprocessor system
such that the program's execution time is minimized. The last job must be
completed as early as possible. Genetic algorithm (GA) is one of the widely
used techniques for constrained optimization.
