Solving multi-objective parallel machine scheduling problem by a modified NSGA-Ⅱ

摘要

In this paper, we modify a Multi-Objective Evolutionary Algorithm, known as Nondominat-ed sorting Genetic Algorithm-Ⅱ (NSGA-Ⅱ) for a parallel machine scheduling problem with three objectives. The objectives are - (1) minimization of total cost due tardiness, (2) minimization of the deterioration cost and (3) minimization of makespan. The formulated problem has been solved by three Multi-Objective Evolutionary Algorithms which are: (1) the original NSGA-Ⅱ (Non-dominated Sorting Genetic Algorithm-Ⅱ), (2) SPEA2 (Strength Pareto Evolutionary Algorithm-2) and (3) a modified version of NSGA-Ⅱ as proposed in this paper. A new mutation algorithm has also been proposed depending on the type of problem and embedded in the modified NSGA-Ⅱ. The results of the three algorithms have been compared and conclusions have been drawn. The modified NSGA-Ⅱ is observed to perform better than the original NSGA-Ⅱ. Besides, the proposed mutation algorithm also works effectively, as evident from the experimental results.