HYBRID GASA FOR BI-CRITERIA
MULTIPROCESSOR TASK SCHEDULING WITH
PRECEDENCE CONSTRAINTS
Computer Applications: An International Journal (CAIJ), 1 (1):
1-11 (2014/08 2014)Abstract
Task scheduling on different processors with precedence constraints is NP hard and finds a prominent
place in the field of parallel computing and combinatorial optimization. However, it is quite difficult to
achieve an optimal solution to this problem with traditional optimization approaches owing to the high
computational complexity. Amongst the metaheuristics, Simulated Annealing (SA) and Genetic Algorithm
(GA) represent the powerful combinatorial optimization methods with corresponding strengths and
weaknesses. Borrowing the respective advantages of the two paradigms, an effective combination of GA
and SA called hybrid GASA has been proposed for multiprocessor task scheduling problems with
precedence constraints. The bi-criteria objective function, including the weighted sum of makespan and
total completion has been considered for the analysis. Comparative analysis with the help of defined
performance index on the standard problems shows that the proposed hybrid GASA provides better results
when compared to simple GA and SA alone in terms of solution quality.